Binary search
Here’s how binary search works:
Divide the array in half and determine whether what you are looking for (called the search key) is in the left or right half. How do you determine what half of the search key is? That’s why you sort the array in the first place, so that you can do a simple < or > comparison. If the search key is on the left half, repeat the process there: divide the left half into two smaller sections and see which one the search key is on. (Again, do the same for the right half.) Repeat until the search key is found. If you cannot split the array further, you must regrettably conclude that the search key is not in the array. Now you know why it’s called a “binary” search: at each step it splits the array in half. Divide and conquer quickly Narrows the search key.
This is a recursive implementation of binary search in Swift:
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? { if range.lowerBound >= range.upperBound { // If we get here, then the search key is not present in the array. return nil } else { // Calculate where to split the array. let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2 // Is the search key in the left half? if a[midIndex] > key { return binarySearch(a, key: key, range: range.lowerBound .. < midIndex) // Is the search key in the right half? } else if a[midIndex] < key { return binarySearch(a, key: key, range: midIndex + 1 .. < range.upperBound) // If we get here, then we've found the search key! } else { return midIndex } } }Copy the codeCustom types can be enabled in Swift by implementing the Equatable protocol to support == and! = both operators; Comparable inherits from Equatable and implements Comparable to enable type support for the >, >=, <, <= operators.
Try copying the code to playground and doing the following:
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] binarySearch(numbers, key: 43, range: 0 .. < numbers.count) // gives 13Copy the codeNotice that the numbers array is sorted. Otherwise the binary search algorithm won’t work!
Binary search searches by splitting an array in half, but we don’t actually create two new arrays. We use SwiftRange objects to track these splits. Initially, this range covers the entire array, 0.. “The Numbers. The count. As we split the array, the range gets smaller and smaller.
Note: One thing to note is that range.upperBound always points to the element after the last element. In this case, the range is 0.. <19, because there are 19 numbers in the array, range.lowerBound = 0 and range.upperBound = 19. But in our array, the last element is in index 18 instead of 19, because we’re counting from 0. Keep this in mind when working with scopes: upperBound is always one more index than the last element.
Note: Many binary searches evaluate midIndex = (lowerBound + upperBound) / 2. This contains a subtle bug that can occur in very large arrays, because lowerBound + upperBound may overflow the maximum number an integer can hold. This is unlikely to happen on 64-bit cpus, but it definitely can happen on 32-bit machines.
Binary search is recursive in nature, because you apply the same logic to smaller and smaller subarrays over and over again. However, this does not mean that you must implement binarySearch() as a recursive function. It is often more efficient to convert a recursive algorithm to an iterative version, using simple loops rather than lots of recursive function calls.
This is an iterative implementation of binary search in Swift:
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? { var lowerBound = 0 var upperBound = a.count while lowerBound < upperBound { let midIndex = lowerBound + (upperBound - lowerBound) / 2 if a[midIndex] == key { return midIndex } else if a[midIndex] < key { lowerBound = midIndex + 1 } else { upperBound = midIndex } } return nil }Copy the codeAs you can see, the code is very similar to the recursive version. The main difference is the use of a while loop.
Using iteration:
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43) // gives 13
Copy the codeConclusion:
Is it a problem that arrays have to be sorted first? Sorting takes time — a combination of binary search and sorting can be slower than a simple linear search. But in cases where you sort only once and then search multiple times, binary search works.
Insertion Sort
func insertionSort(_ array: [Int]) -> [Int] { var a = array // 1 for x in 1.. <a.count { // 2 var y = x while y > 0 && a[y] < a[y - 1] { // 3 a.swapAt(y - 1, y) y -= 1 } } return a } let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ] insertionSort(list)Copy the codeCode working principle:
Start by creating a copy of the array. This is necessary because we cannot modify the contents of the parameter Array directly. InsertionSort () returns a copy of the original array, just as Swift already has the sort() method.
There are two loops inside the function, and the outer loop looks for each element in the array in turn; This is the process of taking the top number from the heap. Part is ordered variable x over and heap start index (namely | symbol position). Remember, at any given time, the array of positions from 0 to x is ordered, and the rest is unordered.
The inner loop starts at the element in position X. X is the element at the top of the heap, which may be smaller than all of the preceding elements. The inner loop starts at the end of the ordered array and looks forward. Each time we find a large element, we swap them until the end of the inner loop. The first part of the array is still ordered, and the ordered element is added.
Note: The outer loop starts at 1, not 0. Moving the first element from the top of the heap to the ordered array makes no sense and can be skipped.
performance
Insertion sort is very fast if the array is already sorted. This may sound obvious, but not all search algorithms are like this. In practice, a lot of data (most, perhaps not all) is already sorted, and insertion sort is a good choice in this case.
The worst and average performance of insert sort is O(n^2). This is because there are two nested loops in the function. Others, such as quicksort and merge sort, have O(n log n) performance and are faster when there are lots of inputs.
Insert sort is actually pretty fast when sorting small arrays. Some libraries switch from quicksort to insert sort when the amount of data is 10 or less.
We did a speed test to compare our insertionSort() with Swift’s built-in sort(). In an array of about 100 elements, the difference in speed is very small. And then, if you input a very large amount of data, O(n^2) is immediately much worse than O(n log n), much worse in insert sort.
Selection Sort
func selectionSort(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } // 1 var a = array // 2 for x in 0 .. < a.count - 1 { // 3 var lowest = x for y in x + 1 .. < a.count { // 4 if a[y] < a[lowest] { lowest = y } } if x ! = lowest { // 5 a.swapAt(x, lowest) } } return a } let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ] selectionSort(list) // [-1, 0, 1, 2, 3, 3, 5, 8, 9, 10, 26, 27]Copy the codeStep by step code description:
If the array is empty or contains only a single element, no sorting is required.
Generates a copy of the array. This is necessary because we cannot modify the contents of the array parameter directly in Swift. Like Swift’s sort() function, selectionSort() returns a sorted copy of the original array.
There are two loops in the function. The loop looks at each element in the array in turn; This is the reason why forward | bar.
The inner loop implementation finds the smallest number in the rest of the array.
Swap the current array index number for the smallest number. If judgments are necessary because you cannot swap() the same element in Swift.
There is no swap() method for arrays in Swift, only swapAt(), and swapAt() swaps the same element without a problem. This could be a Swift version update issue.
Conclusion:
For each element of the array, selection sort swaps places using the smallest value in the rest of the array. As a result, the array is sorted from left to right. (You can also work from right to left, in which case you always look for the largest number in the array. Try it!)
Note: The outer loop ends with index A.count-2. The last element will automatically be in the correct position because there are no smaller elements left.
Performance:
Selection sort is easy to understand, but slow O(n^2). It’s worse than insert sort, but better than bubble sort. Finding the lowest element in the rest of the array is slow, especially because the inner loop repeats itself.
Heap sort uses the same principles as selection sort, but uses a quick way to find the minimum value in the rest of the array. Heap sort performance is O(nlogn).
Merge Sort
Top-down implementation (recursive method)
Swift implementation of merge sort:
func mergeSort(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } // 1 let middleIndex = array.count / 2 // 2 let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3 let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4 return merge(leftPile: leftArray, rightPile: rightArray) // 5 } func merge(leftPile: [Int], rightPile: [Int]) -> [Int] { // 1 var leftIndex = 0 var rightIndex = 0 // 2 var orderedPile = [Int]() // 3 while leftIndex < leftPile.count && rightIndex < rightPile.count { if leftPile[leftIndex] < rightPile[rightIndex] { orderedPile.append(leftPile[leftIndex]) leftIndex += 1 } else if leftPile[leftIndex] > rightPile[rightIndex] { orderedPile.append(rightPile[rightIndex]) rightIndex += 1 } else { orderedPile.append(leftPile[leftIndex]) leftIndex += 1 orderedPile.append(rightPile[rightIndex]) rightIndex += 1 } } // 4 while leftIndex < leftPile.count { orderedPile.append(leftPile[leftIndex]) leftIndex += 1 } while rightIndex < rightPile.count { orderedPile.append(rightPile[rightIndex]) rightIndex += 1 } return orderedPile } //[22, 44, 50, 66, 77, 123, 654, 888, 50,66,44,22,77,999,123,654,888] ([999] mergeSort)}Copy the codeBottom-up implementation (iteration)
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let n = a.count
var z = [a, a] // 1
var d = 0
var width = 1
while width < n { // 2
var i = 0
while i < n { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]
Copy the codeperformance
The speed of the merge sort algorithm depends on the size of the array it needs to sort. The larger the array, the more work it needs to do. Whether the initial array is sorted or not doesn’t affect the speed of the merge sort algorithm, because you will do the same number of splits and comparisons regardless of the initial order of the elements. Therefore, the time complexity of the best, worst and average cases will always be O(n log n). One drawback of the merge sort algorithm is that it requires a temporary “working” array of the same size as the array being sorted. It does not sort in place, like quicksort for example. Most implementations of merge sort algorithms are stable sorts. This means that array elements with the same sort key will remain in the same order relative to each other after sorting. This is not important for simple values like numbers or strings, but when sorting more complex objects, it can be problematic if the sorting is not stable.