Implementation of Several Common Sorting Algorithms

1. Bubble sort

1. Baidu Encyclopedia

Bubble Sort is a relatively simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, compares two adjacent elements in turn, and swaps them if the order is wrong (e.g., big to small, first letter from Z to A). The work of visiting elements is repeated until no adjacent elements need to be exchanged, that is, the element column has been sorted. The name of this algorithm comes from the fact that the smaller elements will slowly "float" to the top of the sequence (in ascending or descending order) through exchange, just as the bubbles of carbon dioxide in carbonated drinks will eventually float to the top, hence the name "bubbling" Sort".

2.C language implementation

Define two functions separately (sort from small to large)

//Bubbling (after one round of bubbling, the last of the array is the maximum value)
void Bubble(int arr[], int n){
    for(int i = 0; i < n-1; i++){
        int temp;
        if(arr[i] > arr[i+1]){
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//Bubble Sort
void bubbleSorrt(int arr[], int n){
    for(int i = n; i > 0; i--){
        Bubble(arr, i);
    }

for loop nested implementation

//Bubble Sort
void bubbleSorrt(int arr[], int n){
    for(int i = 0; i < n-1; i++)//Control the number of rounds of bubbling
    {
        for(int j = 0; j < n-1-i; j++)//Controls the number of times each round of bubbling array element swaps
        {
            int temp;
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Example

#include <stdio.h>

//Bubbling (after one round of bubbling, the last of the array is the maximum value)
void Bubble(int arr[], int n){
    for(int i = 0; i < n-1; i++){
        int temp;
        if(arr[i] > arr[i+1]){
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//Bubble Sort
void bubbleSorrt(int arr[], int n){
    // for(int i = n; i > 0; i--){
    //     Bubble(arr, i);
    // }
    for(int i = 0; i < n-1; i++)//Control the number of rounds of bubbling
    {
        for(int j = 0; j < n-1-i; j++)//Control the number of bubbling in each round, minus one for each round
        {
            int temp;
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main(){
    int arr[7] = {6, 7, 5, 8, 4, 2, 9};
    bubbleSorrt(arr, 7);
    for(int i = 0; i < 7; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Second, the selection sort

1. Baidu Encyclopedia

Selection sort is a simple and intuitive sorting algorithm. Its working principle is: first select the smallest (or largest) element from the data elements to be sorted, store it at the beginning of the sequence, and then find the smallest (largest) element from the remaining unsorted elements elements, and then placed at the end of the sorted sequence. And so on, until the number of all data elements to be sorted is zero. Selection sort is an unstable sorting method.

2. Diagram

Red is the current minimum value, yellow is the sorted sequence, and blue is the current position.

3.C language implementation

define two functions

//Find the position of the largest value (sort from small to large)
int findMaxPos(int arr[], int n){
    int Max_pos = 0;
    int max = arr[Max_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] > max){
            max = arr[i];
            Max_pos = i;
        }
    }
    return Max_pos;
}
//Find the position of the smallest value (sort from largest to smallest)
int findMinPos(int arr[], int n){
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] < min){
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//selection sort
void selectionSort(int arr[], int n){
    for(int i = n; i > 0; i--){
        int pos = findMinPos(arr, i);//i represents the size of this array
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//Swap the maximum value with the last term
    }
}

Example

#include <stdio.h>

//Find the position of the smallest value (sort from largest to smallest)
int findMinPos(int arr[], int n){
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] < min){
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//selection sort
void selectionSort(int arr[], int n){
    for(int i = n; i > 0; i--){
        int pos = findMinPos(arr, i);//To change the sort order just change the function name
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//Swap the largest (smaller) value with the last item
    }
}

int main(){
    int arr[8] = {6, 7, 10, 11, 4, 11, 9, 7};
    selectionSort(arr, 8);
    for(int i = 0; i < 8; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

3. Insertion sort

1. Wikipedia

Insertion Sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence, and for unsorted data, scans backwards and forwards in the sorted sequence, finds the corresponding position and inserts it. In terms of implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space), so in the process of scanning from the back to the front, it is necessary to repeatedly move the sorted elements backward step by step. , to provide insertion space for the newest element.

2. Diagram

3. Code implementation

//Insertion sort
void insertionSort(int arr[], int len){
    for(int i = 1; i < len; i++){
        int pos = i;//pos represents the position of the element to be inserted
        int key = arr[pos];//The key represents the element to be inserted, and the entire insertion process will not change
        while(arr[pos-1] > key && pos > 0){
            arr[pos] = arr[pos-1];
            pos--;//Move the position forward one bit to continue the comparison
        }
        arr[pos] = key;//Continue to save the element to be inserted at the pos position
    }
}

Example

#include <stdio.h>

//Insertion sort
void insertionSort(int arr[], int len){
    for(int i = 1; i < len; i++){
        int pos = i;//pos represents the position of the element to be inserted
        int key = arr[pos];//key indicates the element to be inserted
        while(arr[pos-1] > key && pos > 0){
            arr[pos] = arr[pos-1];
            pos--;//Move the position forward one bit to continue the comparison
        }
        arr[pos] = key;//Continue to save the element to be inserted at the pos position
    }
}

int main(){
    int arr[12] = {6, 7, 10, 11, 4, 11, 9, 7, 3, 1, 8, 0};
    insertionSort(arr, 12);
    for(int i = 0; i < 12; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}