Quicksort -- Three way partition When implementing quicksort, if the array conta

Question

Quicksort -- Three way partition

When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three way comparisons as provided by the compareTo method.

Give an algorithm that performs a three way in place partition using only N-1 comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two way partitioning algorithm. (Hint: as i and j move toward each other, maintain five groups of elements as shown below):

EQUAL SMALL UNKNOWN LARGE EQUAL

i j

Explanation / Answer

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

The base case of the recursion is lists of size zero or one, which never need to be sorted.

CODE:

#include<iostream>
#include<stdlib.h>
using namespace std;
int Partition(int a[], int beg, int end)          //Function to Find Pivot Point
{
int p=beg, pivot=a[beg], loc;

for(loc=beg+1;loc<=end;loc++)
{
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;

p=p+1;
}
}
return p;
}

void QuickSort(int a[], int beg, int end)
{
if(beg<end)
{
int p=Partition(a,beg,end);                       //Calling Procedure to Find Pivot

QuickSort(a,beg,p-1);                             //Calls Itself (Recursion)
QuickSort(a,p+1,end);                          //Calls Itself (Recursion)
}
}

int main()
{
//clrscr();
int a[100],i,n,beg,end;

cout<<" ------- QUICK SORT ------- ";
cout<<"Enter the No. of Elements : ";
cin>>n;

for(i=0;i<n;i++)
{
cin>>a[i];
}
beg=0;
end=n-1;

QuickSort(a,beg,end);                              //Calling of QuickSort Function

cout<<" After Sorting : ";
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
//getch();
system("pause");
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.