10. (10 points) You are running quicksort. List the comparisons between elements

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: 431658297

Explanation / 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

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.