Question

Alfa The first column in the table below contains an unsorted list of words. The last column contains a sorted list of words. Each intermediate column contains a partially sorted list. Each intermediate column was constructed by beginning with the unsorted list at the left and running one of the sorting algorithms that we learned about in class, stopping at some point before it finishes. Each algorithm is executed exactly as described in the lecture notes. (One column has been sorted using a sorting algorithm not listed.) Identify, below, which column was (partially) sorted with which algorithm. Hint: Do not just execute each sorting algorithm, step-by-step, until it matches one of the columns. Instead, think about the invariants that are true at every step of the sorting algorithm. Unsorted A B с D E F Sorted Juliett Alfa Bravo Bravo Delta Mike Alfa Bravo Bravo Juliett Alfa Bravo Lima Bravo Bravo Kilo Juliett Kilo Foxtrot Echo Kilo Charlie Charlie Lima Kilo Lima Charlie Hotel Juliett Delta Delta Papa Lima Alfa Juliett Golf Delta Echo Echo Alfa Papa Charlie Delta Alfa India Juliett Foxtrot Foxtrot Foxtrot Foxtrot Kilo Foxtrot Hotel Foxtrot Golf Charlie Charlie Papa India Charlie Charlie Kilo Hotel Oscar Oscar Oscar Golf India Foxtrot Oscar India Delta Delta Delta Hotel Juliett Echo Lima Juliett November November November Lima November Bravo November Kilo India India India Echo Oscar Alfa India Lima Golf Golf Golf Mike Papa Golf Golf Mike Hotel Hotel Hotel November Lima November Hotel November Mike Mike Oscar Mike Oscar Mike Oscar Echo Echo Echo Papa Kilo Papa Papa Papa Unsorted A B с D E F Sorted Mike Please write the proper number in the blank space beside the letter: A 1. BubbleSort B 2. SelectionSort с 3. Insertion Sort D 4. Merge Sort (top down, sorts top half before bottom half) E 5. QuickSort (with first element as the pivot) F 6. None of the above

Answer 1

The correct options are

A - InsertionSort

B - MergeSort

C - BubbleSort

D - QuickSort

E - None

F - SelectionSort

Explaination:

A - InsertionSort

We know that Insertion sort maintains a sorted sub-list, it compares between two elements sequentially and swaps them, and also in turn compares with all the other elements in the sub-list.

This way we get Alfa, Bravo, Juliett, Kilo, Lima, Papa...

B - MergeSort

We know that Merge sort divides the values until one element is remaining, and merges them back by sorting each pair. It's mentioned in the problem that top half is sorted first, hence Option B. Until Papa is the top sorted half.

C - BubbleSort

It compares two elements and swaps, repeats until everything is sorted. C is correct for this.

D - QuickSort

In quick sort, one element is taken as pivot, left pointer keeps increasing till it finds an element greater than the pivot. Right pointer decreases till it finds an element lesser than pivot and then both are swapped. This is continued till both pointers crossover and the right pointer is replaced with pivot. In our case Juliett is the pivot, so after performing quicksort it should be placed in the correct place. Hence D is the option.

E- None of the above

F- SelectionSort

The lowest values are selected from the unsorted array and kept in the sorted array. This pattern is seen in F.

comment for any further clarifications!