12 - Sorting algorithm with time complexity of O(n^2)

The order n^2 sorting algorithm doesn’t do very well, but for those of you who are new to it, it’s worth learning. There are three kinds of sorting algorithms: 1) bubble sorting; 2) Select sort; 3) Insertion sort.

Bubble sort

The principle of

Firstly, introduce the principle of bubble sort algorithm:

Starting with the first element, the adjacent elements are compared, and if the first is larger than the second, their values are swapped
When you do the same thing for each group of adjacent elements, the last group of elements must be the largest
Repeat these steps for all but the last sorted element
Repeat the above steps until there are no sets of numbers to compare

example

Let’s take an example. Suppose we have the following array:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 8 7 | | | | 14 5 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

According to the above principle, the first one is compared with the second one, and 8 is exchanged with 7. The result is as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 7 8 | | | | 14 5 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

The second and third numbers continue to compare, and the third number 14 is greater than the second number 8, so you don’t have to switch.

The third and fourth comparison, 14 and 5 are swapped, so the first comparison is done, and the last number is the largest number. Here are the results:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 7 8 | | | | 5 14 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

The following is the second round of comparison, the first group of 7 and 8 order is correct, no need to switch; The first group, 8 and 5, needs to be switched, and the results are as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 7 5 | | | | 8 14 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

The last one is already big, so no comparison. That is, every time you go through a round of comparison, you have one less element to compare in the next round.

In the third round of comparison, 7 is exchanged with 5, and the results are as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 5 7 | | | | 8 14 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

Because this is the third round of comparison, you don’t have to compare the next two numbers, and at this point, you’re done.

implementation

To keep our methods generic, we don’t just sort arrays. Swift has a protocol called MutableCollection. This protocol stipulates that the collection must support access or modification of the elements in the collection by subscript, so we sort the objects of MutableCollection directly.

The implementation code is as follows:

func bubbleSort<T> (_ collection: inout T)
    where T: MutableCollection.T.Element: Comparable {
        guard collection.count > 1 else {
            return
        }
        for end in collection.indices.reversed() {
            var swapped = false
            var current = collection.startIndex
            while current < end {
                let next = collection.index(after: current)
                if collection[next] < collection[current] {
                    collection.swapAt(next, current)
                    swapped = true
                }
                current = next
            }
            if !swapped {
                return}}}Copy the code

Code parsing:

First of all, we have to have at least two elements before we can sort ifcollection.countNo greater than1, directly return
Because after each round of comparison, the next round of comparison has to ignore the last element, soforThe conditions of the cycle, the cycleindicesReverse order
Defines aswappedVariable that records whether elements have been swapped in the current round of comparison
whileThe loop performs the current round of comparison, swapping if the next element is less than the previous one
ifswapped 为 false“, indicating that the current round of comparison did not swap elements, which means that the order has been sorted, exit the loop ahead of time

test

var ints = [4.5.5467.73.234.678.87.989]
bubbleSort(&ints)
print(ints)

/ / the result
[4.5.73.87.234.678.989.5467]
Copy the code

The result is correct.

Selection sort

Selection sort offers some improvements to bubble sort that reduce the number of exchanges between elements. The selection sort is changed only after each round of comparison.

example

Let’s take an example. Suppose we have the following array:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 8 7 | | | | 14 5 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

First find the smallest element 5, 8 is swapped with 5, and the result is as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 5 7 | | | | 14 8 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

Find the smallest element outside of the first element 7,7 in the second position, no interchange.

Find the smallest element 8 and place it in the third position. The result is as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 5 7 | | | | 8 14 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

At this point, the sorting is complete. Obviously, the number of swaps is much less than with bubble sort.

implementation

To keep our methods generic, we sort objects of type MutableCollection directly, as with bubble sort.

func selectionSort<T> (_ collection: inout T)
    where T: MutableCollection.T.Element: Comparable {
        guard collection.count > 1 else {
            return
        }
        for current in collection.indices {
            var lowest = current
            var next = collection.index(after: current)
            while next < collection.endIndex {
                if collection[next] < collection[lowest] {
                    lowest = next
                }
                next = collection.index(after: next)
            }
            if lowest ! = current {
                collection.swapAt(lowest, current)
            }
        }
}
Copy the code

Code parsing:

First of all, we have to have at least two elements before we can sort ifcollection.countNo greater than1, directly return
Because every time you go through a round, you have to ignore the previous element in the next round, so you useforLoop, the condition starts with the smallest subscript
whileLoop to find the smallest element
If the smallest element found is not equal to the current element, the positions are swapped

test

var ints = [4.5.5467.73.234.678.87.989]
selectionSort(&ints)
print(ints)

/ / the result
[4.5.73.87.234.678.989.5467]
Copy the code

The result is correct.

Insertion sort

How insertion sort works: The current element is compared to the previous one, and if the current element is less than the previous one, the position is switched, and the process is repeated until it is placed in the appropriate position.

example

Let’s take an example. Suppose we have the following array:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 8 7 | | | | 14 5 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

The first element is ignored because there are no other elements before it.

The second element, 7, is compared with the previous element, 8, and needs to be switched. The result is as follows:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 7 8 | | | | 14 5 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

The third element, 14, is larger than both of the previous elements, so you don’t have to swap them.

The fourth element, 5, is smaller than any of the previous ones, so it’s going to keep swapping with the previous ones until it’s in the first place. Here are the results:

+ -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + + -- -- -- -- -- -- -- -- + | | | | | | | | | | 5 7 | | | | 8 14 | | | | | | | | | | + -- -- -- -- -- -- -- -- + +--------+ +--------+ +--------+Copy the code

implementation

To keep the method generic, we don’t sort the array type directly, but the Swift collection type. First, we need to swap the locations of the elements. The collection type must be MutableCollection. In addition, we need to access the last element, and the BidirectionalCollection type has this feature. So our sort type is BidirectionalCollection & MutableCollection. The code is as follows:

func insertionSort<T> (_ collection: inout T)
    where T: BidirectionalCollection & MutableCollection.T.Element: Comparable {
        guard collection.count > 1 else {
            return
        }
        for current in collection.indices {
            var moving = current
            while moving > collection.startIndex {
                let previous = collection.index(before: moving)
                if collection[previous] > collection[moving] {
                    collection.swapAt(previous, moving)
                } else {
                    break
                }
                moving = previous
            }
        }
}
Copy the code

First of all, we have to have at least two elements before we can sort ifcollection.countNo greater than1, directly return
forThe loop guarantees the element that is currently moving to the left
whileInside the loop, the current element is compared to the previous one, and if the previous one is greater than the current one, the position is swapped. Otherwise, the first elements would have been sorted, so it’s straightforwardbreak

test

var ints = [4.5.5467.73.234.678.87.989]
insertionSort(&ints)
print(ints)

/ / the result
[4.5.73.87.234.678.989.5467]
Copy the code

The result is correct.

Welcome to join my Swift development group: 536353151.

Complete code >>

The resources

Data Structures and Algorithms in Swift — Raywenderlich.com. Click on the link to buy the original.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

12 – Sorting algorithm with time complexity of O(n^2)

Bubble sort

The principle of

example

implementation

test

Selection sort

example

implementation

test

Insertion sort

example

implementation

test

Complete code >>

The resources

12 – Sorting algorithm with time complexity of O(n^2)

Bubble sort

The principle of

example

implementation

test

Selection sort

example

implementation

test

Insertion sort

example

implementation

test

Complete code >>

The resources

Related Posts

Explore the underlying implementation of KVO

IOS startup optimization based on binary rearrangement

Some practices on Swift Codable