C language sorting algorithm

1. Bubble sorting

Bubble Sort is A simple sort algorithm. It repeatedly visits the sequence to be sorted, compares two elements at A time, and exchanges them if their order (e.g. from large to small and from A to Z) is wrong.

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

2. Select sort

Selection sort is a simple and intuitive sorting algorithm. Its working principle is as follows. First, find the smallest (large) element in the unordered sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unordered elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.

void selection_sort(int a[], int len) 
{
    int i,j,temp;
 
    for (i = 0 ; i < len - 1 ; i++) 
    {
        int min = i;                  // Record the minimum value. The first element is the minimum by default
        for (j = i + 1; j < len; j++)     // Access unsorted elements
        {
            if (a[j] < a[min])    // Find current minimum
            {
                min = j;    // Record minimum
            }
        }
        if(min != i)
        {
            temp=a[min];  // Swap two variables
            a[min]=a[i];
            a[i]=temp;
        }
        /* swap(&a[min], &a[i]);  */   // Use custom function exchange
    }
}
 
/*
void swap(int *a,int *b) // Swap two variables
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
*/

3. Insert sort

Insertion Sort (English: Insertion Sort) is a simple and intuitive sorting algorithm. Its working principle is to build an ordered sequence, scan the unordered data from back to front in the sorted sequence, find the corresponding position and insert it. In the implementation of Insertion Sort, in place sort is usually adopted (that is, the sort that only needs the additional space of {\ displaystyle O(1)} {\displaystyle O(1)}). Therefore, in the process of scanning from back to front, the sorted elements need to be moved back step by step to provide insertion space for the latest elements.

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

4. Hill sort

Hill sort, also known as decreasing incremental sort algorithm, is a more efficient improved version of insertion sort. Hill sorting is an unstable sorting algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

• Insertion sorting is efficient when operating on almost ordered data, that is, it can achieve the efficiency of linear sorting
• But insert sort is generally inefficient, because insert sort can only move data one bit at a time

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

5. Merge sort

Divide the data into two segments, select the smallest element one by one from the two segments and move it to the end of the new data segment.

It can be carried out from top to bottom or from bottom to top.

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

6. Quick sort

Randomly select an element in the interval as the benchmark, put the element less than the benchmark before the benchmark, and the element greater than the benchmark after the benchmark, and then sort the decimal area and large number area respectively.

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}