Past exam question: 2073 Bhadra (Regular), Q8
Open in the Padhaiko appQuestion
Provide best case, average case and worst case for following algorithms in Big-Oh: bubble sort, insertion sort, merge sort and selection sort. Construction heap sort for following given list with an algorithm: 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22.
Solution
Asymptotic Time Complexity Comparison:
| Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort (with early-exit flag) | |||
| Insertion Sort | |||
| Merge Sort | |||
| Selection Sort |
Heap Sort Algorithm:
Algorithm HEAPSORT(A, n):
1. For i = floor(n/2) - 1 down to 0:
HEAPIFY(A, n, i) // Build max-heap
2. For end = n - 1 down to 1:
Swap A[0] and A[end]
HEAPIFY(A, end, 0) // Restore max-heap on A[0..end-1]Trace on [37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22] ():
- Build Max-Heap (heapify indices ):
[92, 86, 48, 33, 57, 22, 26, 25, 12, 37, 42, 18] - Extraction Passes:
- Swap
9218, heapify(11):[86, 57, 48, 33, 42, 22, 26, 25, 12, 37, 18 | 92] - Swap
8618, heapify(10):[57, 42, 48, 33, 37, 22, 26, 25, 12, 18 | 86, 92] - Swap
5718, heapify(9):[48, 42, 26, 33, 37, 22, 18, 25, 12 | 57, 86, 92] - Swap
4812, heapify(8):[42, 37, 26, 33, 12, 22, 18, 25 | 48, 57, 86, 92] - Swap
4225, heapify(7):[37, 33, 26, 25, 12, 22, 18 | 42, 48, 57, 86, 92] - Swap
3718, heapify(6):[33, 25, 26, 18, 12, 22 | 37, 42, 48, 57, 86, 92] - Swap
3322, heapify(5):[26, 25, 22, 18, 12 | 33, 37, 42, 48, 57, 86, 92] - Swap
2612, heapify(4):[25, 18, 22, 12 | 26, 33, 37, 42, 48, 57, 86, 92] - Swap
2512, heapify(3):[22, 18, 12 | 25, 26, 33, 37, 42, 48, 57, 86, 92] - Swap
2212, heapify(2):[18, 12 | 22, 25, 26, 33, 37, 42, 48, 57, 86, 92] - Swap
1812:[12, 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92]
- Swap
Answer:
- Complexities: Bubble/Insertion: best, avg/worst; Selection: all; Merge: all.
- Heap Sort Output:
12, 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92.