Specialized Sorting Algorithms: Custom Solutions for Specific Problems

Welcome to specialized sorting algorithms! While divide and conquer algorithms work well for general cases, sometimes you need algorithms designed for specific scenarios. These algorithms excel when you know something special about your data.

Heap Sort: The Reliable Pyramid Builder 🏗️

Real-Life Analogy: Priority Document Organizer

Imagine you have a huge pile of important documents that need to be processed in priority order. You build a special pyramid where the most important document is always on top. Each time you need to process a document, you take the top one and rebuild the pyramid.

That’s Heap Sort - it builds a “max-heap” where the largest element is always accessible, then repeatedly extracts the largest element.

How Heap Sort Works (Step by Step)

Let’s sort: [4, 10, 3, 5, 1]

Step 1: Build the heap (heapify)

• Start with: [4, 10, 3, 5, 1]
• Transform into a max-heap where every parent ≥ its children
• Result: [10, 5, 3, 4, 1] (10 is largest, at the top!)

Step 2: Extract maximum elements

• Swap largest (10) with last element: [1, 5, 3, 4, 10]
• Heapify the remaining elements: [5, 4, 3, 1, 10]
• Swap largest (5) with last: [1, 4, 3, 5, 10]
• Heapify remaining: [4, 1, 3, 5, 10]
• Continue until sorted: [1, 3, 4, 5, 10]

Understanding Heap Structure

A heap is a complete binary tree stored in an array:

• Root: index 0
• Left child: index 2*i + 1
• Right child: index 2*i + 2
• Parent: index (i-1)/2

For array [10, 5, 3, 4, 1]:

       10  (index 0)
      /  \
     5    3  (indices 1,2)
    / \
   4   1     (indices 3,4)

Max-Heap Rule: Every parent node ≥ its children

Complete Go Implementation

package main

import "fmt"

// HeapSort builds a max-heap and repeatedly extracts maximum elements
func HeapSort(arr []int) {
    n := len(arr)

    // Build max heap (heapify from bottom up)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // Extract elements one by one
    for i := n - 1; i > 0; i-- {
        // Move current root (largest) to end
        arr[0], arr[i] = arr[i], arr[0]

        // Heapify the reduced heap
        heapify(arr, i, 0)
    }
}

// heapify ensures the subtree rooted at index i follows max-heap property
func heapify(arr []int, n, i int) {
    largest := i         // Assume current node is largest
    left := 2*i + 1      // Left child
    right := 2*i + 2     // Right child

    // Check if left child exists and is larger than root
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // Check if right child exists and is larger than current largest
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // If largest is not root, swap and continue heapifying
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest) // Recursively heapify affected subtree
    }
}

func main() {
    testArrays := [][]int{
        {4, 10, 3, 5, 1},
        {12, 11, 13, 5, 6, 7},
        {1},
        {},
        {3, 2, 1, 5, 4},
    }

    for i, arr := range testArrays {
        original := make([]int, len(arr))
        copy(original, arr)

        HeapSort(arr)
        fmt.Printf("Test %d: %v → %v\n", i+1, original, arr)
    }
}

Why Heap Sort is Reliable

• Guaranteed performance: Always O(n log n), even in worst case
• In-place sorting: No extra space needed
• No worst-case scenarios: Performance doesn’t depend on input order
• Cache-friendly: Works well with computer memory

Time Complexity: O(n log n) for all cases (best, average, worst) Space Complexity: O(1) - sorts in place Stable: No (equal elements may change order)

Counting Sort: The Inventory Counter 📊

Real-Life Analogy: Store Inventory

Imagine you’re a store manager taking inventory of toys by size. Instead of comparing each toy to every other toy, you simply count how many toys of each size you have, then put them out in order:

• Size 1: 2 toys
• Size 2: 1 toy
• Size 3: 2 toys
• Size 4: 1 toy

Then place them in order: two 1’s, one 2, two 3’s, one 4.

That’s Counting Sort - perfect when you know the range of values ahead of time!

How Counting Sort Works (Step by Step)

Let’s sort: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] (range 1-9)

Step 1: Count occurrences

• Create count array: index represents value, value represents count
• count[1] = 2, count[2] = 1, count[3] = 2, count[4] = 1, count[5] = 3, count[6] = 1, count[9] = 1

Step 2: Calculate positions

• Make count cumulative: count[i] = number of elements ≤ i
• count[1] = 2, count[2] = 3, count[3] = 5, count[4] = 6, count[5] = 9, etc.

Step 3: Build output array

• Place elements in correct positions using cumulative counts
• Result: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Complete Go Implementation

package main

import "fmt"

// CountingSort sorts by counting occurrences of each value
func CountingSort(arr []int, maxValue int) []int {
    if len(arr) == 0 {
        return arr
    }

    // Step 1: Create count array (size maxValue + 1)
    count := make([]int, maxValue+1)
    output := make([]int, len(arr))

    // Step 2: Count occurrences of each element
    for _, num := range arr {
        if num >= 0 && num <= maxValue {
            count[num]++
        }
    }

    // Step 3: Make count array cumulative
    // count[i] now contains number of elements ≤ i
    for i := 1; i <= maxValue; i++ {
        count[i] += count[i-1]
    }

    // Step 4: Build output array
    // Place elements in correct positions
    for i := len(arr) - 1; i >= 0; i-- {
        num := arr[i]
        if num >= 0 && num <= maxValue {
            position := count[num] - 1
            output[position] = num
            count[num]-- // Decrement for next occurrence
        }
    }

    return output
}

func main() {
    // Test scores (0-100)
    scores := []int{85, 92, 78, 96, 88, 73, 91, 85, 82}
    fmt.Println("Test scores:", scores)
    sortedScores := CountingSort(scores, 100)
    fmt.Println("Sorted scores:", sortedScores)

    // Small range example
    smallRange := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
    fmt.Println("\nSmall range array:", smallRange)
    sortedSmall := CountingSort(smallRange, 9)
    fmt.Println("Sorted:", sortedSmall)
}

When Counting Sort Excels

• Known range: Like test scores (0-100), ages (0-120), months (1-12)
• Integer data: Works with whole numbers
• Small range: When range k is much smaller than number of elements n
• Stable sorting needed: Preserves relative order of equal elements

Time Complexity: O(n + k) where k is the range Space Complexity: O(n + k) Stable: Yes

Radix Sort: The Digit-by-Digit Organizer 📱

Real-Life Analogy: Sorting Phone Numbers

Imagine sorting phone numbers by area code, then exchange, then number. Instead of comparing entire numbers, you sort one digit at a time:

1. Sort by last 4 digits
2. Then sort by middle 3 digits
3. Finally sort by area code

That’s Radix Sort - it processes one digit position at a time, from least significant to most significant.

How Radix Sort Works (Step by Step)

Let’s sort: [170, 045, 075, 090, 002, 024, 802, 066]

Step 1: Sort by units place (rightmost digit)

• 170(0), 045(5), 075(5), 090(0), 002(2), 024(4), 802(2), 066(6)
• Group by last digit: [170,090], [002,802], [024], [045,075], [066]
• Result: [170, 090, 002, 802, 024, 045, 075, 066]

Step 2: Sort by tens place

• 170(7), 090(9), 002(0), 802(0), 024(2), 045(4), 075(7), 066(6)
• Group by tens: [002,802], [024], [045], [066], [170,075], [090]
• Result: [002, 802, 024, 045, 066, 170, 075, 090]

Step 3: Sort by hundreds place

• 002(0), 802(8), 024(0), 045(0), 066(0), 170(1), 075(0), 090(0)
• Group by hundreds: [002,024,045,066,075,090], [170], [802]
• Result: [002, 024, 045, 066, 075, 090, 170, 802] ✅

Complete Go Implementation

package main

import "fmt"

// RadixSort sorts numbers digit by digit, from least to most significant
func RadixSort(arr []int) {
    if len(arr) == 0 {
        return
    }

    // Find maximum number to determine number of digits
    maxNum := findMax(arr)

    // Sort by each digit place (1s, 10s, 100s, etc.)
    for digitPlace := 1; maxNum/digitPlace > 0; digitPlace *= 10 {
        countingSortByDigit(arr, digitPlace)
    }
}

// countingSortByDigit sorts array by a specific digit place
func countingSortByDigit(arr []int, digitPlace int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10) // 0-9 digits

    // Count occurrences of each digit in this place
    for _, num := range arr {
        digit := (num / digitPlace) % 10
        count[digit]++
    }

    // Make count cumulative
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    // Build output array (stable sort)
    for i := n - 1; i >= 0; i-- {
        digit := (arr[i] / digitPlace) % 10
        position := count[digit] - 1
        output[position] = arr[i]
        count[digit]--
    }

    // Copy back to original array
    copy(arr, output)
}

// findMax returns the maximum value in array
func findMax(arr []int) int {
    if len(arr) == 0 {
        return 0
    }

    max := arr[0]
    for _, num := range arr[1:] {
        if num > max {
            max = num
        }
    }
    return max
}

func main() {
    // Phone numbers (last 3 digits)
    phoneNumbers := []int{5551234, 5559876, 5553456, 5551111, 5558765}
    fmt.Println("Phone numbers:", phoneNumbers)
    RadixSort(phoneNumbers)
    fmt.Println("Sorted by number:", phoneNumbers)

    // Mixed numbers
    mixed := []int{170, 45, 75, 90, 2, 24, 802, 66}
    fmt.Println("\nMixed numbers:", mixed)
    RadixSort(mixed)
    fmt.Println("Sorted:", mixed)
}

Why Radix Sort is Special

• Stable sorting: Preserves relative order of equal elements
• No comparisons: Just groups by digit values
• Fixed performance: Doesn’t depend on input order
• Perfect for: Numbers with same digit length, strings

Time Complexity: O(n × d) where d is number of digits Space Complexity: O(n + k) Stable: Yes

Algorithm Comparison: When to Use Each? 🎯

Real-World Applications

• Heap Sort: Priority queues, scheduling algorithms
• Counting Sort: Sort characters in strings, histogram-based algorithms
• Radix Sort: Sort IP addresses, phone numbers, employee IDs

Practice Problems 🎯

1. Priority Tasks: Use heap sort to sort tasks by priority level
2. Grade Distribution: Use counting sort to sort exam scores 0-100
3. Phone Book: Use radix sort to sort phone numbers
4. Memory Comparison: Compare space usage of all three algorithms
5. Hybrid Sorter: Create a function that chooses the best algorithm based on data characteristics

What’s Next? 🚀

Now that you understand specialized sorting algorithms, the final lesson will cover advanced concepts like hybrid sorting algorithms (Intro Sort, Timsort), external sorting for big data, and how Go’s built-in sorting works!

Specialized algorithms teach us that the best solution depends on your specific data characteristics. Choose wisely! 🎯