The column on the left is the original input of strings to be sorted; the column
ID: 3759018 • Letter: T
Question
The column on the left is the original input of strings to be sorted; the column on the right are the string in sorted order; the other columns are the contents at some intermediate step during one of the 8 sorting algorithms listed below. Match up each algorithm by writing its number under the corresponding column. Use each number exactly once.
(a) Selection sort
(b) Insertion sort
(c) Shellsort (13-4-1 increments)
(d) Mergesort (top-down)
(e) Mergesort (bottom-up)
(f) Quicksort (standard, no shuffle)
(g) Quicksort (3-way, no shuffle)
(h) Heapsort
Extra credit (just a bit): why don’t f and g make use of a shuffle?
C T E E M S S S S S S O B B rt R R E H-10 O O O O O O C E E ETTLSFFFI PPR LYY TYS YLTTF MRR EE HE os os os os os os E G E E E AE EB CO HI RF IN HY OL AT AT RE LE EL HY TEMCSE8S OR PH CTEEM EBY 3RRE UHREH AAC CI CH C C C C C C O E E E M E E E P M P O G P L CESSOBEEGONET YTESBES OPCPC CCCEEG ROE pExplanation / Answer
(a) Selection sort
Column 3 follows selection sort,
As all the starting lemenst are in the final sorted order, which is the property of the selection sort.
Hence, it is selection sort.
(b) Insertion sort
It is the 12 th step of insertion sort.All the elements above the 12th element are sorted, and the elements below the 12th element are not sorted.
Hence it is insertion sort in the 1st column.
(c) Shellsort (13-4-1 increments)
Column 5 is one of the step of shell sort, by observation of shell sort rules on the given data.
d) Mergesort (top-down)
Column 2 is one of the step of merge sort, As the merging and sorting property Is observed in that in the top down order.
(e) Mergesort (bottom-up)
Column 4 is one of the step of merge sort, As the merging and sorting property Is observed in that data.
(f) Quicksort (standard, no shuffle)
Column 6 is one of the step of Quicksort sort, As the quick sort property Is observed in that.
(g) Quicksort (3-way, no shuffle)
Column 8 is one of the step of Quicksort sort, As the quick sort property Is observed in that.
(h) Heapsort
Column 4 is one of the step of Heapsort, by observation of heap sort rules on the given data.
Final answer:
1 Insertion sort
2 Mergesort (top-down)
3 Selection sort
4 Mergesort (bottom-up)
5 Shellsort (13-4-1 increments)
6 Quicksort (standard, no shuffle)
7 Heapsort
8 Quicksort (3-way, no shuffle)