Summary of various sorting algorithms

Sorting algorithms are the most basic and commonly used algorithms. Different sorting algorithms will have different performances in different scenarios or applications. We need to be proficient in various sorting algorithms to apply them in practice and to better play their advantages. Today, let's summarize various sorting algorithms.

The following table summarizes the complexity and stability of various sorting algorithms:

Comparison of the complexity of various sorting algorithms.png

Bubble Sort

Bubble sort is the most classic sorting algorithm. It is a comparison-based sorting algorithm with a time complexity of O(n^2). Its advantages are simple implementation and better performance when n is small.

• Algorithm principle: Adjacent data are compared in pairs, with small numbers placed in front and large numbers placed in the back. After one round, the smallest number is ranked first, and the second round is the same, and so on, until all the data is sorted.

• C++ code implementation

 void bubble_sort( int arr[], int len)
 {
 for ( int i = 0 ; i < len - 1 ; i++)
 {
 for ( int j = len - 1 ; j >= i; j--)
 {
 if (arr[j] < arr[j - 1 ])
 {
 int temp = arr[j];
                  arr[j] = arr[j - 1 ];
                  arr[j - 1 ] = temp;
 }
 }
 }
 }

Selection Sort

• The algorithm works by first finding the smallest (largest) element in the unsorted sequence and storing it at the beginning of the sorted sequence. Then, continue to find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence. This process continues until all elements are sorted.

• C++ code implementation

 void select_sort( int arr[], int len)
 {
 for ( int i = 0 ; i < len; i++)
 {
 int index = i;
 for ( int j = i + 1 ; j < len; j++)
 {
 if (arr[j] < arr[index])
 index = j;
 }
 if (index != i)
 {
 int temp = arr[i];
              arr[i] = arr[index];
              arr[index] = temp;
 }
 }
 }

Insertion Sort

• The algorithm principle divides the data into two parts, the ordered part and the unordered part. At the beginning, the ordered part contains the first element, and the unordered elements are inserted into the ordered part in sequence until all elements are in order. Insertion sort is divided into direct insertion sort, binary insertion sort, linked list insertion, etc. Here we only discuss direct insertion sort. It is a stable sorting algorithm with a time complexity of O(n^2)

• C++ code implementation

 void insert_sort( int arr[], int len)
 {
 for ( int i = 1 ; i < len; i ++)
 {
 int j = i - 1 ;
 int k = arr[i];
 while (j > - 1 && k < arr[j] )
 {
              arr[j + 1 ] = arr[j];
 j --;
 }
 arr[j + 1 ] = k;
 }
 }

Quick Sort

• Algorithm principle Quick sort is a very efficient sorting algorithm in practice. It is not a stable sorting algorithm. The average time complexity is O(nlogn) and the complexity is O(n^2) in the worst case. Its basic idea is to divide the data to be sorted into two independent parts through a sorting process, where all the data in one part is smaller than all the data in the other part. Then, the two parts of data are quickly sorted separately according to this method. The whole sorting process can be performed recursively to turn the whole data into an ordered sequence.

• C++ code implementation

 void quick_sort( int arr[], int left, int right)
 {
 if (left < right)
 {
 int i = left, j = right, target = arr[left];
 while (i < j)
 {
 while (i < j && arr[j] > target)
 j--;
 if (i < j)
              arr[i++] = arr[j]; 
 
 while (i < j && arr[i] < target)
 i++;
 if (i < j)
              arr[j] = arr[i];
 }
 arr[i] = target;
      quick_sort(arr, left, i - 1 );
      quick_sort(arr, i + 1 , right);
 }
 }

Merge Sort

• Algorithm principle The specific working principle of merge sort is as follows (assuming that the sequence has a total of n elements):

  • Merge every two adjacent numbers in the sequence to form floor(n/2) sequences. After sorting, each sequence contains two elements.
  • Merge the above sequences again to form floor(n/4) sequences, each containing four elements

  • Repeat step 2 until all elements are sorted.

    Merge sort is a stable sorting algorithm with a time complexity of O(nlogn). If a linked list is used, the space complexity can reach O(1). However, if an array is used to store data, temporary space is required to store the merged data during the merging process, so the space complexity is O(n).

• C++ code implementation

 void merge( int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
 {
 int i = start_index, j = mid_index + 1 ;
 int k = 0 ;
 while (i < mid_index + 1 && j < end_index + 1 )
 {
 if (arr[i] > arr[j])
             temp_arr[k++] = arr[j++];
 else  
             temp_arr[k++] = arr[i++];
 }
 while (i < mid_index + 1 )
 {
         temp_arr[k++] = arr[i++];
 }
 while (j < end_index + 1 )
         temp_arr[k++] = arr[j++]; 
 
 for (i = 0 , j = start_index; j < end_index + 1 ; i ++, j ++)
         arr[j] = temp_arr[i];
 } 
 
 void merge_sort( int arr[], int temp_arr[], int start_index, int end_index)
 {
 if (start_index < end_index)
 {
 int mid_index = (start_index + end_index) / 2 ;
         merge_sort(arr, temp_arr, start_index, mid_index);
         merge_sort(arr, temp_arr, mid_index + 1 , end_index);
         merge(arr, temp_arr, start_index, mid_index, end_index);
 }
 }

Heap Sort

Binary Heap

A binary heap is a complete binary tree or an approximately complete binary tree that satisfies two properties.

• The key value of the parent node is always greater than or equal to (less than or equal to) the key value of any child node
• The left subtree and right subtree of each node are a binary heap

When the key value of the parent node is always greater than or equal to the key value of any child node, it is a maximum heap. When the key value of the parent node is always less than or equal to the key value of any child node, it is a minimum heap. Generally, a binary tree is simply called a heap.

Heap storage

Generally, an array is used to store a heap. The parent node of node i has a subscript of (i – 1) / 2. The subscripts of its left and right child nodes are 2 * i + 1 and 2 * i + 2 respectively. For example, the subscripts of the left and right child nodes of node 0 are 1 and 2 respectively. The storage structure is shown in the figure:

Heap structure.png

Heap sort principle

The time complexity of heap sort is O(nlogn)

• Algorithm principle (taking *** heap as an example)

  • First, build the initial data R[1..n] into a *** heap, which is the initial unordered area
  • Then swap the record R[1] (i.e. the top of the heap) with the last record R[n] in the unordered area, thus obtaining a new unordered area R[1..n-1] and an ordered area R[n], and satisfying R[1..n-1].keys≤R[n].key
  • Since the new root R[1] after the swap may violate the heap property, the current unordered area R[1..n-1] should be adjusted to a heap.
  • Repeat steps 2 and 3 until there is only one element in the unordered region.

• C++ code implementation

 /**
 * Build a large root heap from array arr
 * @param arr the array to be adjusted
 * @param i The subscript of the array element to be adjusted
 * @param len the length of the array
 */  
 void heap_adjust( int arr[], int i, int len)
 {
 int child;
 int temp; 
 
 for (; 2 * i + 1 < len; i = child)
 {
 child = 2 * i + 1 ; // child node position = 2 * parent node position + 1  
 // Get the node with the larger key value among the child nodes  
 if (child < len - 1 && arr[child + 1 ] > arr[child])
 child++;
 // If the larger child node is larger than the parent node, move the larger child node up and replace its parent node  
 if (arr[i] < arr[child])
 {
 temp = arr[i];
            arr[i] = arr[child];
            arr[child] = temp;
 }
 else  
 break ;
 }
 } 
 
 /**
 * Heap sort algorithm
 */  
 void heap_sort( int arr[], int len)
 {
 int i;
 // Adjust the first half of the sequence so that the last element is the last element in the sequence  
 for ( int i = len / 2 - 1 ; i >= 0 ; i--)
 {
        heap_adjust(arr, i, len);
 } 
 
 for (i = len - 1 ; i > 0 ; i--)
 {
 // Swap the first element with the last element to ensure that the last element in the current sequence is the first one  
 int temp = arr[ 0 ];
 arr[ 0 ] = arr[i];
 arr[i] = temp;
 // Keep reducing the range of the heap, and ensure that the first element is the maximum value of the current sequence after each adjustment  
        heap_adjust(arr, 0 , i);
 }
 }