Question

Use the following sequence as the list to sort: [ T, H, A, N, K, F, U, L ] You need to display the contents of the list during the execution of the algorithm. a) Sort the list using selection sort. b) Sort the list using heap sort. You do not need to draw the heap diagram unless you find it helpful, but you must still show the contents on the list during execution. c) What is the worst-case runtime complexity of selection sort? d) What is the worst-case runtime complexity of heap sort?

Answer 1

A. SELECTION SORT

1. [ T, H, A, N, K, F, U, L ]
2. [ A, T, H, N, K, F, U, L ]
3. [ A, F, T, H, N, K, U, L ]
4. [ A, F, H, T, N, K, U, L ]
5. [ A, F, H, K, T, N, U, L ]
6. [ A, F, H, K, L, T, N, U ]
7. [ A, F, H, K, L, N, T, U ]

The time complexity of Selection Sort is O(n²).

A. HEAP SORT

T H A N K F U L 
T H U N K F A L 
T N U L K F A H 
U N T L K F A H 
U N T L K F A H 
H N T L K F A U 
T N H L K F A U 
A N H L K F T U 
N L H A K F T U 
F L H A K N T U 
L K H A F N T U 
F K H A L N T U 
K F H A L N T U 
A F H K L N T U 
H F A K L N T U 
A F H K L N T U 
F A H K L N T U 
A F H K L N T U 
A F H K L N T U 
A F H K L N T U 
A F H K L N T U 
Sorted array is 
A F H K L N T U 

The time complexity of Heap Sort is O(nlogn).