10. (10 points) You are running quicksort. List the comparisons between elements
ID: 3725155 • Letter: 1
Question
10. (10 points) You are running quicksort. List the comparisons between elements (in the order the happen), and the pivots chosen (in the order they happen). Assume that you always use the rightmost legal element as a pivot, and also assume that when you run partition, it simply slides smaller values to the left of the pivot and larger values to the right, without otherwise changing the order of elements within each partition. Your starting array: 431658297Explanation / Answer
Array is [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 4 and 7 --> swapped 4 4 [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 3 and 7 --> swapped 3 3 [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 1 and 7 --> swapped 1 1 [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 6 and 7 --> swapped 6 6 [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 5 and 7 --> swapped 5 5 [4, 3, 1, 6, 5, 8, 2, 9, 7] Comparing 8 and 7 Comparing 2 and 7 --> swapped 8 2 [4, 3, 1, 6, 5, 2, 8, 9, 7] Comparing 9 and 7 *** Just set pivot: swapped 8 7 [4, 3, 1, 6, 5, 2, 7, 9, 8] Array is [4, 3, 1, 6, 5, 2] Comparing 4 and 2 Comparing 3 and 2 Comparing 1 and 2 --> swapped 4 1 [1, 3, 4, 6, 5, 2] Comparing 6 and 2 Comparing 5 and 2 *** Just set pivot: swapped 3 2 [1, 2, 4, 6, 5, 3, 7, 9, 8] Array is [4, 6, 5, 3] Comparing 4 and 3 Comparing 6 and 3 Comparing 5 and 3 *** Just set pivot: swapped 4 3 [1, 2, 3, 6, 5, 4, 7, 9, 8] Array is [6, 5, 4] Comparing 6 and 4 Comparing 5 and 4 *** Just set pivot: swapped 6 4 [1, 2, 3, 4, 5, 6, 7, 9, 8] Array is [5, 6] Comparing 5 and 6 --> swapped 5 5 [5, 6] *** Just set pivot: swapped 6 6 [1, 2, 3, 4, 5, 6, 7, 9, 8] Array is [9, 8] Comparing 9 and 8 *** Just set pivot: swapped 9 8 [1, 2, 3, 4, 5, 6, 7, 8, 9] Sorted array is: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.