Quick Sort

QuickSort, or Quick Sort, is an efficient method for sorting an array, discovered in 1960 by the British programmer C.A.R. Hoare. For a set of n arbitrary values, the algorithm performs O(n log n) comparisons, but in the worst case, it performs O(n^2) comparisons.

The algorithm is of the divide and conquer type; it sorts a sequence of the array (initially the entire array) as follows:

• choose a special element of the list, called the pivot
• arrange the elements of the list so that all elements to the left of the pivot are less than or equal to it, and all elements to the right of the pivot are greater than or equal to it;
• continue recursively with the sequence to the left of the pivot and with the one to the right of it.

The following C++ function sorts an array, passed as a parameter:

void QuickSort(int v[], int st, int dr)
    {
        if(st < dr)
        {
            // the pivot is initially v[st]
            int m = (st + dr) / 2;
            int aux = v[st];
            v[st] = v[m];
            v[m] = aux;
            int i = st, j = dr, d = 0;
            while(i < j)
            {
                if(v[i] > v[j])
                {
                    aux = v[i];
                    v[i] = v[j];
                    v[j] = aux;
                    d = 1 - d;
                }
                i += d;
                j -= 1 - d;
            }
            QuickSort(v, st, i - 1);
            QuickSort(v, i + 1, dr);
        }
    }

Observations:

• during pivoting:
• in each iteration, only one of the variables i and j changes: either i increases, or j decreases
• the pivot is the element with the index that does not change
• the above algorithm sorts the array in ascending order; for descending order, the algorithm is similar: by pivoting, the elements to the left of the pivot become greater than it, those to the right become smaller;
• the algorithm is faster the closer the lengths of the two sequences delimited by the pivot are (ideally equal);
• if the array is initially sorted in ascending or descending order, the algorithm's complexity becomes quadratic;
• certain methods of choosing the pivot can avoid this situation.