Quick sorting

Today, we will discuss "quick sorting" one of the most efficient and widely used algorithm of sorting. The method is based on the "devide-and-conquer" approach. It is completed by recursion in the following 3 steps :

1. In the array of elements, choose any element a_p indexed by p;

2. Each element, less than or equal to a_p is placed to the left of a_p, otherwise - to the right. So that we have two subarrays {a_j} and {a_k} :

{a_j} <= [a_p] > {a_k}

3. If more than 2 elements are available in either subarray, launch the procedure recursively for such subarray .

Finally, we obtain completely sorted sequence of elements.

___

But, let us further look into the details :

Assume we have an array {a_i}, where i=0, ..., N . Randomly choose any element a_p indexed by p , and follow the 4 basic steps below :

1. Let i and j be the indexes pointing at the first and the last element of the array : a_i and a_j respectively, so that i=0 and j=N.

2. We will be increasing index i by 1 until we find an element a_i such that a_i >= a_p . Similarly, we will be decreasing j by 1 untill we find an element a_i <= a_p 3. if i <= j, swap elements a_i and a_j 4. while i <= j repeat steps 2 and 3 . For example, consider the following array having 7 elements a_0, ..., a_6 , where a_3=6 (remember elements are counted starting from 0) is the splitting element (circled in the Figure below), then :

By now, the array has been split into two parts : each element of part 1 is less than or equal to a_p = 6, while any element of the second part is greater than or equal to a_p. Therefore, at this stage, splitting has been done.

To recap, the pseudocode can be presented as follows.

quickSort(array a, a.size() ) {
     Select any element a_p (e.g. in the middle of array a);
  Split array {a} into two subarrays: to the left and to the right of a_p;
  If the subarray to the left of a_p contains more than 1 element, call quickSort for it;
  If the subarray to the right of a_p contains more than 1 element, call quickSort for it;
}

There are Theta(n) operations needed per each split. The depth of recursion is about log n, given that the array is being split in more or less equal parts. Therefore, total complexity is proven to be O(n log n).