The original intention of the code is to make it easy to understand. There are many codes optimized by God on the Internet. It is not recommended to copy the code in this article in the project.

Catalog

• Time complexity
  • Operation of Constant Time
  • Computation of Time Complexity
  • Time Complexity of Constant Operational Expression Types
  • Comparisons with the same time complexity
• Bubble sort
  • Improved Bubble Sorting
• Selection sort
  • Binary Selective Sorting
• Insertion sort
• Worst case, best case, average case of time complexity
• Logarithmic device

Time complexity

The former is represented by time complexity, and the latter is represented by time complexity. Spatial complexity (that is, the measure of the size of the temporary storage space occupied by the algorithm in the running process).

• Operation of Constant Time

If an operation has nothing to do with the amount of data, each operation is completed in a fixed time, called a constant operation.
For example, the addressing of array subscripts, a pair of subscripts exchange.

• Constant Operating Quantity

For a single constant time operation, write O(1). Read big O 1.

• Computation of Time Complexity

• Linear time complexity

For example, an algorithm needs to perform N cycles, each of which is a constant operation O(1).

for i in 1..<N+1 {
    //Constant operation
    let firstItem = arr[i-1]
    let secondItem = arr[i]
    if firstItem > secondItem {
        arr.swapAt(i-1, i)
    }
}

T(N)=F(N)=N, time complexity is O (F (N) = O (N).

• Time Complexity of Constant Operational Expression Types

Specifically speaking. In the expression of constant number of operations, as long as the higher order term, not the lower order term, and not the coefficients of the higher order term, the remaining part if recorded as f(N), then the time complexity is O (f(N).

To borrow examples from Baidu Encyclopedia:

for(i=1; i<=n; ++i)
{
    c[i];//This step belongs to the number of basic operations performed:n
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//This step belongs to the basic operation execution times: n square times.
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//This step belongs to the number of times the basic operation is executed: the third power of n.
    }
}

T(N) = A*N_+B*N_+C*N. When N approaches infinity, the influence of cubic power is much greater than that of quadratic power and primary power. Of course, it is also greater than the effect of constant term A.
So the expression f(N)=N.
Time complexity is O(N)=O(f(N)=O(N)=N_

A diagram is attached to facilitate understanding the changes of higher order items when the cardinality increases:

• Comparisons with the same time complexity

To evaluate the performance of an algorithm process, first look at the time complexity index, and then sub-divide it.
The actual running time under different data samples is analyzed, that is, the constant term time.

Bubble sort

Specifically, if the two adjacent digits are larger, the two digits are exchanged and stop when they reach the boundaries of the disordered array.

func bubbleSort(arr: inout [Int]) {
    if arr.count < 2 {
        return
    }
    
    for i in 0..<arr.count {
        for j in 0..<arr.count - (i+1) {
            if arr[j] > arr[j+1] {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
}

Time complexity O(N_) and extra space complexity O(1).

The source of time complexity f (N) = N + (N-1) + (N-2) +... + 2 + 1 is one Arithmetic progression . The general formula of the sum of the first N terms is: N*(N-1)/2 simplified f(N)=N_.

• Improved Bubble Sorting

func bubbleSort2(arr: inout [Int]) {
    if arr.count < 2 {
        return
    }
    var swapped = false //Record whether there are variables for swapping actions
    for i in 0..<arr.count {
        swapped = false
        for j in 0..<arr.count - (i+1) {
            if arr[j] > arr[j+1] {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                swapped = true //Record switching actions
            }
        }
        if swapped == false {
            break //There is no exchange action, indicating that there is order.
        }
    }
}

In extreme cases (for an already ordered array), the algorithm returns after completing the first outer loop.
In fact, only N - 1 Comparisons occur, so in the best case, the complexity of the algorithm is O(N).

Selection sort

Specifically, each iteration records the position of the minimum value in the disordered sequence, and at the end of the iteration, it exchanges with the first position of the disordered sequence to make it the last position of the ordered sequence.

func selectionSort(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    var minIndex :Int
    for i in 0..<arr.count {
        minIndex = i
        for j in i+1..<arr.count { //The loop starts with i+1, which is the second bit of the unordered array.
            minIndex = arr[j]<arr[minIndex] ? j:minIndex //Comparing the current position with the recorded position, the record is the smallest.
        }
        arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array
    }
}

• Binary Selective Sorting

The sequence is divided into three parts: the ordered part of the front segment, the disordered part of the middle segment and the ordered part of the back end.
In each cycle, the maximum and minimum values are placed in two ordered sequences.

func selectionSort2(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    var minIndex :Int
    var maxIndex :Int
    for i in 0..<arr.count {
        minIndex = i
        maxIndex = i
        if i+1 >= arr.count - i {
            return // Because of this step, the loop actually ends at i=arr.count/2.
        }
        for j in i+1..<arr.count - i { //The loop starts with i+1, which is the second bit of the disordered array. And stop at the front of the back-end ordered sequence
            minIndex = arr[j]<arr[minIndex] ? j:minIndex //Comparing the current position with the recorded position, the record is the smallest.
            maxIndex = arr[j]>arr[maxIndex] ? j:maxIndex //Comparing the current position with the recorded position, the record is the largest.
        }

        if maxIndex == i && minIndex == arr.count - (i+1) {
            //If the maximum and minimum are exactly at the boundary, direct exchange can lead to disorder. Manual assignment is required
            let maxValue = arr[maxIndex];
            let minValue = arr[minIndex];
            let maxToValue = arr[arr.count - (i+1)]
            let minToValue = arr[i]
            
            arr[maxIndex] = maxToValue
            arr[arr.count - (i+1)] = maxValue
            arr[minIndex] = minToValue
            arr[i] = minValue
            
        }else if maxIndex == i{
            //If the maximum is in the position where the minimum is to be exchanged, the maximum is exchanged first.
            arr.swapAt(arr.count - (i+1) , maxIndex) //Exchange the last bit of an unordered array with the largest bit
            arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array
        }else  {
            arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array
            arr.swapAt(arr.count - (i+1) , maxIndex) //Exchange the last bit of an unordered array with the largest bit
        }
    }
}

In this way, although the complexity is O(N), in fact, the expression coefficients are more than 1/2 smaller than the classical selection ranking.

Insertion sort

Specifically, it will be compared from the end of the ordered sequence, and exchanged if the front bit is larger than the rear bit.

func insertionSort(arr : inout [Int]) {
    if arr.count<2 {
        return
    }
    for i in 1..<arr.count { //Unordered arrays from i=1 to the end
        for j in (0...i-1).reversed() {  //Cycling in an ordered array from i-1 to 0
            if arr[j+1] > arr[j] {  //j+1 is at the top of an unordered array when it is first executed
                break //If the back position is larger than the front position, the order is indicated. Exit the current loop
            }
            arr.swapAt(j, j+1)//Otherwise exchange
        }
    }
}

If it's improved, maybe you can try to determine the specific position by dichotomy and then move the whole back and insert it.

Worst case, best case, average case of time complexity

For insertion sort, which has definite termination conditions, the actual time complexity is related to the actual situation of the data.
Best of all, it's orderly at the beginning. We only need to perform a large loop with O(N) complexity.
The worst case is that the entire array is arranged in reverse order once with O(N_) complexity.
Average case refers to the average expected complexity in most cases.

When the actual situation of the data has an impact on the algorithm process, the worst case is used as the time complexity.

However, we can take advantage of active disruption of the impact of data conditions. Express the complexity in a way that is easily mathematically desirable (refer to random fast scheduling).

Logarithmic device

• The general steps for designing logarithms are:

1. Have a method you want to test a; write your own method
2. Implement an absolutely correct method even if the complexity is not good b; the system can bring its own method.
3. Implement a random sample generator.
4. The method of realizing the comparison; whether the two results are consistent in the end
5. Compare method a with method b many times to verify that method a is correct.
6. If there is a sample that makes the alignment wrong, which method does the printed sample analysis make a mistake?
7. When the number of samples is large, the comparison test is still correct, which can confirm that method a is correct.

• Realize logarithm

One, two and four of them have already been said. There's nothing to say about 6 and 7.

3. Implementing a Random Sample Generator

/// Random Array Generator
///
/// - Parameters:
///- size: maximum length
///- value: Maximum
///- Returns: Random Array
func generateRandomArray(size : Int ,value : Int) -> [Int] {
    var arr :[Int]
    arr = Array.init()
 
    for i in 0..<Int(arc4random() % 10) * size / 10  {
        let item = Int(arc4random() % 10)*value/10
        arr.append(item)
    }
    print(arr)
    return arr
}

• Compare method a with method b many times to verify that method a is correct.

var checkOK = true
for i in 0..<10000 {
    var arr1 = generateRandomArray(size: 5, value: 20)
    var arr2 = arr1 //Arrays are of value type in swift, and assignment actions copy automatically
    let originalArr = arr1
    arr1.sort()
    heapSort(arr: &arr2)
    
    if arr1 != arr2 {
        checkOK = false
        print(originalArr)
        print(arr2)
        break
    }
}

print(checkOK ? "Comparison success":"Comparison failure")


//Printing
[0, 6, 2, 12, 18]
[0, 6, 12, 2, 18]
//Comparison failure

The wrong raw data has been printed out, and you can reproduce it at will for debugging.

var arr = [0, 6, 12, 2, 18];
print(arr)
heapSort(arr: &arr)
print(arr)

Reference material

Zuo Shenniu Course Network Algorithms Course
A Simple Explanation of Time Complexity and Space Complexity
Selection and Sorting and Improvement Method