HERGHELEGIU

QUICK-SORT(A,p,q) – uses the divide et impera alghoritm

it separates the elements from p to q into 2 partitions from p to r and from r+1 to q
where all the elements from the first partition are smaller than the elements from the second one.

The worst running time is O(n^2) but on average is very efficient THETA(n log n)
For balanced partitioning 9 good and 1 bad -> O(n log n)


 
void QUICKSORT(A,p,r)
{
    if ( p < r )
    {
        q = PARTITION(A, p, r);
        QUICKSORT(A, p, q);
        QUICKSORT(A, q+1, r);
    }
}
 
 
int PARTITION(A, p, r) //- rearrange the A[p..r]
{
    x = A[p]; // pivot element
    i = p-1;
    j = r+1;
 
    while (true)
    {
        for( j--; j>=p && A[j] > x; j-- );
 
        for( i++; i<=r && A[i] < x; i++ );
 
        if ( i < j )
            exchange( A[i] , A[j] );
        else
            return j;
    }
}

 

To avoid the worst time of the algorithm use the randomize partition

 
int RANDOMIZED-PARTITION(A, p, r)
{
    i = RANDOM(p, r);
    exchange A[p]-A[i];
    return PARTITION(A, p, r);
}


Read more on Wikipedia