Posted 08 August 2007 - 11:18 AM
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
MultiQuote
| 