Simple selection of sorting algorithm in Swift

preface

For iOS developers, the implementation of the algorithm doesn't really matter, because you just need to call the advanced interface to get the best algorithm in the system, but it's better to know the principle behind the wheel, isn't it? Without further ado, let's take a look at the details.

Selection sort

Let's take [9, 8, 7, 6, 5] for example.

[9, 8, 7, 6, 5]

The first scan, scan each number, if less than the first number swap, until find the smallest number, swap it to the subscript 0.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

For the second scan, since the first number is determined, the scan starts from the second number, and the small number obtained from the same logic as above is exchanged to subscript 1.

[5, 8, 9, 7, 6]
[5, 7, 9, 8, 6]
[5, 6, 9, 8, 7]

On the third scan, skip two Numbers, scan from the third number, and swap to get subscript 2.

[5, 6, 8, 9, 7]
[5, 6, 7, 9, 8]

At the fourth scan, apply the above logic to get the subscript 3.

[5, 6, 7, 8, 9]

Since there is only one digit at the end, there is no need to swap, so no scanning is required.

Now that we know the logic, let's look at how the code should be written;

func selectSort(list: inout [Int]) {
 let n = list.count
 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 loop is scanned from 0 to n-1, i represents the number of scan advances.

The inner loop goes from i+1, scanning to the last 1 bit, comparing one by one, swapping if less than i.

Selective sorting (Optimization)

Above, we have explained selection sorting by very simple logic, and sure enough, the algorithm is not as difficult as expected. Next, let's see how to optimize this sorting algorithm.

We also use [9, 8, 7, 6, 5] as an example.

[9, 8, 7, 6, 5]

The first scan, and the previous scan, but only remember the minimum index, exit the inner loop when switching.

[5, 8, 7, 6, 9]

In the second scan, the minimum value of bit 1 was determined and then 1 grid was advanced, and the logic was exchanged as above.

[5, 6, 7, 8, 9]

We can clearly see the effect of the optimization, the number of exchanges is reduced, because instead of exchanging values each time, we swap them out of the inner loop after recording with a pointer.

Let's look at how the code can be optimized:

func optimizationSelectSort(list: inout [Int]) {
 let n = list.count
 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 minimum subscript through idx and swap the value if the subscript and the current value are different.

Bubble sort

Now let's look at bubble sort, again, 9, 8, 7, 6, 5.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

0

The first scan, the same scan for each number, the difference is that there are two Pointers going forward at the same time, if n > n-1 is exchanged. Make sure the last value is the maximum value.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

1

For the second scan, scan from the beginning. Since the last scan is determined to be the maximum value, 1 bit less is scanned.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

2

Third scan, same logic as above.

[6, 7, 5, 8, 9]
[6, 5, 7, 8, 9]

At the fourth scan, the sorted value is obtained.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

4

The above may be difficult to understand, more than a few times should be ok.

If that still doesn't work, let's look at the code;

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

5

The outer loop is also scanned from 0 to n-1, which is not repeated.

The inner loop is scanned from scratch (0) to ES85en-1-ES86en (1 bit less per scan), because the last bit is determined to be the maximum each time.

Bubble sort (Optimized)

Bubble sort optimization is not the choice of the sort of optimization so powerful, there may be negative optimization, caution!!

This time we use [5, 6, 7, 9, 8] as an example.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

6

This optimization is not particularly intuitive, it's better to run my source code. The optimization comes from not scanning for idling if the sorting is done. The blank line above is idling.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

7

It's just adding a flag bit to see if it jumps out of the scan.

Quick sort

Quick sort, not a great example, but the most important sort.

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: list.count - 1)
}

We can see from looking at the code directly that we scan the subscript 0 as a ruler, and the larger one is sorted to the right and the smaller one to the left in a recursive way. Because the fuzzy sorting is done at the same time after the first scan, the efficiency is extremely high.

Sorting trade-off

We compared all the sorting algorithms above with the systematic sorting, taking 10,000 random Numbers as an example.

[8, 9, 7, 6, 5]
[7, 9, 8, 6, 5]
[6, 9, 8, 7, 5]
[5, 9, 8, 7, 6]

9

--- 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 quicksort I wrote here is the most efficient, and the system sort is an order of magnitude more efficient than the bubble sort, and the puzzle is the same system sort plus {$0 < By comparing the rules, there will be an order of magnitude increase in efficiency.

Now do you know how to choose the sorting algorithm?

2 minutes and search

@discardableResult func binSearch(list: [Int], find: Int) -> Int {
 var low = 0, high = list.count - 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: list.count - 1, find: find)
}

The principle of 2 points search is not to say much, is half and half and half and half again, the key to this search algorithm is to order, so with the appropriate sorting algorithm is the most important!

Source download: github or local download

conclusion