1. The Sorting Problem
Definition – Sorting
Given a list of elements, each with a key from a totally ordered set, produce a permutation of the list whose keys are in ascending (or descending) order.
Example: .
- Complexity of a sorting algorithm = number of comparisons it performs.
- Size of the problem = number of elements .
2. Selection Sort
Principle
At iteration , find the smallest value in tab[i..n-1] and swap it with tab[i].
template <class Elem>
void selectionSort(Elem *tab, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (tab[j] < tab[min]) min = j;
Elem Tmp = tab[i]; tab[i] = tab[min]; tab[min] = Tmp; // swap
}
}Worked example – 42 20 17 13 28 14 23 15
| After pass | Min found | Array (sorted part in bold) |
|---|---|---|
| start | 42 20 17 13 28 14 23 15 | |
| 0 | 13 | 13 20 17 42 28 14 23 15 |
| 1 | 14 | 13 14 17 42 28 20 23 15 |
| 2 | 15 | 13 14 15 42 28 20 23 17 |
| 3 | 17 | 13 14 15 17 28 20 23 42 |
| 4 | 20 | 13 14 15 17 20 28 23 42 |
| 5 | 23 | 13 14 15 17 20 23 28 42 |
| 6 | 28 | 13 14 15 17 20 23 28 42 |
Complexity
Finding the 1st minimum takes comparisons, the 2nd , …, the last :
Same in worst, average and best case. Only swaps (an advantage when swaps are expensive).
3. Bubble Sort
Principle
Compare adjacent pairs from the end of the array and swap if out of order; small elements “bubble up”. After pass , the element at position is in its final place.
template <class Elem>
void BubbleSort(Elem *tab, int n) {
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if (tab[j-1] > tab[j]) {
Elem Tmp = tab[j-1]; tab[j-1] = tab[j]; tab[j] = Tmp;
}
}Worked example – 42 20 17 13 28 14 23 15
| After pass | Array (final positions in bold) |
|---|---|
| start | 42 20 17 13 28 14 23 15 |
| 0 | 13 42 20 17 14 28 15 23 |
| 1 | 13 14 42 20 17 15 28 23 |
| 2 | 13 14 15 42 20 17 23 28 |
| 3 | 13 14 15 17 42 20 23 28 |
| 4 | 13 14 15 17 20 42 23 28 |
| 5 | 13 14 15 17 20 23 42 28 |
| 6 | 13 14 15 17 20 23 28 42 |
Detail of pass 0 ( from 7 down to 1): 23↔15, 28↔14, 17↔13, 20↔13, 42↔13 → 13 has bubbled to the top.
Complexity
Pass makes comparisons:
Same in worst, average and best case.
⚠️ This holds for the slide’s version, which never stops early. Adding a flag “no swap in this pass → stop” makes the best case (already sorted) .
4. Insertion Sort
Principle
The left part tab[0..i-1] is already sorted; insert tab[i] into it, shifting larger elements one place to the right.
template <class Elem>
void insertionSort(Elem *tab, int n) {
for (int i = 1; i < n; i++) {
Elem Tmp = tab[i];
int j = i;
while (j - 1 >= 0 && Tmp < tab[j-1]) { // until insertion position
tab[j] = tab[j-1];
j--;
}
tab[j] = Tmp;
}
}Worked example – 42 20 17 13 28 14 23 15
| Inserted | Array (sorted part in bold) | |
|---|---|---|
| 1 | 20 | 20 42 17 13 28 14 23 15 |
| 2 | 17 | 17 20 42 13 28 14 23 15 |
| 3 | 13 | 13 17 20 42 28 14 23 15 |
| 4 | 28 | 13 17 20 28 42 14 23 15 |
| 5 | 14 | 13 14 17 20 28 42 23 15 |
| 6 | 23 | 13 14 17 20 23 28 42 15 |
| 7 | 15 | 13 14 15 17 20 23 28 42 |
Complexity
| Case | When | Cost |
|---|---|---|
| Worst | each element inserted at the beginning (reverse-sorted input) | |
| Best | each element stays at the end (already sorted) | comparisons → |
| Average |
Comparison of the simple sorts
| Worst | Average | Best | |
|---|---|---|---|
| Selection | |||
| Bubble | |||
| Insertion |
5. Shell Sort
Principle
- View the array as interleaved sub-arrays whose elements are cells apart; sort each with insertion sort → the array is -sorted: .
- Repeat for decreasing , ending with (a plain insertion sort on an almost-sorted array → fast).
- Quality depends on the sequence of increments.
Shell/Knuth increment sequence
Generated in increasing order, used in reverse: down to 1.
Worked example – : generate (stop: ). Use → increments 40, 13, 4, 1.
Other sequences are possible, e.g. .
template <class Elem>
void ShellSort(Elem *Tab, int n) {
int h = 1;
while (h <= n) h = 3*h + 1;
while (h > 1) {
h = h / 3;
InsertionShell<Elem>(Tab, n, h);
}
}
template <class Elem>
void InsertionShell(Elem *Tab, int n, int h) { // insertion sort with step h
for (int i = h; i < n; i++) {
Elem Tmp = Tab[i];
int j = i;
while (j - h >= 0 && Tmp < Tab[j-h]) { Tab[j] = Tab[j-h]; j -= h; }
Tab[j] = Tmp;
}
}Worked example – 16 elements with
Initial: 59 20 17 13 28 14 23 83 36 98 11 70 65 41 42 15
— write the array in rows of 8 and insertion-sort each column:
| 59 | 20 | 17 | 13 | 28 | 14 | 23 | 83 |
| 36 | 98 | 11 | 70 | 65 | 41 | 42 | 15 |
| ↓ | |||||||
| 36 | 20 | 11 | 13 | 28 | 14 | 23 | 15 |
| 59 | 98 | 17 | 70 | 65 | 41 | 42 | 83 |
→ 36 20 11 13 28 14 23 15 59 98 17 70 65 41 42 83
— rows of 4, sort columns:
| Before | After | ||||||
|---|---|---|---|---|---|---|---|
| 36 | 20 | 11 | 13 | 28 | 14 | 11 | 13 |
| 28 | 14 | 23 | 15 | 36 | 20 | 17 | 15 |
| 59 | 98 | 17 | 70 | 59 | 41 | 23 | 70 |
| 65 | 41 | 42 | 83 | 65 | 98 | 42 | 83 |
→ 28 14 11 13 36 20 17 15 59 41 23 70 65 98 42 83
— two interleaved sequences (even / odd positions):
- even: 28 11 36 17 59 23 65 42 → 11 17 23 28 36 42 59 65
- odd: 14 13 20 15 41 70 98 83 → 13 14 15 20 41 70 83 98
→ 11 13 17 14 23 15 28 20 36 41 42 70 59 83 65 98
— plain insertion sort (few shifts needed):
→ 11 13 14 15 17 20 23 28 36 41 42 59 65 70 83 98
⚠️ This worked example uses (Shell’s original “halve ” sequence), not the sequence that the code generates (for the code would use ). Both sort correctly; performs better.
Complexity
| Worst | Average | Best |
|---|---|---|
6. Heapsort
Principle
- Build a max-heap (or min-heap) from the array.
- Repeatedly remove the maximum (root) and place it at the end of the array; repeat as many times as there are nodes.
template <class Elem>
void maxHeap::heapSort(Elem *a, int n) {
for (int i = 0; i < n; ++i) Insert(a[i]);
for (int i = n - 1; i >= 0; --i) {
Elem v = deleteMax();
a[i] = v;
}
}Worked example – sort 5 2 9 1
| Step | Heap (array, root first) | Output array |
|---|---|---|
| insert 5, 2 | 5 2 | |
| insert 9 | 9 2 5 (9 sifted up) | |
| insert 1 | 9 2 5 1 | |
| deleteMax → 9 | 5 2 1 | _ _ _ 9 |
| deleteMax → 5 | 2 1 | _ _ 5 9 |
| deleteMax → 2 | 1 | _ 2 5 9 |
| deleteMax → 1 | – | 1 2 5 9 |
Complexity: insertions + deletions, each → in worst, average and best case.
⚠️ The slide’s version uses a separate heap ( extra space). Real heapsort builds the heap in place inside the array and is extra space.
7. Merge Sort
Principle
- If there are 0 or 1 elements → already sorted, return.
- Recursively sort the first half and the second half.
- Merge the two sorted halves into one sorted sequence ().
flowchart TD A["9 5 1 6 2"] --> B["9 5 1"] A --> C["6 2"] B --> D["9 5"] B --> E["1"] D --> F["9"] D --> G["5"] C --> H["6"] C --> I["2"] F --> J["5 9"] G --> J J --> K["1 5 9"] E --> K H --> L["2 6"] I --> L K --> M["1 2 5 6 9"] L --> M
template <class Elem>
void MergeSort(Elem *Tab, Elem *tmpTab, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
MergeSort(Tab, tmpTab, left, center);
MergeSort(Tab, tmpTab, center + 1, right);
Merge(Tab, tmpTab, left, center, right);
}
}
template <class Elem>
void Merge(Elem *Tab, Elem *tmpTab, int leftPos, int centerPos, int rightPos) {
for (int i = leftPos; i <= centerPos; i++) tmpTab[i] = Tab[i];
for (int j = 1; j <= rightPos - centerPos; j++)
tmpTab[rightPos - j + 1] = Tab[j + centerPos]; // right half copied REVERSED
int r = rightPos;
for (int k = leftPos; k <= r; k++)
if (tmpTab[leftPos] < tmpTab[rightPos]) Tab[k] = tmpTab[leftPos++];
else Tab[k] = tmpTab[rightPos--];
}The right half is copied in reverse, so the two halves face each other (largest values in the middle) — this acts as a sentinel and no “half exhausted” test is needed.
Worked example – merge [1 5 9] and [2 6]
tmpTab = 1 5 9 | 6 2 (right half reversed). Pointers: L at 1, R at 2.
| k | Compare | Take | Tab so far |
|---|---|---|---|
| 0 | 1 < 2 | 1 (L→) | 1 |
| 1 | 5 < 2? no | 2 (←R) | 1 2 |
| 2 | 5 < 6 | 5 (L→) | 1 2 5 |
| 3 | 9 < 6? no | 6 (←R) | 1 2 5 6 |
| 4 | 9 < 9? no (both point to 9) | 9 | 1 2 5 6 9 |
Complexity
Divide by and telescope:
Adding the equations: — in worst, average and best case.
⚠️ With
<the merge takes from the right half on ties → not stable. Use<=to keep equal keys in their original order. AlsotmpTab( extra space) should be freed withdelete[].
8. Quick Sort
Principle
A partition function picks a pivot and rearranges the array into:
- a left part with values pivot,
- the pivot,
- a right part with values pivot.
Then both parts are sorted by two recursive calls.
template <class Elem>
void QuickSort(Elem *Tab, int inf, int sup) {
if (sup > inf) {
int middle = Partition(Tab, inf, sup);
QuickSort(Tab, inf, middle - 1);
QuickSort(Tab, middle + 1, sup);
}
}
template <class Elem>
int Partition(Elem *Tab, int inf, int sup) {
Elem pivot = Tab[inf], temp;
int i = inf; // last position of an element <= pivot
for (int j = inf + 1; j <= sup; j++)
if (Tab[j] <= pivot) {
i++;
temp = Tab[i]; Tab[i] = Tab[j]; Tab[j] = temp;
}
temp = Tab[i]; Tab[i] = Tab[inf]; Tab[inf] = temp; // pivot to its place
return i;
}Invariant during partition: [pivot | ≤ pivot ... (up to i) | ≥ pivot ... (up to j-1) | not yet seen].
Worked example – partition 6 10 13 5 8 3 2 11 (pivot 6)
| j | Tab[j] | ≤ 6? | i | Array |
|---|---|---|---|---|
| – | 0 | 6 10 13 5 8 3 2 11 | ||
| 1 | 10 | no | 0 | 6 10 13 5 8 3 2 11 |
| 2 | 13 | no | 0 | 6 10 13 5 8 3 2 11 |
| 3 | 5 | yes → swap T[1],T[3] | 1 | 6 5 13 10 8 3 2 11 |
| 4 | 8 | no | 1 | 6 5 13 10 8 3 2 11 |
| 5 | 3 | yes → swap T[2],T[5] | 2 | 6 5 3 10 8 13 2 11 |
| 6 | 2 | yes → swap T[3],T[6] | 3 | 6 5 3 2 8 13 10 11 |
| 7 | 11 | no | 3 | 6 5 3 2 8 13 10 11 |
| end | swap pivot T[0]↔T[3] | 3 | 2 5 3 6 8 13 10 11 |
Returns 3: everything left of 6 is , everything right is .
Complexity
With the pivot ending at position : , .
| Case | When | Recurrence | Result |
|---|---|---|---|
| Worst | pivot always the smallest/largest → sub-array of size | ||
| Best | pivot always the median | ||
| Average |
⚠️ With the first element as pivot, an already sorted array triggers the worst case . Choosing a random pivot or the median of three avoids this.
9. Comparison of Time Complexities
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Selection | |||
| Bubble | |||
| Insertion | |||
| Shell | |||
| QuickSort | |||
| MergeSort | |||
| HeapSort |
10. Sorting in Linear Time
- Comparison sorts have a lower bound of comparisons.
- Non-comparison sorts (counting, bucket, radix) can run in under certain assumptions on the keys.
⚠️ The slide writes “lower bound ”; the correct notation for a lower bound is .
Counting Sort
Assumption: keys are integers in . If (order of ), sorting is .
Idea: for each element , count how many elements are ; that count is ‘s final position (e.g. 8 elements before → goes to position 9). Duplicates handled by decrementing the counter.
Arrays: input , output , counters .
for i = 0 to k: C[i] = 0
for j = 1 to length[A]: C[A[j]] = C[A[j]] + 1 // C[i] = # elements equal to i
for i = 1 to k: C[i] = C[i] + C[i-1] // C[i] = # elements <= i
for j = length[A] downto 1:
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1Worked example – ,
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| (counts) | 2 | 0 | 2 | 3 | 0 | 1 |
| (cumulative) | 2 | 2 | 4 | 7 | 7 | 8 |
Placement from the end of :
| j | A[j] | C[A[j]] → position | B after | C[A[j]] becomes |
|---|---|---|---|---|
| 8 | 3 | 7 | _ _ _ _ _ _ 3 _ | 6 |
| 7 | 0 | 2 | _ 0 _ _ _ _ 3 _ | 1 |
| 6 | 3 | 6 | _ 0 _ _ _ 3 3 _ | 5 |
| 5 | 2 | 4 | _ 0 _ 2 _ 3 3 _ | 3 |
| 4 | 0 | 1 | 0 0 _ 2 _ 3 3 _ | 0 |
| 3 | 3 | 5 | 0 0 _ 2 3 3 3 _ | 4 |
| 2 | 5 | 8 | 0 0 _ 2 3 3 3 5 | 7 |
| 1 | 2 | 3 | 0 0 2 2 3 3 3 5 | 2 |
Result: .
- Complexity in all cases → when .
- No comparisons at all.
- Stable: equal keys keep their initial order (thanks to the backward loop).
Bucket Sort
Assumption: inputs are uniformly distributed in , with .
Idea: split into equal buckets, distribute the numbers (bucket ), sort each bucket (insertion sort), concatenate.
n = length[A]
for i = 1 to n: insert A[i] into list B[floor(n * A[i])]
for i = 0 to n-1: sort list B[i] with insertion sort
concatenate B[0], B[1], ..., B[n-1]Worked example – (, bucket holds )
| Bucket | Contents (sorted) |
|---|---|
| 0 | – |
| 1 | .12 .17 |
| 2 | .21 .23 .26 |
| 3 | .39 |
| 4, 5 | – |
| 6 | .68 |
| 7 | .72 .78 |
| 8 | – |
| 9 | .94 |
Concatenation: .12 .17 .21 .23 .26 .39 .68 .72 .78 .94
Expected complexity: with = size of bucket ,
Since each value is equally likely to fall in any bucket, , so .
⚠️ If the data are not uniform (e.g. all values in ), everything lands in one bucket and the cost degrades to insertion sort, .
Radix Sort
Originally used for punched cards. Sort on the least significant digit first, then the next digit, … up to the most significant, each time with a stable sort (e.g. counting sort).
for i = 1 to d: stable-sort A on digit i // d = max number of digitsWorked example
| Input | By units | By tens | By hundreds |
|---|---|---|---|
| 329 | 720 | 720 | 329 |
| 457 | 355 | 329 | 355 |
| 657 | 436 | 436 | 436 |
| 839 | 457 | 839 | 457 |
| 436 | 657 | 355 | 657 |
| 720 | 329 | 457 | 720 |
| 355 | 839 | 657 | 839 |
Complexity: with counting sort ( = base, here 10).
⚠️ The per-digit sort must be stable; otherwise the order established by lower digits is destroyed.