Preface
For iOS developers, the implementation process of algorithms is not very concerned, because you only need to call advanced interfaces to get the best algorithm in the system, but understanding the principles behind the wheel can make better choices, right? I won’t say much below, let’s take a look at the detailed introduction together.
Select Sort
Let’s take [9, 8, 7, 6, 5] as an example.
[9, 8, 7, 6, 5]
For the first scan, scan each number, if smaller than the first number, exchange until the smallest number is found and exchange it to subscript 0.
[8, 9, 7, 6, 5] [7, 9, 8, 6, 5] [6, 9, 8, 7, 5] [5, 9, 8, 7, 6]
In the second scan, since the first number is determined, the scan starts from the second number, and the logic is exchanged to subscript 1 with the same number as the previous obtained.
[5, 8, 9, 7, 6] [5, 7, 9, 8, 6] [5, 6, 9, 8, 7]
The third scan, skip two numbers, start the scan from the third number, and exchange to obtain the subscript 2.
[5, 6, 8, 9, 7] [5, 6, 7, 9, 8]
In the fourth scan, apply the above logic to obtain the subscript 3.
[5, 6, 7, 8, 9]
Since there is only one single number in the end, no exchange is required, and no scanning is required.
After understanding the logic, let’s see how to write the code;
func selectSort(list: inout [Int]) {
let n =
for i in 0..<(n-1) {
var j = i + 1
for _ in j..<n {
if list[i] > list[j] {
list[i] ^= list[j]
list[j] ^= list[i]
list[i] ^= list[j]
}
j += 1
}
}
}
The outer layer loops to scan from 0 to n-1, and i represents the number of scan advances.
The inner layer loop is from i+1, scans to the last bit, compares one by one, and exchanges if it is smaller than i.
Select Sort (Optimization)
In the above, we have explained the selection sorting through very simple logic. Sure enough, the algorithm is not as difficult as imagined. Next, let’s take a look at how to optimize this sorting algorithm.
Let us also take [9, 8, 7, 6, 5] as an example.
[9, 8, 7, 6, 5]
The first scan is the same as before, but only remember the subscript of the minimum value and exchange it when exiting the inner loop.
[5, 8, 7, 6, 9]
The second scan is used to determine the minimum value of the first bit and then advance one grid. The logic is exchanged as above.
[5, 6, 7, 8, 9]
We can clearly see the optimization effect, and the number of exchanges has decreased, because we do not exchange values every time, but record them with a pointer and jump out of the inner loop and exchange them.
Let's take a look at how the code should be optimized:
func optimizationSelectSort(list: inout [Int]) {
let n =
var idx = 0
for i in 0..<(n - 1) {
idx = i;
var j = i + 1
for _ in j..<n {
if list[idx] > list[j] {
idx = j;
}
j += 1
}
if idx != i {
list[i] ^= list[idx]
list[idx] ^= list[i]
list[i] ^= list[idx]
}
}
}
Record the subscript of the minimum value through idx, and exchange the numerical value if the subscript and the current value are not equal.
Bubble sort
Next, let’s look at the bubble sorting, taking [9, 8, 7, 6, 5] as an example.
[9, 8, 7, 6, 5]
The first scan is the same for each number. The difference is that there are two pointers moving forward at the same time. If n>n-1, then exchange. Make sure the last value is the maximum value.
[8, 9, 7, 6, 5] [8, 7, 9, 6, 5] [8, 7, 6, 9, 5] [8, 7, 6, 5, 9]
The second scan is performed from the beginning, and since it is determined that the end is the maximum value, one less scan is scanned.
[7, 8, 6, 5, 9] [7, 6, 8, 5, 9] [7, 6, 5, 8, 9]
The third scan is the same as the above logic.
[6, 7, 5, 8, 9] [6, 5, 7, 8, 9]
The fourth scan is used to obtain the sorted values.
[5, 6, 7, 8, 9]
The above may be difficult to understand, and it should be fine to read it a few more times.
If you still can’t understand, let’s take a look at the code;
func popSort(list: inout [Int]) {
let n =
for i in 0..<n-1 {
var j = 0
for _ in 0..<(n-1-i) {
if list[j] > list[j+1] {
list[j] ^= list[j+1]
list[j+1] ^= list[j]
list[j] ^= list[j+1]
}
j += 1
}
}
}
The outer loop also scans from 0 to n-1, so I will not elaborate on this point.
The inner layer cycle starts by scanning from 0 to n-1-i, which means that one less scan is scanned every time. The last bit should be determined as the maximum value each time.
Bubble sort (optimization)
The optimization of bubble sorting is not as powerful as the optimization of choosing sorting. It may also produce negative optimizations. Use with caution!!
This time we use [5, 6, 7, 9, 8] to give an example.
--- scope of: popsort --- [5, 6, 7, 9, 8] [5, 6, 7, 8, 9] --- scope of: opt_popsort --- [5, 6, 7, 9, 8] [5, 6, 7, 8, 9]
This optimization is not particularly intuitive, it is best to run my source code. The optimization comes from if the sorting has been completed, you don't need to scan the idle. The empty line above is idle.
func optimizationPopSort(list: inout [Int]) {
let n =
for i in 0..<n-1 {
var flag = 0
var j = 0
for _ in 0..<(n-1-i) {
if list[j] > list[j+1] {
list[j] ^= list[j+1]
list[j+1] ^= list[j]
list[j] ^= list[j+1]
flag = 1
}
j += 1
}
if flag == 0 {
break
}
}
}
It is to add a flag to determine whether the scan will jump out.
Quick sort
Quick sorting is not particularly easy to give, but the most important sorting is.
func quickSort(list: inout [Int]) {
func sort(list: inout [Int], low: Int, high: Int) {
if low < high {
let pivot = list[low]
var l = low; var h = high
while l < h {
while list[h] >= pivot && l < h {h -= 1}
list[l] = list[h]
while list[l] <= pivot && l < h {l += 1}
list[h] = list[l]
}
list[h] = pivot
sort(list: &list, low: low, high: l-1)
sort(list: &list, low: l+1, high: high)
}
}
sort(list: &list, low: 0, high: - 1)
}
We can see directly at the code that we use the subscript 0 as a ruler and scan the rows larger than it, and sort them recursively in order to sort them in a recursive way. Since the fuzzy sort is performed after one scan, it is extremely efficient.
Sort and trade-offs
We compared all the sorting algorithms mentioned above with the sorting of the system, taking 10,000 random numbers as an example.
scope(of: "sort", execute: true) {
scope(of: "systemsort", execute: true, action: {
let list = randomList(10000)
timing {_ = ()}
// print(())
})
scope(of: "systemsort2", execute: true, action: {
let list = randomList(10000)
timing {_ = {$0 < $1}}
// print( {$0 < $1})
})
scope(of: "selectsort", execute: true, action: {
var list = randomList(10000)
timing {selectSort(list: &list)}
// print(list)
})
scope(of: "opt_selectsort", execute: true, action: {
var list = randomList(10000)
timing {optimizationSelectSort(list: &list)}
// print(list)
})
scope(of: "popsort", execute: true, action: {
var list = randomList(10000)
timing {popSort(list: &list)}
// print(list)
})
scope(of: "opt_popsort", execute: true, action: {
var list = randomList(10000)
timing {optimizationPopSort(list: &list)}
// print(list)
})
scope(of: "quicksort", execute: true, action: {
var list = randomList(10000)
timing {quickSort(list: &list)}
// print(list)
})
}
--- scope of: sort --- --- scope of: systemsort --- timing: 0.010432243347168 --- scope of: systemsort2 --- timing: 0.00398015975952148 --- scope of: selectsort --- timing: 2.67806816101074 --- scope of: opt_selectsort --- timing: 0.431572914123535 --- scope of: popsort --- timing: 3.39597702026367 --- scope of: opt_popsort --- timing: 3.59421491622925 --- scope of: quicksort --- timing: 0.00454998016357422
We can see that the fast-row sort I wrote is the most efficient, and is the same as the system sort, and the choice is more efficient than bubble. What is confusing is that the system sort is also combined with the comparison rules of {$0 < $1}, and the efficiency will be improved by orders of magnitude.
Do you know how to choose the sorting algorithm now?
Binary search
@discardableResult func binSearch(list: [Int], find: Int) -> Int {
var low = 0, high = - 1
while low <= high {
let mid = (low + high) / 2
if find == list[mid] {return mid}
else if (find > list[mid]) {low = mid + 1}
else {high = mid - 1}
}
return -1;
}
@discardableResult func recursiveBinSearch(list: [Int], find: Int) -> Int {
func search(list: [Int], low: Int, high: Int, find: Int) -> Int {
if low <= high {
let mid = (low + high) / 2
if find == list[mid] {return mid}
else if (find > list[mid]) {
return search(list: list, low: mid+1, high: high, find: find)
}
else {
return search(list: list, low: low, high: mid-1, find: find)
}
}
return -1;
}
return search(list: list, low: 0, high: - 1, find: find)
}
I won’t talk about the principle of binary search, it is to fold half and half and then fold half. The key to this search algorithm is to be orderly, so the most important thing is to cooperate with a suitable sorting algorithm!
Source code download:githuborLocal download
Summarize
The above is the entire content of this article. I hope that the content of this article has certain reference value for everyone's study or work. If you have any questions, you can leave a message to communicate. Thank you for your support.