Quick Sort

Quick sort applies the divide and conquer paradigm. Let x be an array and n the number of elements to be sorted. Choose an element a from a specific position within the array. Suppose that the elements of x are partitioned so that a is placed into position j and the following conditions hold:

• Each of the elements in positions 0 through j-1 is less than or eual to a.
• Each of the elements in position j+1 through n-1 is greater than or equal to a.

If this conditions holds for a particular a and j, a is the jth smallest element of x, so that a remains in position j when the array is completely sorted.If foregoing process is repeated with the subarays x[0] through x[j-1] and x[j+1] through x[n-1] and any subarrays created by the process in successive iterations, the final result is a sorted file.

Below is procedure for quicksort.

void QuickSort(int x[],int lb,int ub)
{
    int j;
    if(lb>=ub)
        return; /* array is sorted */
   
    partition(x,lb,ub,&j);
    /* partition the elements of the subarray such that one of the elements is now at position x[j] and
     * x[i] <= x[j] for lb <=i < j
     * x[i] >= x[j] for j < i <=ub
     */
   
    QuickSort(x,lb,j-1);     /* sort the subarray between positions lb and j-1 */
    QuickSort(x,j+1,ub);    /* sort the subarray between positions j+1 and ub */
}

Now we need to implement the procedure partition.The object of partition is to allow a specific element to find its proper position with respect to the others in the subarray.
For this we need to consider a pivot element which will be at its proper position after partition. For time being consider pivot element a=x[lb]. Two pointers, up and down are initialized to the upper and lower bounds of the subarray, respectively. At any point during execution, each element in a position above up is greater than or equal to a, and each element in a position below down is less than or equal to a. The two pointers are moved towards each other in following fashion.

• Repeatedly increase the pointer down by one position until x[down] > a.
• Repeatedly decrease the pointer up by one position until x[up] <= a.
• if up > down, interchange x[down] with x[up]

The process is repeated until the condition in last step fails(up<=down), at which point x[up] is interchanged with x[lb](which equals pivot element a), whose final position was sought, and j is set to up.

Below is procedure partition.

void partition(int x[],int lb, int ub, int *pj)
{
    int a, down, temp, up;

    a=x[lb];
    up=ub;
    down=lb;

    while(down < up) {
        while(x[down] <= a && down < up)
            down++;
        while(x[up] > a)
            up--;
        if(down < up) {
            temp = x[down];
            x[down] = x[up];
            x[up] = temp;
        }
    }
    x[lb] = x[up];
    x[up] = a;
    *pj = up;
}
   
Average Time Complexity of quick sort is O(nlogn). Its worst case is when the array is sorted and time complexity in that case is O(n2). It requires O(logn) additional space for the stack.

It is possible to speed up quick sort for sorted files by choosing a random elements of each subfile as the pivot element.If file is nearly sorted this might be a good strategy(may choose a middle element as pivot element). However if nothing is known above the file, such a strategy doesnot improve the worst case behaviour.

Lets see quick sort example.If an array is given as
    25 57 48 37 12 92 86 33
pivot element a = 25. so after 1st iteratin, 25 will be at its proper postion, and the resulting array will be.
    12 25 57 48 37 92 86 33
it will divide the array into two subparts (12) and ( 57 48 37 92 86 33) which needs to be sorted.
proceeding in this way following will be output after successive iterations.
    12 25 (48 37 33 57 92 86)
    12 25 (48 37 33) 57(92 86)
    12 25 (37 33) 48 57 (92 86)
    12 25 (33) 37 48 57 (92 86)
    12 25 33 37 48 57 (92 86)
    12 25 33 37 48 57 (86) 92
    12 25 33 37 48 57 86 92