“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
All sorts described below are non-descending by default! See Github for all algorithms and test cases
1. Simple sorting
Simple sorting algorithms mainly include bubble sort, selection sort, insertion sort and hill sort improved from insertion sort, whose time complexity is Nlognlognnlogn
1.1 Bubble sort
Algorithm idea:
The violent solution starts with the first element, pairs the size, and if the latter is less than the former, switches the order of the two, and so on until the largest element “bubbles” to its final position
The code is as follows:
#include <iostream> #include <algorithm> template <typename T> void bubbleSort (T arr[], int n){ for (int i = 0 ; i < n - 1; i++){ for (int j = 0; j < n - 1 - i; j++){ if (arr[j + 1] < arr[j]) std::swap(arr[j + 1],arr[j]); }}}Copy the code1.2 Selection Sort
Algorithm idea:
It’s a violent solution
Each cycle is traversed by selecting and sorting the default first element is the smallest element of the cycle, and then comparing it with the following elements, constantly updating the minimum value of the cycle, and finally exchanging the position of the minimum element and the default initial element, and so on.
The idea is similar to bubbling, except that bubbling sort compares the elements before and after in pairs, whereas selection sort compares the initial element to all subsequent elements.
#include <iostream>
#include <algorithm>
template <typename T>
void selectionSort(T arr[],int n){
int minIndex = 0;
for (int i = 0; i < n - 1; i++){// Swap arr[minIndex] and arr[I] with arr[I]
minIndex = i;
for (int j = i + 1; j < n ; j++){if (arr[j] < arr[minIndex])
minIndex = j;
}
std::swap(arr[minIndex],arr[i]); }}Copy the code1.3 Insertion Sort
Algorithm idea:
Bottom-up subtraction algorithm
Assuming that the first elements of the array are already ordered, the idea of insertion sort is to compare the first unsorted element with the sorted element from back to front. If an element smaller than itself is encountered, the unsorted element is inserted into the place after the element, and so on……
The code is as follows:
#include <iostream>
template <typename T>
void insertionSort(T arr[],int n){
T target = 0;
int j = 0;
for (int i = 1; i < n; i++){ target = arr[i]; j = i -1;
while (j >= 0 && arr[j] > target){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = target; }}Copy the codeIt should be noted that although the average time complexity of insertion sort is O(n2)O(n^2)O(n2), when the array to be sorted is nearly ordered, its time complexity degrades to O(n)O(n)O(n) O(n), The efficiency is no less than any O(nlogn)O(Nlogn)O(Nlogn) advanced sorting algorithm, so insert sort is often used as an optimization sub-process in the advanced sorting algorithm, when the advanced sorting algorithm will sort the array almost in order, the effect of calling insert sort is very good. This optimization idea will be involved in the advanced sorting algorithm below.
1.4 Hill Sort
Algorithm idea:
Hill sort (invented by D.L. Hill) was created by summarizing and magnifying the advantages of insertion sort and can be understood as an improvement on insertion sort.
As we know from the above, insertion sort is quite efficient to sort nearly ordered elements. Hill sort is to insert and sort elements according to the given step size, and then construct nearly ordered array, and continue to insert and sort. Obviously, the step size must end with 1. Therefore, the time complexity of the algorithm depends more precisely on the selection of step size queue. For hill sort, steps 1,4,13,40…… The efficiency is the highest, of course, when using the need to reverse.
The code is as follows:
#include <iostream>
template <typename T>
void shellSort(T arr[],int n){
int h = 1;
T target = 0;
int j = 0;
while (h <= n)
h = 3 * h + 1;
while (h > 0) {// Insert sort with step h
for (inti = h; i < n ; i += h){ target = arr[i]; j = i - h;while (j >= 0 && arr[j] > target){
arr[j + h] = arr[j];
j -= h;
}
arr[j + h] = target;
}
h /= 3; }}Copy the code2 Advanced Sorting
Advanced sort mainly includes merge sort, quick sort and heap sort. The average algorithm complexity is O(nlogn)O(nlogn)O(nlogn) O(nlogn), but the performance of different types of data may be completely different. The application scenarios suitable for different algorithms and the improvement of the algorithm in most cases will be discussed below.
2.1 Merge Sort
Algorithm idea:
Merge sort is a perfect example of divide-and-conquer
For an array A[0…n-1] that needs sorting, merge sort splits them into two: A[0…n / 2] and A[n / 2 + 1], sorts each subarray recursively, and then merges the two sorted subarrays into an ordered array.
First, let’s consider dividing the array into A and B, and make sure that both A and B are ordered. So we’re using the recursive idea of dividing each array into two, knowing that the divided array contains only one element, because we think that once we have only one element, the array is an ordered array. The code for merging is as follows:
template <typename T>
void __mergeSort(T arr[],int l,int r){
// Recursive termination condition
if (l >= r){
return ;
}
int mid = (r + l) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
// Merge after sorting
__merge(arr, l, mid, r);
}
Copy the codeThe logic is simple; the key is to merge two sorted arrays. Unlike other sorting algorithms, we need to introduce an auxiliary array to help us merge.
We will be a new name after the assignment of auxiliary array for aux the second array (pictured above), the original array arr for the first array (pictured above), using a pointer k (subscript index, similarly hereinafter) refers to the first element arr, and respectively using pointer I, j, respectively to two to merge the first element of the array, and then compare the size of the two elements, The smaller element is added to arr[k], then the pointer k moves back, and the pointer to the array being copied moves back. This continues until one of the AUX parts is processed, and then, in the unprocessed array, the remaining elements are copied directly to the end of the ARR. Merge sort code is as follows:
template <typename T>
//l is the index of the first element of the array, mid is the index of the last element of the first array to be merged, and r is the index of the last element of the array
void __merge(T arr[],int l,int mid,int r){
// Declare the auxiliary array aux, note the number of elements (array subscript is closed interval)
T aux[r - l + 1];
// Auxiliary array assignment, note that arr subscripts start at l and aux subscripts start at 0
for (inti = l; i <= r; i++){ aux[i - l] = arr[i]; }// Define the pointer to the first element of the array to be merged
int i = l, j = mid + 1;
for (intk = l; k <= r; k++){// Check whether pointer I crosses mid
// If yes, aux[l...mid] has been merged
if (i > mid){
arr[k] = aux[j - l];
j++;
}else if (j > r){// Check if j crosses r
arr[k] =aux[i - l];
i++;
}else if (aux[i - l] < aux[j - l]){
arr[k] = aux[i - l];
i++;
}else{ arr[k] = aux[j - l]; j++; }}}Copy the codeFinally, we wrap the merges in the same format as above for simple sorting
template <typename T>
void mergeSort(T arr[], int n){
__mergeSort(arr,0,n-1);
}
Copy the code2.1.1 Merge sort performance test
We use the function to automatically generate 100,000 elements in order, and then swap 10 groups of them, so we get a nearly ordered array, for the same sample data, let us use the insertion sort and merge sort sorting test, test results are as follows:
Thus, for nearly ordered arrays (or, more extreme, perfectly ordered arrays), insertion sort outperforms merge sort by a large order of magnitude!
This is because in the near-ordered case, insertion sort degrades to O(n)O(n)O(n), and the sorted elements are no longer sorted. Merge sort is the same as before, even if the elements are ordered, they will be sorted according to the original strategy.
2.1.2 Merge sort optimization
For this, we derive a bit of optimization for merge sort, as follows:
template <typename T>
void __mergeSort(T arr[],int l,int r) {
// Recursive termination condition
// if (l >= r) {
// return ;
// }
// Optimization 2: If r-l<=15(optionally), use insertion sort
if ( r - l <= 15) {
insertionSort(arr,l,r);
return;
}
int mid = (r + l) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
// Merge after sorting
// Optimization 1: If it is nearly ordered, adding this judgment will improve performance
if (arr[mid] > arr[mid + 1])
__merge(arr, l, mid, r);
}
Copy the codeWhere, insert sort code is as follows:
template <typename T>
void insertionSort(T arr[],int l, int r){
T target = 0;
int j = 0;
for (int i = l + 1; i <= r; i++){ target = arr[i]; j = i -1;
while (j >= l && arr[j] > target){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = target; }}Copy the codeThe effect is as follows:
It’s still a little bit slower than insert sort, but it’s a lot faster than merge sort
2.1.3 Bottom-up merge sort algorithm
The merging sort introduced above belongs to the top-down method, that is, starting from the whole, divide the whole into parts, and then combine the parts into the whole. Below we introduce the bottom-up merge sort algorithm, first merge small array, then merge the completed array (length is twice the size of the small array), the legend is as follows:
Bottom-up thinking doesn’t require recursion, just iteration, as follows:
#include <iostream>
#include <algorithm>
template <typename T>
void mergeSortBU(T arr[],int n){
for (int h = 1; h <= n; h += h){// Make sure there are two arrays to merge, not one
for(int i = 0; i + h < n; i += h + h){ __merge(arr,i,i + h -1,std::min(r,i + h + h - 1)); }}}Copy the codeSince it makes less use of the index properties of arrays, bottom-up merge sort can be extended to sort linked lists, with time complexity O(nlogn)O(nlogn)O(nlogn) O(nlogn)