Scene 1 (0s)
ADVANCED SORTING ALGORITHMS A Comprehensive Analysis & Implementation Prepared for: Algorithms Practical Exam 2026 Topics: Heap Sort | Counting Sort | Radix Sort Algorithms 2026 | Slide 1.
Scene 2 (9s)
1. HEAP SORT Core Concept Comparison-based sorting technique based on a Binary Heap data structure. Similar to selection sort where we first find the maximum element. Build Max-Heap: Transform input array into a heap where parent > children. Extract Max: Swap root with last element and rebuild heap. Complexity: O(n log n) | Space: O(1) Mathematical Example Input: [4, 10, 3, 5, 1] Build Max-Heap: [10, 5, 3, 4, 1] Swap root(10) with last(1): [1, 5, 3, 4] | Sorted: 10 Heapify and repeat until sorted: [1, 3, 4, 5, 10] • • 1. 2. 3. Algorithms 2026 | Slide 2.
Scene 3 (38s)
HEAP SORT: IMPLEMENTATION def heapify(arr, n, i): largest = i l, r = 2 * i + 1, 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build maxheap for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) Algorithms 2026 | Slide 3.
Scene 4 (1m 3s)
2. COUNTING SORT Non-Comparison Logic Integer sorting algorithm that counts objects having each distinct key value. Uses a Frequency Array to store counts. Cumulative counts determine final index positions. Best for: Small range of input data (K) relative to size (N). Complexity: O(n + k) | Stable Algorithm def countingSort(arr): max_val = max(arr) count = [0] * (max_val + 1) output = [0] * len(arr) for num in arr: count[num] += 1 for i in range(1, len(count)): count[i] += count[i-1] for num in reversed(arr): output[count[num] - 1] = num count[num] -= 1 return output • • • Algorithms 2026 | Slide 4.
Scene 5 (1m 27s)
3. RADIX SORT Digit-by-Digit Processing Avoids comparison by distributing elements into buckets according to individual digits. Processes from Least Significant Digit (LSD) to Most (MSD). Utilizes Counting Sort as a stable subroutine. Complexity: O(d * (n + k)) Example [170, 45, 75, 90, 802, 2, 24, 66] Sort by Units: [170, 90, 802, 2, 24, 45, 75, 66] Sort by Tens: [802, 2, 24, 45, 66, 170, 75, 90] Sort by Hundreds: [2, 24, 45, 66, 75, 90, 170, 802] • • 1. 2. 3. Algorithms 2026 | Slide 5.
Scene 6 (1m 56s)
TECHNICAL COMPARISON Algorithm Time (Worst) Space Best Use Case Heap Sort O(n log n) O(1) Memory-constrained systems Counting Sort O(n + k) O(n + k) Small range of integers Radix Sort O(d * (n + k)) O(n + k) Large arrays with fixed digits Viva Pro-Tip If asked "Why is Heap Sort not stable?", explain that long-distance swaps during heapification do not preserve the relative order of duplicate elements. Algorithms 2026 | Final Slide.