A Generic Quicksort Implementation in C

A

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] > 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.

About the author

dgraziotin

Dr. Daniel Graziotin is a senior researcher (Akademischer Rat) at the University of Stuttgart, Germany. His research interests include human, behavioral, and psychological aspects of empirical software engineering, studies of science, and open science. He is associate editor at the Journal of Open Research Software and academic editor at the Research Ideas and Outcomes (RIO) journal. Daniel was awarded an Alexander von Humboldt Fellowship for postdoctoral researchers in 2017, the European Design Award (bronze) in 2016, and the Data Journalism Award in 2015. He received his Ph.D. in computer science at the Free University of Bozen-Bolzano, Italy.

Add comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

By dgraziotin

About Author

dgraziotin

Dr. Daniel Graziotin is a senior researcher (Akademischer Rat) at the University of Stuttgart, Germany. His research interests include human, behavioral, and psychological aspects of empirical software engineering, studies of science, and open science. He is associate editor at the Journal of Open Research Software and academic editor at the Research Ideas and Outcomes (RIO) journal. Daniel was awarded an Alexander von Humboldt Fellowship for postdoctoral researchers in 2017, the European Design Award (bronze) in 2016, and the Data Journalism Award in 2015. He received his Ph.D. in computer science at the Free University of Bozen-Bolzano, Italy.