Quicksort (C++)

 NEW!  Quicksort (C++/ Java/ C/ Prolog/ javaScript)

quickSort.cpp

#include <iostream>

void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);

using namespace std;

int main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int);

    cout << "Size of test array :"  << N << endl;

    cout << "Before sorting : " << endl;
    print(test, N);

    quickSort(test, 0, N-1);

    cout << endl << endl << "After sorting : " << endl;
    print(test, N);
    
    return 0;
}

/**
 * Quicksort.
 * @param a - The array to be sorted.
 * @param first - The start of the sequence to be sorted.
 * @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

    if(first < last)
    {
        pivotElement = pivot(a, first, last);
        quickSort(a, first, pivotElement-1);
        quickSort(a, pivotElement+1, last);
    }
}

/**
 * Find and return the index of pivot element.
 * @param a - The array.
 * @param first - The start of the sequence.
 * @param last - The end of the sequence.
 * @return - the pivot element
*/
int pivot(int a[], int first, int last) 
{
    int  p = first;
    int pivotElement = a[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        /* If you want to sort the list in the other order, change "<=" to ">" */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }

    swap(a[p], a[first]);

    return p;
}


/**
 * Swap the parameters.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

/**
 * Swap the parameters without a temp variable.
 * Warning! Prone to overflow/underflow.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swapNoTemp(int& a, int& b)
{
    a -= b;
    b += a;// b gets the original value of a
    a = (b - a);// a gets the original value of b
}

/**
 * Print an array.
 * @param a - The array.
 * @param N - The size of the array.
*/
void print(int a[], const int& N)
{
    for(int i = 0 ; i < N ; i++)
        cout << "array[" << i << "] = " << a[i] << endl;
} 

This code was developed by me, G. Samaras.

Notice, that I used as little C++ as possible, so that one can easy interchange between C and C++.
Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

15 thoughts on “Quicksort (C++)

    • Efficient in terms of speed? Of course not! This code is for demonstration, for letting others understand the algorithm. First you learn and then you optimize. However, if you wish to share with us an efficient version, feel free.🙂

  1. Thanks for sharing the code.

    Here’s a version of swapNoTemp with no overflow😉

    void swapNoTemp(int& a, int& b)
    {
    a ^= b;
    b ^= a;
    a ^= b;
    }

  2. Can you please explain me the use of the line sizeof(test)/sizeof(int) to get the size. Why cant we fix N as 10 directly i.e., N=10because the size of the array is 10

    • We do that so that the size will be assigned automatically. So if the size of the array is changed, we won’t have to change that line. If we had a pre-defined value (like 10 or 8), we would have to change it every time we had more/less elements in the array. Is it more clear now?

    • Well Shuvam, the size of the array is fixed. The order of the elements (i.e. the position of every element) is not fixed. In this example alone, it is OK to set the size manually, to the value 8. The reason the code is written this way is this: Assume you copy-paste the code to your editor and you add some elements the array, let’s say two elements. Then you would have to change 8 to 10, since the size of the array is increased by two. With the current code, you do not have to do that, since the size will be computed on runtime. Is my answer better now?🙂 If not, let me know!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s