Illustrate Quick sort to sort the following data You need to

Illustrate Quick sort to sort the following data. (You need to sort alphabetically, Assume that numerical value of the character according to their position in the alphabet i.e., Q = 17, U = 21, I = 9, C = 3, K = 11, S = 19, O = 15, R = 18)

Solution

Q U I C K S O R

Let Q be Pivot Item and index of Q is Pivot.

low=min=0    high=max=7 (last Index)

           As U is big than Q low=1    (1 Comparison)

As O is less than Q high=6

                                                                                    (1 comparison and 1 swap)

Elements are Q O I C K S U R

S is big => low=5   K is small high=4 (total 6 comparisons)

Now low<high is violated therefore (1 comparison)

Now elements are K O I C Q S U R

Let K be pivot in array K O I C Q

low= 1 (1 comparison) high=3 (2 comparisons) è K C I O Q (1 swap)

low= 3 (2 comparisons) high=2(1 comparison) è I C K O Q (1 swap)

Let I be Pivot in I C

low= 1 (1 comparison) high=0 (2 comparisons) èC I (1 swap)

Let O be pivot in O Q

low= 1 (1 comparison) high=1 (2 comparisons) è O Q (0 swap)

Let S be pivot in S U R

low=1 (1 comparison) high=2 (1 comparison) èS R U (1 swap)

low=2 (1 comparison) high=1 (1 comparison) èR S U (1 swap)

Combining all we get C I K O Q R S U

Totally 25 Comparisons and 7 Swapping’s. This will be the run time.