The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls.
Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.)
Why or why not?
Solution:In the first place,whatever I put here is only my approach to solve this problem and much better solution might exist.Now getting on to the solution..
In linked list implementation,we simply modify the pointers so that we end up with 3 lists.One list L1 to contain all the keys less than pivot ,one L2 with keys equal to the pivot and the other L3 with keys greater than pivot.Hence what we require is only an additional head pointer which points to this list L3 containing all elements equal to the pivot.SO we do not require any significant additional memory !!
But this is not the case with array implementation wherein we are confronted by difficulties arising from fixed size of array .If at all we want to maintain a list of keys equal to the pivot, then we need to maintain a separate array and also need to remove all those from the original array,which means a herder's task.
We will do it in much simpler way.Whenever,a duplicate entry of pivot is encountered by the left pointer,swap it with some element ,smaller than pivot and positioned to its left.Hence we move all the pivots encountered by the left pointer to the left extreme of the array. Similarly move all the pivots encountered by the right pointer to the right side of the array.
Now we have all the elements equal to the pivot on either extreme ends of the array.
In the middle,we have remaining 2 sub-arrays.Now the array looks like this
L2-left L1 L3 L2-right
Now get all these pivot elements in the left extreme (L2-left) to occupy the positions preceding L3 by swapping with those elements on the right portion of the first list L1.Similarly do swaps to get L2-right next to L2-Left by swapping its elements with those elements on the left portion of 3rd list L3.Now we have array in the form L1,L2,L3 where L2-left and L2-right are joined into one.
Now we can recursively sort L2-left and L2-right.
I am also putting the code of normal array based quicksort and this modified version ,so that once can verify it.
int leftpivotcounter=0; //global variable
int rightpivotcounter=0; //global variable
// these 2 are the only additional space used to accomplish the task in modified quicksort.
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void normal_quicksort(int *arr,int left,int right)
{
if(left>=right)
return;
else if(right-left==1)
{
if(arr[left]>arr[right])
swap(arr+left,arr+right);
}
else
{
swap(arr+(left+right)/2,arr+right);
int rpos=right,lpos=left;
int pivot=arr[right--];
while(left <right)
{
while(left <rpos &&arr[left]<=pivot )
left++;
while(right>=lpos &&arr[right]>=pivot )
right--;
if(left <=right )
{
swap(arr+left,arr+right);
}
else if (left > right )
{
swap(arr+right+1,arr+rpos);
partition(arr,lpos,right);
partition(arr,right+2,rpos);
break;
}
}
}
}
void modified_quicksort(int *arr,int left,int right)
{
if(left>=right)
return;
else if(right-left==1)
{
if(arr[left]>arr[right])
swap(arr+left,arr+right);
}
else
{
swap(arr+(left+right)/2,arr+right);
int rpos=right,lpos=left;
leftpivotcounter=lpos-1;
rightpivotcounter=rpos;
int pivot=arr[right--];
while(left <right)
{
while(left <rpos &&arr[left]<=pivot )
{
if(arr[left]==pivot)
{
leftpivotcounter++;
swap(arr+leftpivotcounter,arr+left);
}
left++;
}
while(right>=lpos &&arr[right]>=pivot )
{
if(arr[right]==pivot)
{
rightpivotcounter--;
swap(arr+rightpivotcounter,arr+right);
}
right--;
}
if(left <=right )
{
swap(arr+left,arr+right);
}
else if (left > right )
{
swap(arr+right+1,arr+rpos);
for(int i=0;(i+lpos<=leftpivotcounter) &&((2*i) <right-lpos);i++)
{
swap(arr+lpos+i,arr+right-i);
}
for(int i=0;(rpos-i-1>=rightpivotcounter) && (rpos > right+3+2*i) ;i++)
{
swap(arr+rpos-1-i,arr+right+2+i);
}
partition(arr,lpos,right-(leftpivotcounter-lpos+1));
partition(arr,right+2+(rpos-rightpivotcounter),rpos);
break;
}
}
}
}
Click here for more questions
No comments:
Post a Comment