DataslopeBasic Sorting Algorithms
Learn bubble sort, selection sort, insertion sort, stability, and loop invariants in C++
Sorting rearranges data into an order, usually ascending or descending. These algorithms are not the fastest for large inputs, but they teach loop invariants and the structure of comparison-based sorting.
Why study slow sorts?
Basic sorts make hidden ideas visible: sorted prefixes and suffixes grow, comparisons decide order, and swaps or shifts move elements into place. These ideas reappear in efficient sorting and interview problems.
Bubble sort
Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order. After one full pass, the largest value has bubbled to the end.
With an early-exit flag, bubble sort is O(n) on already sorted input. Its average and worst cases are O(n^2).
Selection sort
Selection sort finds the smallest element in the unsorted suffix and swaps it into the next position. The sorted prefix grows by one each pass.
Selection sort always does O(n^2) comparisons, even if the input is already sorted, and uses O(1) extra space.
Insertion sort
Insertion sort builds a sorted prefix. For each new value, it shifts larger elements right until the correct position opens.
Insertion sort is O(n^2) in the worst case, but O(n) on nearly sorted data. Many hybrid sorts use it for tiny partitions.
Stability
A stable sort keeps equal elements in their original relative order. Insertion sort is stable when it shifts only values greater than the key. Selection sort is not stable in its typical swap-based form.
Comparing basic sorts
| Algorithm | Best | Average | Worst | Extra space | Stable? |
|---|---|---|---|---|---|
| Bubble sort with early exit | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
A helper that prints vectors cleanly is useful while debugging sorts.
Insertion sort's invariant is: before each outer-loop iteration, elements before i are already sorted.
Practice: bubble sort with early exit
Implement void bubbleSort(std::vector<int>& v) using adjacent swaps and an early-exit flag. The driver prints the sorted vector with comma separators.
Practice: insertion sort
Implement void insertionSort(std::vector<int>& v). The driver prints the sorted result with comma separators.
Check your understanding
Which basic sort can run in O(n) on already sorted input with an early-exit flag?
Bubble sort
Selection sort
Merge sort
Quicksort
What does it mean for a sorting algorithm to be stable?
It never uses extra memory.
It always runs in O(n log n).
Equal elements keep their original relative order.
It never swaps elements.
Which algorithm repeatedly selects the minimum element from the unsorted suffix and swaps it to the front?
Bubble sort
Selection sort
Insertion sort
Binary search