Page 1 of 1

QuickSort Tutorial (with a complete quicksort module) Rate Topic: ****- 2 Votes

#1 csmanoj  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 10
  • View blog
  • Posts: 150
  • Joined: 06-August 07

Post icon  Posted 08 August 2007 - 11:18 AM

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.

#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 August 2007 - 10:56 AM


Is This A Good Question/Topic? 2
  • +

Replies To: QuickSort Tutorial

#2 banc4  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 16-September 07

Posted 16 September 2007 - 11:41 AM

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



#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)


Was This Post Helpful? 1
  • +
  • -

#3 ibaraku  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 190
  • Joined: 12-May 07

Posted 10 April 2008 - 06:57 PM

Extremely well explained tutorial!!!
have you considered writing one for counting and radix sort???
Was This Post Helpful? 0
  • +
  • -

#4 cmaster  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 18-November 08

Posted 05 May 2009 - 12:27 AM

Cool tutorial. One also can check check this link: Illustrated quicksort explanation with implementations in Java and C++.
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Deepak*


Reputation:

Posted 08 September 2010 - 04:36 AM

Great post! The explanation was so clear and concise. Thanks for this!
Was This Post Helpful? 0

#6 animecrazy  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 22
  • Joined: 22-May 10

Posted 02 November 2010 - 05:24 AM

Really nice tutorial.....CHEERS!!
Was This Post Helpful? 0
  • +
  • -

#7 Blueorb  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 17
  • Joined: 03-July 10

Posted 15 February 2011 - 09:08 AM

I don't have the time to read your entire post at this time. But from what I can tell you're using a concept I learned called a Bubble Sort Algorithm.

Please excuse me if I'm completely off topic.

If you are simply sorting numbers, I would use the following code:

/***************************************************************
----------------------------------------------------------------
  Written by: Blueorb                                          |
----------------------------------------------------------------
  This program sorts the values of a one-dimensional array     |
  in ascending order using the Bubble Sort Algorithm.          |
----------------------------------------------------------------
***************************************************************/

#include <iostream>	// Include Input/Output stream
using std::cout;	// Use cout.
using std::endl;	// Use endl.

#include <iomanip>	// Include string manipulation library
using std::setw;	// Use setw.

#include "data.h";	// Include array, array size, and array definition.

// Begin main function execution
int main()
{
	// Declarations
	int swaps = 0;
	int totalSwaps = 0;
	int totalPasses = 0;
        const int arraySize = 12;

	int a[ arraySize ] = { 0, 1, 3, 35, 2, 4, 6, 10, 15, 4, 17, 35};

	cout << "Original array values" << endl;

	// Output the original array values
	for( int i = 0; i < arraySize; i++ )
		cout << setw( 4 ) << a[ i ];

	cout << "\n\n";

	// Loop to determine amount of passes
	for( int i = 0; i < arraySize; i++ )
	{
		// Reset variable swaps to zero
		swaps = 0;

		// Bubble Sort Algorithm
		// Sort numbers in ascending order
		for( int j = 1; j < arraySize - i; j++ )
		{
			// Keep a copy of the elements being compared
			int previousElement = a[ j - 1 ];
			int currentElement = a[ j ];

			// Swap values if they're in wrong order
			if( previousElement > currentElement )
			{
				a[ j - 1 ] = currentElement;
				a[ j ] = previousElement;

				swaps++;
			}
		}

		cout << "Array after bubble sort pass " << i + 1 << endl;

		// Display values after each pass
		for( int k = 0; k < arraySize; k++ )
			cout << setw( 4 ) << a[ k ];

		cout << "\n\n";

		// Keeps track of the amount of swaps and passes
		totalSwaps += swaps;
		totalPasses++;

		// If no swaps were made in the last pass,
		// no need to continue the loop. Sorting complete.
		if( swaps == 0 )
			break;
	}

	// Display some statistics to the user
	cout << "-----------------------------------------------------------------\n";
	cout << "Total Swaps: " << totalSwaps << endl;
	cout << "Total Passes: " << totalPasses << "\n\n";

	system("pause");

	// Successful program termination
	return 0;
} // End main functions execution




Again this is if you're sorting numbers, it's a quick and reliable method.
Let me know what you think.

Blueorb

This post has been edited by Blueorb: 15 February 2011 - 09:11 AM

Was This Post Helpful? 0
  • +
  • -

#8 markkenzy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 11-November 10

Posted 15 April 2011 - 09:14 PM

I wonder if the performance of quicksort will be better than bubble sort or not.... Please tell me about this! It turns out that quick sort require many "subfunction" and fairly many line of code comparing to a few line to accomplish bubblesort.... If I input 10 9 8 7 6 5 4 3 2 1, and then it shows me that swap() occur ..18 times. A lots!
Was This Post Helpful? 0
  • +
  • -

#9 MoErAe  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 24-August 08

Posted 07 May 2011 - 02:12 PM

View Postmarkkenzy, on 15 April 2011 - 09:14 PM, said:

I wonder if the performance of quicksort will be better than bubble sort or not.... Please tell me about this! It turns out that quick sort require many "subfunction" and fairly many line of code comparing to a few line to accomplish bubblesort.... If I input 10 9 8 7 6 5 4 3 2 1, and then it shows me that swap() occur ..18 times. A lots!


In real world applications the quicksort is considerably faster than bubble sort. Your input would be an example of a worst case scenario, giving O(n^2), however the average case performance is O(n log n)! If you want to go even faster, look at heap sort. Heap sort exhibits O(n log n) performance even in the worst case scenario - although it isn't considered a very stable algorithm, so you probably shouldn't use it for value based data.
Was This Post Helpful? 0
  • +
  • -

#10 nwaioalb99  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 01-May 11

Posted 18 May 2011 - 09:49 PM

Thanks a lot of the very nice information.
In c++ have so many sorts like quick sort,bubble sort,radix sort.
Which sort is easy?

This post has been edited by nwaioalb99: 18 May 2011 - 09:49 PM

Was This Post Helpful? 0
  • +
  • -

#11 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 452
  • View blog
  • Posts: 857
  • Joined: 17-March 11

Posted 27 February 2012 - 04:57 PM

For those looking for a more modern, generic C++ implementation with an interface akin to std::sort, consider:

C++11
#include <algorithm>
template <class Iterator>
void quicksort(Iterator begin, Iterator end) {
    if (std::distance(begin, end) <= 1) return;
    auto pivot = *begin;
    auto partition_it = std::partition(begin, end, 
        [&](const decltype(pivot)& x) {
            return (x < pivot);
        });
    quicksort(begin, partition_it);
    while(partition_it != end && *partition_it == pivot) 
        ++partition_it;
    quicksort(partition_it, end);
}



C++98/03 (without the lambda function and auto)
#include <algorithm>

template <class Iterator>
void quicksort(Iterator begin, Iterator end) {
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    if (std::distance(begin, end) <= 1) return;
    value_type pivot = *begin;
    Iterator partition_it = std::partition(begin, end, 
        std::bind2nd(std::less<value_type>(), pivot));
    quicksort(begin, partition_it);
    while(partition_it != end && *partition_it == pivot) 
        ++partition_it;
    quicksort(partition_it, end);
}



These are fully functional, efficient, in-place quicksort implementations working on stl containers as well as arrays containing any type that is less-than-comparable.


If you read these algorithms, you'll notice that I use std::partition to do the heavy lifting. A custom partition function might look something like this:

template <class Iterator, class Pred>
Iterator partition(Iterator left, Iterator right, Pred p) {
    if (left == right) return left;
    --right;
    while (left <= right) {
        if (p(*left)) {
            ++left;
        } else {
            std::swap(*left, *right);
            --right;
        }
    }
    return left;
}


This post has been edited by Karel-Lodewijk: 16 March 2012 - 08:04 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1