Module 96

Here are complete, clean, and easy-to-understand pseudocode for all sorting algorithms covered in Unit I, with short comments and example traces where helpful.

1. Shell Sort

SHELL-SORT(A, n)
    gap ← n/2
    while gap > 0
        for i ← gap to n-1
            temp ← A[i]
            j ← i
            while j ≥ gap and A[j - gap] > temp
                A[j] ← A[j - gap]
                j ← j - gap
            A[j] ← temp
        gap ← gap / 2          // integer division

Example: [8,3,7,4,9,2,6] → gaps 3→1 → sorted

2. Quick Sort

QUICKSORT(A, low, high)
    if low < high
        pi ← PARTITION(A, low, high)
        QUICKSORT(A, low, pi-1)
        QUICKSORT(A, pi+1, high)

PARTITION(A, low, high)
    pivot ← A[high]                 // last element as pivot
    i ← low - 1
    for j ← low to high-1
        if A[j] ≤ pivot
            i ← i + 1
            swap A[i] ↔ A[j]
    swap A[i+1] ↔ A[high]
    return i+1                      // pivot position

Example: [5,3,8,4,9,1,6,2,7] → pivot 7 → after partition: [5,3,1,4,6,2,7,8,9]

3. Merge Sort

MERGE-SORT(A, low, high)
    if low < high
        mid ← (low + high) / 2
        MERGE-SORT(A, low, mid)
        MERGE-SORT(A, mid+1, high)
        MERGE(A, low, mid, high)

MERGE(A, low, mid, high)
    leftSize  ← mid - low + 1
    rightSize ← high - mid
    Let L[1..leftSize+1], R[1..rightSize+1] be new arrays
    for i ← 1 to leftSize
        L[i] ← A[low + i - 1]
    for j ← 1 to rightSize
        R[j] ← A[mid + j]
    L[leftSize+1] ← ∞          // sentinel
    R[rightSize+1] ← ∞         // sentinel
    i ← 1, j ← 1
    for k ← low to high
        if L[i] ≤ R[j]
            A[k] ← L[i]; i ← i+1
        else
            A[k] ← R[j]; j ← j+1

Example: [38,27,43,3,9,82,10] → final merged sorted array

4. Heap Sort

HEAP-SORT(A, n)
    BUILD-MAX-HEAP(A, n)                 // O(n)
    for i ← n downto 2
        swap A[1] ↔ A[i]                 // move max to end
        heapSize ← heapSize - 1
        MAX-HEAPIFY(A, 1, heapSize)      // restore heap property

BUILD-MAX-HEAP(A, n)
    heapSize ← n
    for i ← ⌊n/2⌋ downto 1
        MAX-HEAPIFY(A, i, n)

MAX-HEAPIFY(A, i, heapSize)
    left  ← 2*i
    right ← 2*i + 1
    largest ← i
    if left ≤ heapSize and A[left] > A[i]
        largest ← left
    if right ≤ heapSize and A[right] > A[largest]
        largest ← right
    if largest ≠ i
        swap A[i] ↔ A[largest]
        MAX-HEAPIFY(A, largest, heapSize)

(Note: Arrays are 1-based in standard heap pseudocode)

5. Counting Sort (Linear Time)

COUNTING-SORT(A, B, k)        // A: input, B: output, k: max value
    Let C[0..k] be new array
    for i ← 0 to k
        C[i] ← 0
    for j ← 1 to length(A)
        C[A[j]] ← C[A[j]] + 1          // count occurrences
    for i ← 1 to k
        C[i] ← C[i] + C[i-1]           // cumulative count
    for j ← length(A) downto 1
        B[C[A[j]]] ← A[j]
        C[A[j]] ← C[A[j]] - 1
    return B

Example: A = [4,2,1,4,3,2], k=4 → B = [1,2,2,3,4,4]

6. Radix Sort (LSD – Least Significant Digit)

RADIX-SORT(A, d)          // d = max number of digits
    for digit ← 1 to d
        use stable sort (Counting Sort) to sort A by current digit
        // extract digit using (number / 10^(digit-1)) mod 10

Full version using Counting Sort as subroutine:

RADIX-SORT(A, n, maxDigits)
    for pos ← 1 to maxDigits
        COUNTING-SORT-BY-DIGIT(A, pos)   // sorts on pos-th digit

Example: 170, 45, 75, 90, 802, 2 → after units → tens → hundreds → sorted

Bonus: Insertion Sort (often used inside Shell Sort)

INSERTION-SORT(A, n)
    for i ← 1 to n-1
        key ← A[i]
        j ← i - 1
        while j ≥ 0 and A[j] > key
            A[j+1] ← A[j]
            j ← j - 1
        A[j+1] ← key

Now you have complete, exam-ready pseudocode for every sorting algorithm in Unit I, with clear logic and examples. Copy-paste them directly into your notes! Good luck with your studies! 🚀