# Algorithmic Basis - Time Complexity, Three Ordering Algorithms of Conventional O(N) (Bubble, Selection, Insertion)

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

There are two very important indicators to measure the quality of the code: run time and occupied space.

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

In the method, the number of repeated executions of basic operations is a function of the problem size n, which is expressed by T(n).
If there is a function, f (N). When N approaches infinity, T(n)/f(n) approaches a constant of not 0.
f(n) is the same order of magnitude function of T(n). T(n) = O (f(n). O (f(n) is the asymptotic time complexity of the algorithm.

• ###### 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

For the time complexity of T(N) as an expression type, F(N) is simply to simplify it into an expression that has the greatest impact on N when it approaches infinity.

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

In the bubble sorting process, the array will be divided into two parts, the first half is an unordered sequence, and the second half is an ordered sequence. The largest value in an unordered sequence is constantly bubbling into an ordered sequence. After bubbling, our sequence is created.

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

The classic bubble sort, whether or not the array has been ordered. We can improve on this point by traversing it over and over again.

``````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

The basic idea is the same as bubble sort. The first half is an ordered sequence, but the second half is an unordered sequence. The largest value in an unordered sequence is constantly bubbling into an ordered sequence. After bubbling, our sequence is created.

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

There's nothing to improve on the selection sort itself, but we can open the bow left and right.

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

The basic idea is that the first half is ordered, and the second half is disordered. The disordered sequence continuously pushes its first element to the ordered sequence, and the ordered sequence inserts it into the appropriate position.

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

Logger is used to test the correctness of code. When we can't find a suitable oj system to test our own code, we can write a logger to test the code ourselves.

• ##### 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

Keywords: Swift network

Added by bugz-2849 on Wed, 15 May 2019 23:10:28 +0300