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 foundArray (sorted part in bold)
start42 20 17 13 28 14 23 15
01313 20 17 42 28 14 23 15
11413 14 17 42 28 20 23 15
21513 14 15 42 28 20 23 17
31713 14 15 17 28 20 23 42
42013 14 15 17 20 28 23 42
52313 14 15 17 20 23 28 42
62813 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)
start42 20 17 13 28 14 23 15
013 42 20 17 14 28 15 23
113 14 42 20 17 15 28 23
213 14 15 42 20 17 23 28
313 14 15 17 42 20 23 28
413 14 15 17 20 42 23 28
513 14 15 17 20 23 42 28
613 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

InsertedArray (sorted part in bold)
12020 42 17 13 28 14 23 15
21717 20 42 13 28 14 23 15
31313 17 20 42 28 14 23 15
42813 17 20 28 42 14 23 15
51413 14 17 20 28 42 23 15
62313 14 17 20 23 28 42 15
71513 14 15 17 20 23 28 42

Complexity

CaseWhenCost
Worsteach element inserted at the beginning (reverse-sorted input)
Besteach element stays at the end (already sorted) comparisons →
Average

Comparison of the simple sorts

WorstAverageBest
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:

5920171328142383
3698117065414215
↓
3620111328142315
5998177065414283

→ 36 20 11 13 28 14 23 15 59 98 17 70 65 41 42 83

— rows of 4, sort columns:

BeforeAfter
3620111328141113
2814231536201715
5998177059412370
6541428365984283

→ 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

WorstAverageBest

6. Heapsort

Principle

  1. Build a max-heap (or min-heap) from the array.
  2. 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

StepHeap (array, root first)Output array
insert 5, 25 2
insert 99 2 5 (9 sifted up)
insert 19 2 5 1
deleteMax → 95 2 1_ _ _ 9
deleteMax → 52 1_ _ 5 9
deleteMax → 21_ 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.

kCompareTakeTab so far
01 < 21 (L→)1
15 < 2? no2 (←R)1 2
25 < 65 (L→)1 2 5
39 < 6? no6 (←R)1 2 5 6
49 < 9? no (both point to 9)91 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. Also tmpTab ( extra space) should be freed with delete[].


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)

jTab[j]≤ 6?iArray
–06 10 13 5 8 3 2 11
110no06 10 13 5 8 3 2 11
213no06 10 13 5 8 3 2 11
35yes → swap T[1],T[3]16 5 13 10 8 3 2 11
48no16 5 13 10 8 3 2 11
53yes → swap T[2],T[5]26 5 3 10 8 13 2 11
62yes → swap T[3],T[6]36 5 3 2 8 13 10 11
711no36 5 3 2 8 13 10 11
endswap pivot T[0]↔T[3]32 5 3 6 8 13 10 11

Returns 3: everything left of 6 is , everything right is .

Complexity

With the pivot ending at position : , .

CaseWhenRecurrenceResult
Worstpivot always the smallest/largest → sub-array of size
Bestpivot 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

AlgorithmBestAverageWorst
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]] - 1

Worked example – ,

012345
(counts)202301
(cumulative)224778

Placement from the end of :

jA[j]C[A[j]] → positionB afterC[A[j]] becomes
837_ _ _ _ _ _ 3 _6
702_ 0 _ _ _ _ 3 _1
636_ 0 _ _ _ 3 3 _5
524_ 0 _ 2 _ 3 3 _3
4010 0 _ 2 _ 3 3 _0
3350 0 _ 2 3 3 3 _4
2580 0 _ 2 3 3 3 57
1230 0 2 2 3 3 3 52

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 )

BucketContents (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 digits

Worked example

InputBy unitsBy tensBy hundreds
329720720329
457355329355
657436436436
839457839457
436657355657
720329457720
355839657839

Complexity: with counting sort ( = base, here 10).

⚠️ The per-digit sort must be stable; otherwise the order established by lower digits is destroyed.