Exercise on QuickSort Suppose that the result of the shuffle in Algorithm 2.5 is

Question

Exercise on QuickSort

Suppose that the result of the shuffle in Algorithm 2.5 is P A R T I O N E D H F L. Show the result of the first call on partition() by giving the contents of the array after each exchange, as in the trace on p. 291.

al i j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 initial values 0 16 KRATELEP UIMQCXOS scan left, scan right i 12 KRATELE PUI M XOS exchange i 12K CATELEP UI MOR XOS scan left, scan right 39K CAT ELEPU IMQ R XOS exchange 39K CAIETE PUTM QR XOS scan left, scan right 5 6 KCA I ELEP UTM QR XOS exchange 56 KCA IEELP UTM QR XOS scan left, scan right 6 5 K-CAI E EL PUT M Q R XOS final exchange 6 5 ECA I EKLP UTM QR XOS result 5 E CAI E K L P UTM QR XOS Partitioning trace (array contents before and after each exchange)

Explanation / Answer

                 i    j   0 1 2 3 4 5 6 7 8 9 10 11
initial value    0    11 P A R T I O N E D H F   L
                 2    11 P A L T I O N E D H F   R
                 3    10 P A L F I O N E D H T   R
                      9   H A L F I O N E D P T   R

Here the pivot is P. So we scan from left--till we reach an entry which is bigger
than P, similarly we scan from right untill we reach an entry which is smaller than
the pivot.Then we exchange the entries accordingly.As we cross the index or meeet
at some point at last we will compare the last element with the pivot itself and
exchange their position accordingly.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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