Quick Sort Experiment
1. Which of the following arrays are sorted in ascending order?
2. You are given the array [9, 5, 3, 8, 1, 2, 10, 11, 8, 12]. What is the index of 2 if the array is 1-indexed?
3. You are given the array [9, 5, 3, 8, 1, 2, 10, 11, 8, 12]. Which sequence gives the original 1-based indices of the elements in their order in the sorted array?
4. You are asked to sort an array. After the first partitioning step of Quick Sort, the result is [6, 4, 5, 3, 7, 9, 8, 11, 12]. Which of the following could have been the chosen pivot?
5. Consider the following Quick Sort pseudo-code. Which condition can be used for blank (A) when elements smaller than the pivot are placed in smaller_array?
quick_sort(array) -> sorted-array:
if array is empty: return array
pivot = choose_pivot_index()
smaller_array = [], bigger_array = []
for i = 1 to sizeof(array):
if (-----A-----):
append array[i] to smaller_array
else if (-----B-----):
append array[i] to bigger_array
return quick_sort(smaller_array) + [array[pivot]] + quick_sort(bigger_array)
6. Using the same Quick Sort pseudo-code, which condition can be used for blank (B) when elements larger than the pivot are placed in bigger_array?
7. An array of 16 elements is already sorted. We always pick the first element of the array at each step as the pivot. How many recursion levels will Quick Sort require in the worst-case partition pattern?
8. An array of 16 elements is initially sorted in decreasing order. We always choose the middle element, using the higher of the two middle elements when there is a tie, as the pivot. Approximately how many recursion levels are required when the partitions remain balanced?
9. Bozo-sort repeatedly generates a random permutation of an array and checks whether the array is sorted. Which statement best describes its average-case time complexity and its relation to Quick Sort?