Suppose you have an array A[0.. 15] with 16 keys as follows: 27 1 828 1 84590452

Question

Suppose you have an array A[0.. 15] with 16 keys as follows: 27 1 828 1 845904523. So A[0]=2, A[ 1]=7, A[2]= 1, and so on. Apply the randomized Quicksort algorithm adapted to handle equal keys, as in Homework # 4. Assume the following random choices for the pivot and pivot-index: 8 (index 7); 4 (index 5); 1 (index 2); 3 (index 4); 2 (index 5) Show the result of each partitioning step together with the number of comparisons so far, that is show the array A[0 .. 15] after the partitioning step and the exact number of key comparisons so far; After the last partitioning step show the final array A[ 0 ..15] and the exact total number of key comparisons.

Explanation / Answer

# of comparisons: 22
# of swaps: 72
Total number of operations: 94
[0, 1, 1, 2, 7, 3, 4, 5, 2, 4, 5, 2, 8, 9, 8, 8]
# of comparisons: 22
# of swaps: 72
Total number of operations: 94
[0, 1, 1, 2, 7, 3, 4, 5, 2, 4, 5, 2, 8, 9, 8, 8]
# of comparisons: 22
# of swaps: 72
Total number of operations: 94
[0, 1, 1, 2, 7, 3, 4, 5, 2, 4, 5, 2, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 40
# of swaps: 134
Total number of operations: 174
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 42
# of swaps: 142
Total number of operations: 184
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 42
# of swaps: 142
Total number of operations: 184
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 42
# of swaps: 142
Total number of operations: 184
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 42
# of swaps: 142
Total number of operations: 184
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 42
# of swaps: 142
Total number of operations: 184
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 9, 8, 8]
# of comparisons: 44
# of swaps: 150
Total number of operations: 194
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 9, 8]
# of comparisons: 47
# of swaps: 161
Total number of operations: 208
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 8, 9]
# of comparisons: 47
# of swaps: 161
Total number of operations: 208
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 8, 9]
# of comparisons: 47
# of swaps: 161
Total number of operations: 208
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 8, 9]
# of comparisons: 47
# of swaps: 161
Total number of operations: 208
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 8, 9]
# of comparisons: 47
# of swaps: 161
Total number of operations: 208
[0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 8, 8, 8, 9]

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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