# Implementation and idea of common sorting algorithms

## Insert sort

### Direct insertion

- basic thought

Direct insertion sort is a simple insertion sort method. Its basic idea is:

Insert the records to be sorted into an ordered sequence one by one according to the size of their key values, until all records are inserted, and a new ordered sequence is obtained.

- Direct insert sort

When inserting the I (I > = 1) th element, the preceding array[0],array[1],..., array[i-1] have been arranged in order. At this time, compare the sorting code of array[i] with the sorting code of array[i-1],array[i-2],... To find the insertion position, that is, insert array[i], and move the element order at the original position backward

Insert sort – sort from front to back

//Insert sort -- sort from front to back void InsertSort1(int* a, int n) { for (int i = 1; i < n; i++) { int k = 0; while (a[i] > a[k]) { k++; } int temp = a[i]; for (int j = i; j >k; j--) { a[j] = a[j - 1]; } a[k] = temp; } }

Moving data from front to back wastes time and increases sorting time

Insert sort – sort from back to front

//Insert sort -- back to front void InsertSort2(int* a, int n) { for (int i = 1; i < n; i++) { int j = i; while (j > 0 && a[j] < a[j-1]) { swap(&a[j], &a[j-1]); j--; } } }

Compared with the previous version, there is no more data movement, which shortens the sorting time. Here, the time is mainly wasted on the exchange function

//Insert sort -- back to front void InsertSort2(int* a, int n) { for (int i = 1; i < n; i++) { int j = i; while (j > 0 && a[j] < a[j - 1]) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; j--; } } }

Here, the time has been shortened after changing the swap, but it is not too obvious.

//Insert sort – back to front – do not call swap function

void InsertSort3(int* a, int n) { for (int i = 1; i < n; i++) { int j = i; int temp = a[i]; while (j > 0 && temp < a[j-1]) { a[j] = a[j - 1]; j--; } a[j] = temp; } }

### Split search sort

//Half insert void BinInsertSort(int *a,int n) { for (int i = 1; i < n; i++) { //Binary search location int left = 0; int right = i-1; int tem = a[i]; while (left<=right) { int mid = (left + right) / 2; if (tem > a[mid]) { left = mid + 1; } else { right = mid - 1; } } for (int j = i; j > right; j--) { a[j] = a[j - 1]; } a[left] = tem; } }

### Two way sorting

void TwoInsertSort(int* a, int n) { //Open up temporary space int *temp = new int[n]; temp[0] = a[0]; int first=0, end = 0; for (int i = 1; i < n; i++) { //Insert a number smaller than temp[first] in front of him if (a[i] < temp[first]) { first = (first - 1 + n) % n; temp[first] = a[i]; } //A number larger than temp[end] is inserted behind him else if (a[i] > temp[end]) { end++; temp[end] = a[i]; } //A number smaller than temp[first] and a number larger than temp[end] move back from temp[end] until a smaller number is found, and then insert it behind him else { int final = end; while (temp[final] > a[i]) { temp[(final + 1) % n] = temp[final]; final=(final-1+n)%n; } temp[(final + 1)%n] = a[i]; end++; } } int k = 0; for (int i = first; k < n; k++) { a[k] = temp[i]; i = (i + 1) % n; } free(temp); }

Open up an array with the same size as the array. You can regard it as the first connected array, which can be achieved by taking modules

temp[0]=a[0] of de sorted array

Take a[1] and compare it with temp[first] and temp[end] respectively. Insert the number smaller than temp[first] into his front, the number larger than temp[end] into his back, the number smaller than temp[first], and the number larger than temp[end] from temp[end] to find the number smaller than him, and then insert it into his back

## Shell Sort

Basic idea: first select an integer, divide all records in the file to be sorted into groups, divide all records with distance into the same group, and sort the records in each group. Then, take and repeat the above grouping and sorting. When arrival = 1, all records are arranged in a unified group. Pre sort first and insert sort directly. We divide a group of data into several groups with gap as the spacing, and then sort within the group. Gap generally selects the group leader first, and then takes half of the group for intra group sorting. When gap is 1, it is directly inserted for sorting.

//Single Hill sort void shellsort(int* a, int n,int gap) { for (int i = 0; i < n-gap; i++) { int end = i; int temp = a[end+gap]; while (end >=0 ) { if (temp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end+gap] = temp; } } //Shell Sort void ShellSort(int* a, int n) { int s[4] = { 5,2,1 }; for (int i = 0; i <3; i++) { shellsort(a, n, s[i]); } }

- Hill sort is an optimization of direct insertion sort.
- When gap > 1, the array is pre sorted in order to make the array closer to order. When gap == 1, the array is close to ordered, which will be very fast. In this way, the optimization effect can be achieved as a whole. We can compare the performance test after implementation.
- The time complexity of Hill sort is not easy to calculate, because there are many gap value methods, which makes it difficult to calculate. Therefore, the time complexity of Hill sort given in many trees is not fixed

## Select sort

Basic idea:

Each time, the smallest (or largest) element is selected from the data elements to be sorted and stored at the beginning of the sequence until all the data elements to be sorted are arranged.

### Direct selection sort

- Select the data element with the largest (smallest) key in the element set array[i] – array[n-1]
- If it is not the last (first) element in the group, it is exchanged with the last (first) element in the group
- In the remaining array[i] – array[n-2] (array[i+1] – array[n-1]) set, repeat the above steps until there is 1 element left in the set

An example is given below:

Take the first subscript of the array as I, find the smallest number in the n array, and then exchange it with array[i], so that the smallest number is in front of the array.

Then i + +, move to the smallest number in the back of the array and do the same thing as the front until i==n.

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Select Sort directly -- find the subscript of the smallest decimal int selectsort(int* a, int n,int gap) { int temp = a[gap]; int min = gap; for (int i = gap+1; i < n; i++) { if (temp > a[i]) { temp = a[i]; min = i; } } return min; } void SelectSort(int* a, int n) { for (int i = 0; i < n; i++) { int min = selectsort(a, n, i); swap(a[i], a[min]); } }

### Heap sort

Basic idea:

Heap sort is a sort algorithm designed by using the data structure of heap tree (heap). It is a kind of selective sort. It selects data through the heap. It should be noted that large piles should be built in ascending order and small piles should be built in descending order.

## Exchange sort

Basic idea: the so-called exchange is to exchange the positions of the two records in the sequence according to the comparison results of the key values of the two records in the sequence. The characteristics of exchange sorting are: move the records with larger key values to the tail of the sequence and the records with smaller key values to the front of the sequence.

### Bubble sorting

// Bubble sorting void BubbleSort(int* a, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i;j++) { if (a[j+1] < a[j]) { swap(a[j+1], a[j]); } } } }

### Advanced bubble sorting

Take the subscript of the array as j and let temp=a[i]

Let temp and a[j+1] calculate the size. If it is smaller than temp, move forward. If it is larger than temp, temp will copy to its previous item. Then j++

//Improved bubble sorting void BubbleSort1(int* a, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j + 1] < a[j]) { int temp = a[j]; while (j<n - 1 && temp>a[j+1]) { a[j] = a[j + 1]; j++; } a[j] = temp; } } }

//Improved version 2 bubble sorting void BubbleSort2(int* a, int n) { bool tr = false;; for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j + 1] < a[j]) { int temp = a[j]; while (j<n - 1 && temp>a[j + 1]) { a[j] = a[j + 1]; j++; } a[j] = temp; tr = true; } } if (!tr) { break; } else tr = false; } }

Boolean markers are used to detect whether the number of trailing edges is in order. If in order, break directly;

##Quick sort