Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I insert an element at the correct position into a sorted array in Swift?

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a sorted array.

What is the best and high-performance way to do this in pure Swift?

Something along the lines of:

var myArray = ["b", "e", "d", "a"] myArray.sort { $0 < $1 }  // myArray is now [a, b, d, e]  myArray.append("c") myArray.sort { $0 < $1 }  // myArray is now [a, b, c, d, e] 

Instead of appending the new element and then sorting the array, I would like to figure out the correct position and insert the element:

let index = [... how to calculate this index ??? ...] myArray.insert("c", atIndex: index) 
like image 772
Klaas Avatar asked Oct 31 '14 15:10

Klaas


People also ask

What is the procedure to insert into a sorted array?

var array = [1,2,3,4,5,6,7,8,9]; var element = 3.5; function insert(element, array) { array. push(element); array. sort(function(a, b) { return a - b; }); return array; } console. log(insert(element, array));

How do I arrange an array in ascending order in Swift?

To sort an integer array in increasing order in Swift, call sort() method on this array. sort() method sorts this array in place, and by default, in ascending order.


1 Answers

Here is a possible implementation in Swift using binary search (from http://rosettacode.org/wiki/Binary_search#Swift with slight modifications):

extension Array {     func insertionIndexOf(_ elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {         var lo = 0         var hi = self.count - 1         while lo <= hi {             let mid = (lo + hi)/2             if isOrderedBefore(self[mid], elem) {                 lo = mid + 1             } else if isOrderedBefore(elem, self[mid]) {                 hi = mid - 1             } else {                 return mid // found at position mid             }         }         return lo // not found, would be inserted at position lo     } } 

As with indexOfObject:inSortedRange:options:usingComparator: it is assumed that the array is sorted with respect to the comparator. It returns either (any) index of the element if the element is already present in the array, or the index where it can be inserted while preserving the order. This corresponds to the NSBinarySearchingInsertionIndex of the NSArray method.

Usage:

let newElement = "c" let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <) myArray.insert(newElement, at: index) 
like image 112
Martin R Avatar answered Sep 20 '22 15:09

Martin R