C language implements selection sort direct insertion sort bubble sort examples

Selection sort
Selection sort is a simple and intuitive sorting algorithm. Its core idea is to iterate through groups of Numbers, find the smallest element in the unsorted sequence, and put it at the end of the sorted sequence.

Time complexity: O(n^2)

Stability: instability

 /*
 * @brief  selection sort
 */
 void
 selection_sort(int a[], int n)
 {
   int i, j, min, tmp;
   
   for (i = 0; i < n - 1; ++i) {
     min = i;
     for (j = i+1; j < n; ++j) {
       if (a[j] < a[min]) {
         min = j;
       }
     }
     if (min != i) {
       tmp = a[min];
       a[min] = a[i];
       a[i] = tmp;  
     }        
   }
 }

Direct insertion sort
Direct insertion sort is a kind of sorting algorithm that is easy to understand. Its core idea is to go through groups of Numbers and insert the elements in the array into the sorted sequence one by one.

Time complexity: O(n^2)

Stability: stability

Implementation:

 /* @brief insetion sort
 * insert the new element to the sorted subarray
 */
 void
 insertion_sort(int a[], int n)
 {
   int i, j, num;
 
   for (i = 1; i < n; ++i) {
     num = a[i];
     for (j = i - 1; j >= 0 && a[j] > num; --j)
       a[j+1] = a[j];
     a[j+1] = num;
   }
 }

Bubble sort
Bubble sort is one of the most basic sorting algorithms. Its core idea is to traverse groups from the back to the front, comparing a[i] and a[i-1]. If a[i] is smaller than a[i-1], then the two are exchanged. After one iteration, the smallest element is at the front of the array, and subarrays other than the smallest element are traversed. After the n traversal (the number of elements in the n array), the order is completed. The outer cycle is n times, and the inner cycle is n-1, n-2... 1 times.

Time complexity: O(n^2)

Stability: stability

Implementation:

 /* @brief  bubble sort
 * move the smallest element to the front in every single loop
 */
 void
 bubble_sort(int a[], int n)
 {
   int i, j, tmp;
 
   for (i = 0; i < n; ++i) {
     for (j = n - 1; j > i; --j) {
       if (a[j] < a[j-1]) {
         tmp = a[j];
         a[j] = a[j-1];
         a[j-1] = tmp;
       }
     }
   }
 }