Sorting algorithms

Bubble, insertion, selection and library sorting

Sorting is like organizing a bookshelf: arranging books of different heights in order. Different methods have different efficiency:

• Bubble sort: compare two adjacent elements, the larger one "bubbles" backward, time complexity O(n²).
• Selection sort: each round find the minimum value and put it in front, time complexity O(n²).
• Insertion sort: like organizing playing cards, each time insert the new card into its already sorted position, time complexity O(n²).
• Standard library sort: guarantees O(n log n) level comparison count; common implementations use introsort; it cannot be equated with a hand-written quicksort that may degrade.

If the amount of data is small, an O(n²) algorithm can be used; if the amount of data is large, sort must be used.

Stability: only if records with the same key still keep their original relative order after sorting is it called stable. Bubble sort that swaps only on strict inversion, and insertion sort that moves only elements strictly greater than the new value, are stable; ordinary exchange-based selection sort is usually unstable, and std::sort also does not guarantee stability; use stable_sort when needed.

Selection sort finds the minimum value in the unsorted part each round and swaps it with the current position; insertion sort temporarily stores the current position, then shifts right the elements in the sorted part that are greater than it, and finally puts it into the empty slot. Insertion sort can be O(n) on already sorted input, but the worst case is still O(n²).

Selection sort vs insertion sort: the same input

Start with [3, 1, 2]. Selection sort finds and swaps the minimum to produce [1, 3, 2], then [1, 2, 3]. Insertion sort inserts 1 into the sorted prefix, producing [1, 3, 2], then inserts 2 to produce [1, 2, 3]. Matching intermediate arrays do not mean matching comparisons or moves.

Typical selection sort makes n(n−1)/2 key comparisons and at most n−1 swaps. Insertion sort uses n−1 key comparisons on sorted input and can shift n(n−1)/2 values on reverse-sorted input. Swaps and shifts are different measurements.

Sorting traces, comparators and stability

Example 1: Bubble sort (understanding the sorting process)

#include <iostream>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1, 4};
    int n = 5;


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

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

Round 1: 5 and 3 swap → 3,5,8,1,4; 5 and 8 do not swap; 8 and 1 swap → 3,5,1,8,4; 8 and 4 swap → 3,5,1,4,8 (8 sinks to the bottom). After 4 rounds, the result is 1 3 4 5 8.

Example 2: Using sort + a custom comparison function

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1, 4};
    int n = 5;


    sort(a, a + n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl; // 1 3 4 5 8


    sort(a, a + n, greater<int>());
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl; // 8 5 4 3 1

    return 0;
}

sort(first address, last address+1) sorts the array in place. By default ascending; passing greater<int>() gives descending. In contests, prefer sort; it is far faster than bubble sort.

Example 3: Insertion sort preserves the order of equal elements

#include <iostream>
using namespace std;
int main() {
    int a[] = {3, 1, 2, 1};
    for (int i = 1; i < 4; ++i) {
        int value = a[i], j = i - 1;
        while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; --j; }
        a[j + 1] = value;
    }
    for (int x : a) cout << x << " ";
    cout << endl;
}

Output 1 1 2 3. Equal elements are not moved to the right; a new item with the same value is placed after existing items with the same value, thus preserving stability.

Example 4: Selection sort's swaps can break stability

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
    pair<int,char> a[] = {{2,'A'}, {2,'B'}, {1,'C'}};
    for (int i = 0; i < 3; ++i) {
        int best = i;
        for (int j = i + 1; j < 3; ++j) if (a[j].first < a[best].first) best = j;
        swap(a[i], a[best]);
    }
    for (auto x : a) cout << x.first << x.second << " ";
    cout << endl;
}

Output 1C 2B 2A. After swapping 1C with 2A in the first round, 2A, which was originally before 2B, is moved after it, showing instability.

Tips

• Bubble/selection/insertion sort all have time complexity O(n²), and are very slow when n exceeds 10000; when the amount of data is large, be sure to use sort (O(n log n)).
• When using sort to sort structs, write a custom cmp function; note that cmp must return bool and strictly satisfy a "strict weak ordering" (it must not return true when equal).
• In bubble sort, the inner loop should be written as j < n-1-i; omitting -i will perform many useless comparisons.
• Understand the idea of each sorting algorithm: bubble — compare and swap adjacent elements; selection — find the minimum and put it in front; insertion — insert into the existing sequence. Try tracing the sorting process by hand.

Prerequisites

• Array index

Technical references

• Stanford CS106B: sorting

Scope note

This lesson is written by InfoCode and is not an official syllabus; the reference level is a site mapping and does not represent official levels, certification or eligibility. Practice records do not establish mastery or eligibility.

Reference level: GESP Level 4 (site mapping)

See contest pathways