CODEWITHSUNDEEP
c++quicksortpartitioning
hjavan
hjavan

Reputation: 21

quicksort implementation with partitioning around the median in c++

I struggled to solve this issue by myself but it made me more confused. I look at those sample codes for quicksort that used the median to do partition on it, and I tried it on one sample array say A={1,8,4,6,7,10,11} and I did not get the correct partitioning. The code for partition is below:

void swap(int &x, int &y){
    int temp=x;
    x=y;
    y=temp;
 }
//
int partition(int arr[],int low,int high){
int pivot=arr[(low+high)/2];
while(low<=high){
   while(arr[low]<pivot) low++;
   while(arr[high]>pivot) high--;
   if(low<=high){
      swap(arr[low],arr[high]);
      low++;
      high--;
    }
 }
 return low;
}

For my example pivot is 6 so the code first swaps 8 and 6 in the array A ,and then stops. It does not put all smaller values than pivot=6 before that and large ones above. I guess the issue is we assume that we can always find two values from the left and right side of pivot to swap, but this example the right side is fine. Any comments or idea will be appreciated.
Just few updates: (1) my focus here is on the partition part of quick sort and I am aware of the following steps doing a recursive method.(2) I saw this methods in many links even in this website Quick Sort - Middle Pivot implementation strange behaviour (or in the "cracking the coding interview" book, page. 119 written in java)and they claim it works but I doubt it (I mean the partition part, it might somehow end up with a sorted array for any reason but a correct partition has to implemented such that all numbers that are less than the partitioning element come before all elements that are greater than it.) In my sample array A it ends up A={1,6,4,8,7,10,11} which is not a correct partition since 4 is after 6(our pivot).

Upvotes: 2

Views: 7134

Answers (1)

Jason
Jason

Reputation: 3917

There are some obvious bugs in your partition implementation. One of the bigger ones is that you don't re-compare the element you swap in.

When you partition in Quicksort, you only need to move elements larger than the pivot, after the pivot element. So, a simple implementation would be...

int partition(int arr[], int begin, int end) {

  int pivot = arr[begin + ((end - begin) / 2)];

  while (begin != end) {

    if (arr[begin] < pivot)
      begin++;
    else
      swap(arr[begin], arr[end--]);
  }

  return end;
}

Note, the complexity depends on the quality of the pivot, which is why a median would be ideal. However, this would require iterating over all of the elements O(n).

Keep in mind, picking the middle of the array won't always give a good pivot. There are a few strategies for picking a good pivot (randomizing, sample and median, and so on...).

Upvotes: 1

Related Questions