C++ Tutorials

Welcome to Dream.In.Code
	Become a C++ Expert! Join 300,400 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,586 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a C++ Expert

QuickSort Tutorial

QuickSort Tutorial, (with a complete quicksort module)

Options

csmanoj

8 Aug, 2007 - 10:18 AM

Post #1

The core concept of quick sorting is very simple. Given a list, a ‘pivot’ is chosen (any arbitrary element from the list). Now all elements of the list, greater than the pivot are moved to the right. And all elements of the list, smaller than the pivot are moved to the left. Thus we form two unsorted lists. One list is on the left of the pivot, consisting of elements smaller than the pivot. Another list is to the right of the pivot, consisting of elements greater than the list. But what is important here, is that the pivot element has found its place. Consider this list...

5 3 7 2 1 6 -The unsorted list

If we take ‘5’ as the pivot, the list is rearranged as follows...

3 2 1 5 7 6 - After arranging the elements around the pivot
1 2 3 5 6 7 -Sorted list (which is our target)

Observe that, even though the elements before and after ‘5’ are not sorted, ‘5’ has found the place it should be after the sorting happens. That is, now we have two unsorted lists and one element in the right place. All we have to do is do the same thing recursively for those two unsorted lists (3, 2, 1 and 7, 6) until there are no unsorted lists and all elements find their right place. This tutorial will not discuss recursion. It is discussed here.

We will try to implement in a C++ program which quick sorts an array. The program contains the following functions...

• Quicksort() which quick sorts a given array
• Split() which splits the array into two parts, one with smaller elements than the pivot and another with larger elements than the pivot

Quicksort() takes an array, the index of the first element and the index of the last element as arguments. This is necessary because, we need to do recursive calls to Quicksort() with subsections of the list. In the above example we first do Quicksort() for the entire list. Then we do Quicksort() for the first three elements. Then we do Quicksort() for the last two elements. For such reasons, Quicksort() will need the first and last element indexes. We must have in mind that, Quicksort() returns without making further recursions, when there is only one element i.e., first and last are the same. It is the responsibility of Quicksort() to choose a pivot. In our design, we will just consider the leftmost element of the list to be the pivot.

Split() takes an array, the pivot, the index of the first element and the index of the last element as arguments. There are many techniques to achieve this split. We will use the same technique that C.A.R.Hoare (the inventor of the quick sort algorithm) suggested. Split() shuttles the pivot element back and forth repeatedly until it zeroes in at the required place. Then Split() returns the ‘split-point’ i.e., the position where the pivot is. Consider the following example to understand this well.

12 15 5 26 30 8 17 23 33

12 is the pivot. The Split() function, starts from the rightmost element ‘33’, and compares it with the pivot. 33 is larger then the pivot 12. So 12 should be at the left of 33 (because lesser numbers come left to pivot and larger numbers go right to pivot). So, it compares the next element ‘23’ with the pivot. It is again larger then the pivot. ‘12’ should be to the left of ‘23’. So, it compares the next element ‘17’ with the pivot. Yet again, it is larger than the pivot. ‘12’ should be to the left of ‘17’ too. So, it compares the next element ‘8’ with the pivot. ‘8’ is lesser than the pivot. ‘12’ should be to the right of ‘8’. ‘12’ and ‘8’ are swapped. Remember that it is not essential that anything is sorted yet, our only goal is to put all numbers larger than ‘12’ to the right and all numbers lesser than ‘12’ to the left. Now the list is ordered as follows...

8 15 5 26 30 12 17 23 33

The underlined numbers need not be considered again, because they are already pushed to their correct sides. ‘8’ is to the left and ‘17’, ‘23’ and ‘33’ are to the right. Now Split() starts again from the leftmost element ‘15’. But this time it searches for an element larger than ‘12’. ‘12’ and ‘15’ are compared. ‘15’ is larger then the pivot ‘12’. It should be to the right of ‘12’. They are swapped. Now the list looks like this...

8 12 5 26 30 15 17 23 33

Again, Split() starts from the rightmost element ‘30’ and compares it with pivot ‘12’. ‘30’ is larger and is already in its side (right of 12). The next element ‘26’ is also larger than ‘12’ and thus on the correct side. But the next element ‘5’ is lesser than ‘12’. It should be on the left side of ‘12’. So, they are swapped. Now the list is...

8 5 12 26 30 15 17 23 33

There is no more elements to be compared with the pivot (you can see that from the fact that we have underlined all the other numbers). Split() has finished its job i.e., 12 has found its position on the sorted list. Split() returns the split-point which is nothing but the current position of 12.

Quicksort() uses this returned value to determine the boundaries of the two unsorted lists obtained namely, 0-1 and 3-8 because the split-point is 2. Quicksort() makes two recursive calls to itself for these two lists. With each call to Quicksort(), one element finds its position in the sorted list. So finally, all elements find their positions. That is the list gets sorted.

The following code implements the quick sort technique in a C++ program. I recommend you view this code in your own editor, because it looks best in a monospaced font. There are two PrintArray() functions inside the SplitArray() function which are commented out. You can uncomment these functions to observe the array in each step of the process.

CODE

#include <iostream>
using namespace std;

#define ARRAY_SIZE 5                                  //change the array size here

void PrintArray(int* array, int n);
void QuickSort(int* array, int startIndex, int endIndex);
int SplitArray(int* array, int pivotValue, int startIndex, int endIndex);
void swap(int &a, int &b);

int main(void)
{
    int array[ARRAY_SIZE];
    int i;

    for( i = 0; i < ARRAY_SIZE; i++)                //array elements input
    {
         cout<<"Enter an integer : ";
         cin>>array[i];
    }

    cout<<endl<<"The list you input is : "<<endl;
    PrintArray(array, ARRAY_SIZE);
    QuickSort(array,0,ARRAY_SIZE - 1);                //sort array from first to last element
    cout<<endl<<"The list has been sorted, now it is : "<<endl;
    PrintArray(array, ARRAY_SIZE);

    cin.get();
    cin.get();
    return 0;
}

/* This function swaps two numbers
   Arguments :
             a, b - the numbers to be swapped
   */
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

/* This function prints an array.
   Arguments :
             array - the array to be printed
             n - number of elements in the array
   */
void PrintArray(int* array, int n)
{
    int i;

    for( i = 0; i < n; i++) cout<<array[i]<<'\t';
}

/* This function does the quicksort
   Arguments :
             array - the array to be sorted
             startIndex - index of the first element of the section
             endIndex - index of the last element of the section
   */
void QuickSort(int* array, int startIndex, int endIndex)
{
    int pivot = array[startIndex];                    //pivot element is the leftmost element
    int splitPoint;

    if(endIndex > startIndex)                         //if they are equal, it means there is
                                                      //only one element and quicksort's job
                                                      //here is finished
    {
        splitPoint = SplitArray(array, pivot, startIndex, endIndex);
                                                      //SplitArray() returns the position where
                                                      //pivot belongs to
        array[splitPoint] = pivot;
        QuickSort(array, startIndex, splitPoint-1);   //Quick sort first half
        QuickSort(array, splitPoint+1, endIndex);     //Quick sort second half
    }
}

/* This function splits the array around the pivot
   Arguments :
             array - the array to be split
             pivot - pivot element whose position will be returned
             startIndex - index of the first element of the section
             endIndex - index of the last element of the section
   Returns :
           the position of the pivot
   */
int SplitArray(int* array, int pivot, int startIndex, int endIndex)
{
    int leftBoundary = startIndex;
    int rightBoundary = endIndex;

    while(leftBoundary < rightBoundary)               //shuttle pivot until the boundaries meet
    {
         while( pivot < array[rightBoundary]          //keep moving until a lesser element is found
                && rightBoundary > leftBoundary)      //or until the leftBoundary is reached
         {
              rightBoundary--;                        //move left
         }
         swap(array[leftBoundary], array[rightBoundary]);
         //PrintArray(array, ARRAY_SIZE);             //Uncomment this line for study

         while( pivot >= array[leftBoundary]          //keep moving until a greater or equal element is found
                && leftBoundary < rightBoundary)      //or until the rightBoundary is reached
         {
              leftBoundary++;                         //move right
         }
         swap(array[rightBoundary], array[leftBoundary]);
         //PrintArray(array, ARRAY_SIZE);             //Uncomment this line for study
    }
    return leftBoundary;                              //leftBoundary is the split point because
                                                      //the above while loop exits only when
                                                      //leftBoundary and rightBoundary are equal
}

Remember that this SplitArray() function is only one of the many ways this can be done. Don't fail to think about other ways of doing this.

The above tutorial discusses sorting in ascending order using quicksort technique. As exercises try doing a quick sort program, that sorts in the descending order. Programmers who have a bit more confidence can try a quicksort module for linked lists. The underlying principle is the same - divide and conquer.

Comment and Criticize please.

This post has been edited by csmanoj: 10 Aug, 2007 - 09:56 AM

Register to Make This Ad Go Away!

banc4

16 Sep, 2007 - 10:41 AM

Post #2

My problem is with validating the user input. I am trying to use the getInput function without success. Any help is appreciated.

CODE

#include "stdafx.h"
#include <iostream>
using namespace std;

#define ARRAY_SIZE 4  //array size

void PrintArray(int* array, int n);
void ArraySort(int* array, int startIndex, int endIndex);
int SplitArray(int* array, int pivotValue, int startIndex, int endIndex);
void exchange(int &a, int &b);

#include <limits>

bool getInput(int &input)    //function to validate user input

{
    cin >> input;

if (cin.fail())

{

cin.clear();

cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

return false;

}

else

{

// check if input contains chars; if so, make the input invalid

char c = cin.peek();

if (c != '\n')

{

cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

return false;

}

}

return true;

}//end of function

int main(void)
{
    int temp;//validation code
    bool validInput = false;//validation code

    int array[ARRAY_SIZE];
    int i;

    for( i = 0; i < ARRAY_SIZE; i++)                //array elements input
    {
        cout<<"Enter an integer : ";
        //cin>>array[i];
        //validation code added in place of cin>>array[i];
        while (!validInput)

        {

        cout << "Please enter a number: ";

        validInput = getInput(temp);  // Use the getInput function to accept and validate user input

        }//end of added validation code
    }//end of for



    cout<<endl<<"Your list as entered : "<<endl;
    PrintArray(array, ARRAY_SIZE);                    //print array as entered
    ArraySort(array,0,ARRAY_SIZE - 1);                //sort array from first to last element
    cout<<endl<<"Your list in ascending order : "<<endl;
    PrintArray(array, ARRAY_SIZE);                    //print array in ascending order



    cin.get();
    cin.get();
    return 0;

}
void exchange(int &a, int &b)//switches two numbers
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void PrintArray(int* array, int n)    //prints the array
{
    int i;

    for( i = 0; i < n; i++) cout<<array[i]<< endl;
}

void ArraySort(int* array, int startIndex, int endIndex)//array sorting
{
    int pivot = array[startIndex];                    //pivot element is the leftmost element
    int splitPoint;

    if(endIndex > startIndex)                         //if they are equal sort is finished
    {
        splitPoint = SplitArray(array, pivot, startIndex, endIndex); //returns positon where pivot belongs

        array[splitPoint] = pivot;
        ArraySort(array, startIndex, splitPoint-1);   // sort first half
        ArraySort(array, splitPoint+1, endIndex);     // sort second half
    }
}

int SplitArray(int* array, int pivot, int startIndex, int endIndex)//splits array around pivot returns pivot position
{
    int leftBoundary = startIndex;
    int rightBoundary = endIndex;

    while(leftBoundary < rightBoundary)               //move pivot until the boundaries meet
    {
         while( pivot < array[rightBoundary]          //keep moving until a lesser element is found
                && rightBoundary > leftBoundary)      //or until the leftBoundary is reached
         {
              rightBoundary--;                        //move left
         }
         exchange(array[leftBoundary], array[rightBoundary]);

         while( pivot >= array[leftBoundary]          //keep moving until a greater or equal element is found
                && leftBoundary < rightBoundary)      //or until the rightBoundary is reached
         {
              leftBoundary++;                         //move right
         }
         exchange(array[rightBoundary], array[leftBoundary]);
     }
    return leftBoundary;                              //exits when leftBoundary and rightBoundary are equal
}

Attached File(s)