Three sorting algorithms of O(n^2) time

There are many kinds of sorting, some of the algorithms have not even heard of the name, after this period of brush questions, I summarize here a few common sorting. As we all know, algorithms take time complexity and space complexity into account, so I divide algorithms into three categories, respectively, time complexity is O(n^2), O(nlogn), O(n). Note that time complexity here refers to average time complexity. Worst-case and best-case time complexity are discussed below.

For sorting algorithms, we need to know a couple of things, what is the time complexity of the algorithm? Is it a sort in place algorithm? Is the algorithm stable?

In my opinion, time complexity can be understood as the number of times the code needs to be executed. The more times the code needs to be executed, the longer it takes, of course, compared with the same amount of data. The concept of in-place sorting, however, can be pulled into space complexity, as the name implies that the in-place sorting operation directly in the original array, no extra memory, space complexity is O(1). The last question is whether the algorithm is stable, what is stable, when there are two equal numbers in an array, if the order of the two equal numbers does not change after sorting, it is a stable algorithm, otherwise it is an unstable algorithm.

Bubble sort

As the name suggests, the elements to be sorted are replaced one by one, like bubbles rising from water. How does it work? Let’s imagine a set of elements waiting to be sorted, such as the five numbers 2, 5, 1, 7, 0, if we wanted to sort it from smallest to largest.

According to the bubbling algorithm, we compare the size of the first and second two adjacent numbers. If 2 is greater than 5, we switch the positions of 2 and 5. Of course, 2 is definitely less than 5, so the first step is not swapped. So switch the 5 and 1, repeat the process, and by the time the first bubble completes, the 7 will be at the bottom. Each bubble can move a number to its proper position, and n times can sort n data, so the bubble time is O(n^2). Here’s the demo

Let’s look at the code implementation. I’m using go here, but the principle is the same, isn’t it very simple?

Package main import "FMT" func main(){a :=[]int{1,2,5,8,3,} bubbleSort(a) FMT.Println(a)} func bubbleSort(array []int) {// here is the bubble sort function n := len(array) for I := 0; i < n; i++{ for j := 1; j < n; j++{ if array[j] < array[j-1] { temp := array[j] array[j] = array[j-1] array[j-1] = temp } } } }Copy the code

Of course, we can optimize the bubble sort, for example, if there’s no movement in a bubble, then we can stop it, because if there’s no movement, it’s already ordered.

As can be seen, only one temporary variable is applied in the code, and the exchange process is directly in the original array operation, so bubble sort is an in-place sorting algorithm, and if two numbers are equal, it can not exchange positions, so it is a stable algorithm.

Insertion sort

The bubble sort above is a static array sort. If we insert a value into an already ordered array, how can we keep it ordered? And that’s where insertion sort comes in.

The idea of insertion sort is to divide the elements to be sorted into sorted parts and unsorted parts. Each time, a value is removed from the unsorted part and inserted into the sorted part. When the unsorted part is empty, the sorting of elements is completed. It’s easy to understand if you look at the GIF

Code implementation

Package main import "FMT" func main(){a :=[]int{7,2,9,0,3,} insertionSort(a) fmt.println (a)} func insertionSort(arr) []int) []int { for i := range arr { preIndex := i - 1 current := arr[i] for preIndex >= 0 && arr[preIndex] > current { arr[preIndex+1] = arr[preIndex] preIndex-- } arr[preIndex+1] = current } return arr }Copy the code

In terms of the time of insertion sort, in the best case, you insert a value into an ordered array, you only need to traverse it once, so it’s O(n), and in the worst case, the array is in reverse order, so every insert is the first place in the array, so it’s O(n^2). What about the average time complexity? We know that the time to insert one value into an array is O(n), so inserting n values is O(n^2).

Insertion sort, like sham sort, is also an in-place sort algorithm, which also does not swap equal numbers, so it is also a stable algorithm.

Selection sort

Select sort is similar to insert sort in that the sorted part and the unsorted part are separated first, but select sort is to select the largest or smallest element from the unsorted part each time and then insert it into the previously sorted part.

In the best case, starting with the first piece of data, each one is iterated through the array, and even though we know that the array is already sorted, the algorithm still scans one by one, every time we insert a value into the sorted part, so the time is O(n^2). Again, the worst case, the average time complexity, is o(n^2).

code

Package main import "FMT" func main(){a :=[]int{7,2,9,0,3,} selectionSort(a) FMT.Println(a)} func selectionSort(array []int)[]int { length := len(array) if length < 2 {return array} for i := 0; i < length; i++ { for j := i; j < length; j++ { if array[j] < array[i] { temp := array[j] array[j] = array[i] array[i] = temp } } } return array }Copy the code

Is selection sort an in-place sort algorithm? Of course it is, same as above, same order one space complexity, so is selection sort a stable algorithm? That’s not the case. Every time it swaps the smallest number to the front, the number that gets swapped to the back might be the same as the number in the middle, and then their order changes. For example,3, 4,6,3,2, the first round will swap the first 3 with the last 2, and then the order of the two 3’s will change, so it is an unstable algorithm.

How does insert sort compare to bubble sort? Again, insert sort is a little bit better than bubble sort, O(n^2) in time and O(1) in space, and there are fewer assignments in insert sort than in bubble. When the data is small, the difference is small, but when the data is large, the extra two-step assignment takes a lot of time.

Public account: no dream aqiao background reply “group chat”, study together, progress together