Top 10 Classic Sorting Algorithms

Sorting algorithms are among the most fundamental algorithms in Data Structures and Algorithms.

Sorting algorithms can be categorized into internal sorting and external sorting. Internal sorting refers to sorting data records within memory, while external sorting refers to sorting data that is too large to fit entirely in memory at once, requiring access to external storage during the sorting process.

Common internal sorting algorithms include insertion sort, shell sort, selection sort, bubble sort, merge sort, quicksort, heap sort, radix sort, etc.

A summarized illustration:

Regarding Time Complexity

Quadratic time complexity (O(n²)) sorts include simple sorting algorithms such as direct insertion, direct selection, and bubble sort.

Linear-logarithmic time complexity (O(nlog₂n)) sorts include quicksort, heap sort, and merge sort.

O(n^(1+§)) sorting, where § is a constant between 0 and 1, applies to shell sort.

Linear time complexity (O(n)) sorts include radix sort, as well as bucket and bin sorting.

Regarding Stability

Stable sorting algorithms: bubble sort, insertion sort, merge sort, and radix sort.

Unstable sorting algorithms: selection sort, quicksort, shell sort, and heap sort.

Terminology:

n: Size of the dataset
k: Number of “buckets”
In-place: Uses constant memory, no additional memory needed
Out-place: Requires additional memory
Stability: After sorting, two equal key values remain in the same order as they were before sorting.

Bubble Sort

C Language:

void bubble_sort(int a[], int n) 
{
    for(int i = n; i > 0; i--) 
    {
        for(int j = 0; j < i - 1; j++) 
        {
            if(a[j] < a[j + 1]) 
            {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

Python:

def bubble_sort(lst):
    for i in range(0, len(lst) - 1):
        for j in range(len(lst) - 1):
            if lst[j] > lst[j + 1]:
                temp = lst[j]
                lst[j] = lst[j + 1]
                lst[j + 1] = temp
    return lst

Selection Sort

C Language:

void selection_sort(int a[], int n) 
{
    int min;
    for(int i = 0; i < n - 1; i++) 
    {
        min = i;
        for(int j = i + 1; j < n; j++)
            if(a[j] < a[min]) min = j;
        if(i != min) 
        {
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
    }
}

Python:

def selection_sort(lst):
    for i in range(0, len(lst) - 1):
        min_id = i
        for j in range(i + 1, len(lst) - 1):
            if lst[j] < lst[min_id]:
                min_id = j
        if i != min_id:
            lst[i], lst[min_id] = lst[min_id], lst[i]
    return lst

Insertion Sort

C Language:

void insertion_sort(int a[], int n) 
{
    int key, j;
    for (int i = 1; i < n; i++) 
    {
        key = a[i];
        j = i - 1;
        while (key < a[j] && j >= 0) 
        {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

Python:

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst