A Generic Quicksort Implementation in C

This is one of the posts that I unluckily lost on 2011-04-09 and then recovered. The information may be very old. Or not.

As assignment for Data Structures and Algorithms course, we had to work with a modified version of the quicksort algorithm. It came obvious that for modifying a qsort you need to implement it

It is difficult to find a clear quicksort algorithm implemented, so I wrote it.

Here is the generic C implementation of the Quicksort Algorithm, which sorts an array in place, following the Divide And Conquer design.

int partition( int A[], int left, int right) {
    
    int pivot;
    pivot = A[right];
    
    while(1){
        while( A[right] &gt; pivot){
            right--;
        }
        while( A[left] &lt; pivot){
            left++;
        }
        if( left &lt; right ){
            swap(A,left,right);
            }else{
            return left;
        }
    }
}

void quicksort( int A[], int left, int right){
    int m;
    if( left &lt; right ) {
        m = partition( A, left, right);
        quicksort( A, left, m-1);
        quicksort( A, m+1, right);
    }
}

int partition( int A[], int left, int right) {

int pivot;

pivot = A[right];

while(1){

while( A[right] > pivot){

right--;

}

while( A[left] < pivot){

left++;

}

if( left < right ){

swap(A,left,right);

}else{

return left;

}

void quicksort( int A[], int left, int right){

int m;

if( left < right ) {

m = partition( A, left, right);

quicksort( A, left, m-1);

quicksort( A, m+1, right);

}

As you see, there is nothing optimized in this implementation. It just looks elegant and easy to be understood.
If you would like to have a more optimized version of this algorithm, take a look at this one.

A Generic Quicksort Implementation in C

dgraziotin

Leave a Reply Cancel reply

Categories