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)