Since learning to call the sort function of C++ directly, I write less and less sort code. Therefore, this article is written to summarize several common sorting algorithms.

In this article, we will see the following sort：

  • 🏌🏻Bubble Sort
  • 🪂Insertion Sort
  • 🐧Merge Sort
  • 🦴Quick Sort

Bubble Sort

Time compesity O(n2)

General Ideas

Bubble sorting is one of the earliest sorting algorithms I came into contact with. Its main ideas are as follows:

  • A bubble compares all the elements in the sequence from the beginning to the end, and puts the largest one at the end.

  • All elements in the remaining sequence are compared again, with the largest at the end.

  • Repeat step 2.

Code Implementation（C）

1
2
3
4
5
6
7
8
9
10
11
12
13
void Bubble_sort(int arr[], int size)
{
  for(int i=0; i<size-1; i++)
    for(int j=0; j<size-i-1; j++)
    {
      if(arr[j] > arr[j+1])
      {
        int tmp = arr[j];
        arr[j] = arr[j+1];
        a[j+1] = tmp;
      }
    }
}

Insertion Sort

Time compesity O(n2)

General Ideas

  • In a group of numbers to be sorted, assume that the first n-1 （n > = 2）numbers are already in order.
  • Insert the nth number into the previous ordinal number, so that the N numbers are also in order.
  • Repeat this until all are in order.

Code Implementation (C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Insertion_Sort(int arr[], int size)
{
    int j, P;
    
    int tmp;
    for(P=1; P<N; P++)
    {
        tmp = arr[P];
      	/* 若待插入的数前面有比他大的数，就交换 */
        for(j=P; j>0 && arr[j-1]>Tmp; j--)
            arr[j] = arr[j-1];
        arr[j] = Tmp; // 插入
    }
}

Merge Sort

General Ideas

Merge sort is a sort method based on the idea of merge. The algorithm adopts the classic divide and conquer strategy .

  • Divides the problem into some small problems.
  • Recursively solves the small problems,
  • “Repairs” the answers obtained in different stages.

merge_sort

merge_sort1

merge_sort2

Code Implementation (C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)
{
    int Center;
    
    if(Left < Right)
    {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center+1, Right);
        Merge(A, TmpArray, Left, Center+1, Right);
    }
}

void Mergesort(ElementType A[], int N)
{
    ElementType *TmpArray;
    
    TmpArray = malloc(N * sizeof(ElementType));
    if(TmpArray != NULL)
    {
        Msort(A, TmpArray, 0, N-1);
        free(TmpArray);
    }
    else
        FatalError("No space for tmp array!!!");
}

/* Lpos = start of left half, Rpos = start of right half */
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
    int i, LeftEnd, NumElements, TmpPos;
    
    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;
    
    /* main loop */
    while(Lpos <= LeftEnd && Rpos <= RightEnd)
        if(A[Lpos] <= A[Rpos])
            TmpArray[TmpPos++] = A[Lpos++];
    	else
            TmpArray[TmpPos++] = A[Rpos++];
    
    while(Lpos <= LeftEnd) /* Copy rest of first half */
        TmpArray[TmpPos++] = A[Lpos++];
    while(Rpos <= RightEnd) /* Copy rest of second half */
        TmpArray[TmpPos++] = A[Rpos++];
    
    /* Copy TmpArray back */
    for(i=0; i<NumElements; i++, RightEnd--)
        A[RightEnd] = TmpArray[RightEnd];
}

Quick Sort

General Ideas

quick_sort

  • Base on 6.
  • Use two sentries, one from right to left to find the first number smaller than 6, the other from left to right to find the first number larger than 6.
  • Swap the two number. You have to look from right to left first.
  • Repeat step 2 and step 3 until they meet each other.
  • Swap the meet number and 6.

Code Implementation (C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void Quicksort(ElementType A[], int N)
{
    Qsort(A, 0, N-1);
}

/* Return median of Left, Center, and Right */
/* Order these and hide the pivot */
ElementType Median3(ElementType A[], int Left, int Right)
{
    int Center = (Left + Right) / 2;
    
    if(A[Left] > A[Center])
        Swap(&A[Left], &A[Center]);
    if(A[Left] > A[Right])
        Swap(&A[Left], &A[Right]);
    if(A[Center] > A[Right])
        Swap(&A[Center], &A[Right]);
    
    /* Invariant: A[Left] <= A[Center] <= A[Right] */
    Swap(&A[Center], &A[Right-1]);	/* Hide pivot */
    return A[Right--1];	/* Return pivot */
}

#define Cutoff (3)
void Qsort(ElementType A[], int Left, int Right)
{
    int i, j;
    ElementType Pivot;
    
    if(Left + Cutoff <= Right)
    {
        Pivot = Median3(A, Left, Right);
        i = Left;
        j = Right - 1;
        for(;;)
        {
            while(A[++i] < Pivot){}
            while(A[--j] > Pivot){} 
            if(i < j)
                Swap(&A[i], &A[j]);
            else
                break;
        }
        Swap(&A[i], &A[Right-1]); /* Restore pivot */
        
        Qsort(A, Left, i-1);
        Qsort(A, i+1, Right);
    }
    else /* Do an insertion sort on the subarray */
        InsertionSort(A+Left, Right-Left+1);
}