Quick Sort

The popular exchange sort mechanisms are Mean sort, Quick Sort and BSort and Quick sort is the most simple one. Quick sort is most applicable exchange sorting technique for practical applications since it uses relatively less time-space resources.

Lets illustrate finding Order of a Quick sort algorithm in C. Lets start with the below list of numbers –

Numbers list and set up before sorting :

Complete steps for Quick sort is illustrated below in detail – 

Algorithm for Quick Sort

Step 1: Set any element  X[i] = a (usually first element) of the inputted file as a down pointer ‘d’ and the last element as the ‘up’ pointer

Step 2: Increase the down pointer repeatedly until any X[i] > a

Step 3: Decrease the up pointer repeatedly until any X[i] < a

Step 4: If up > down, interchange X[d] and X[‘up’] values

Step 5: Repeat the process until up <= d

Step 6: Now ‘a’ is in its proper position in the original file. Now, we have two sub files on the left and right of ‘a’, which may or may not be sorted

Step 7: Repeat steps 1 to 6 for thee sub files until the whole file is in a sorted form

Efficiency of Quick sort

The total number of comparisons made in Quick sort for all the ‘m’ sub files formed is ,

n + 2xn/2 + 4xn/4 + 5xn/5 …… nxn/n = n₁ + n₂ + n₃ + ……. n_{m = n + m}

i.e., Quick sort is of the order O(n+m). Now, if n = 2^m so that log₂n = m,
Order of quick sort = O(nlog₂n)