foreword

As mentioned above, let's brush the sorting algorithm next, and naturally we have to look at the current top ten sorting algorithms. I plan to go through it all to understand the idea, and then use the code to implement it to deepen the impression. It is only for my own learning accumulation. I also make my own backup when I write it here, and I can come and see it occasionally~~

There is a lot of information and explanations about these ten classic sorting algorithms on the Internet, so I will not repeat the explanations. Here I only put some of my own understanding. Some materials are also sourced from the Internet. After all, there is no need to recreate the wheel. If there is any infringement, please let me know and delete it~

Top 10 Classic Sorting Algorithms Description

The so-called sorting is the operation of arranging a set of sequences in ascending or descending order according to the size of the numbers. So far, there have been 10 classic sorting algorithms, which will be introduced one by one next. As shown below (picture source network):

Glossary:

• Time complexity: qualitatively describe the time it takes to execute an algorithm; (importance > space complexity, priority)
• Space complexity: qualitatively describe the size of memory required to execute an algorithm;
• n: data size/number;
• k: the number of "buckets";
• In-place: occupies constant memory and does not occupy additional memory;
• Out-place: takes up extra memory
• Stable: After sorting, the sequence position of the same elements is not changed;
• Unstable: After sorting, the order of the same elements will be changed.

Top 10 Classic Sorting Algorithms

At present, there are three main classifications: one is classified according to whether it occupies additional memory; the other is classified according to whether it is stable; the last one is classified according to whether the comparison between numbers and numbers is performed; I personally think the last one is comparison Correct classification, easy to understand and remember.

The first two categories have been introduced in the above figure. The last classification method is put below (picture source network):

Let's start to go through each sorting algorithm one by one, and learn how great the ideas of predecessors are. One sorting can think of so many methods and ideas.

Note: The following sorting algorithms are introduced in ascending order.

1. Bubble sort

1.1 Introduction to the algorithm

The classic sorting algorithm compares the size of two numbers in a loop, and if the former is greater than the latter, it is exchanged, otherwise it remains unchanged. The algorithm's name also comes from the fact that smaller elements gradually "bubble" to the front of the sequence through swapping.

There is also an optimization algorithm for bubble sorting, which is to set a flag to record in a traversal comparison, whether an element exchange occurs, if no exchange occurs, it means that the sequence is in order, and the traversal can be terminated in advance to improve performance.

One of the most commonly used sorting by individuals is simple to implement, easy to remember, and can be done with a few lines of code.

1.2 Algorithm steps

1. Compare two adjacent elements, and if the former is greater than the latter, swap;
2. Repeat step 1 up to n^2 times to complete the sorting.

1.3 Algorithm performance indicators

Average complexity:	O(n^2)
Space complexity:	O(1)
stability:	Stablize

1.4 Code Implementation

main.cpp

#include <iostream>

#include "../include/bubble_sort.h"

using namespace std;

/*
    function description:
        printf a array before or after sort
    parameter:
        @is_before_sort : array type,  true for array before sort, false for array after sort
        @array          : data after bubble sort
        @size           : size of data_before_sort
    return Value:
        void
*/
void printf_sort_array(bool is_array_before_sort, const int* array, ssize_t size)
{
    if(NULL == array || size <= 0)
        return;
    
    if(true == is_array_before_sort)
        cout << "array_before_sort: "<< endl;
    else
        cout << "array_after_sort: "<< endl;

    ssize_t i;
    for( i = 0; i < size; i++ )
    {
        cout << " " << array[i];
        if(i == size - 1)
            cout << endl << endl;
    }
}

int main(void) 
{
    /* sequence before sorting */
    int array[] = {
        3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48
    };
    
    ssize_t len_of_array = sizeof(array) / sizeof(int);
    
    /* printf array before sort */
    printf_sort_array(true, array, len_of_array);

    /* sorting */
    bubble_sort(array, len_of_array);

    /* printf array after sort */
    printf_sort_array(false, array, len_of_array);
    return 0;
}

bubble_sort.cpp

#include "../include/bubble_sort.h"

using namespace std;

/*
    function description:
        bubble sort
    parameter:
        @array : data need to be sorted
        @size  : size of data_before_sort
    return Value:
        void
*/
void bubble_sort(int* array, ssize_t size)
{
    if(NULL == array || size <= 0)
         return;
    
    ssize_t i,j;
    ssize_t cycle_num = 0;

    int temp;
    bool flag_to_terminate = true; //flag to optimize bubble sort

    cout<< "Bubble sorting(optimized)..." << endl << endl;

    //The core of the bubble algorithm: exchange one by one
    for(i = 0; i < size - 1; i++)
    {
        flag_to_terminate = true;
        for(j = 0; j < size - 1; j++)
        {
            if(array[j] > array[j + 1])   
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag_to_terminate = false;
            }
            cycle_num++;
        }
        if(flag_to_terminate)
            break;
    }

    cout << "cycle_num: " << cycle_num << endl;
}

bubble_sort.h

#ifndef __BUBBLE_SORT_H
#define __BUBBLE_SORT_H

#include <iostream>
void bubble_sort(int* array, ssize_t size);

#endif // __BUBBLE_SORT_H

1.5 Code running results: