Quick Sort Implementation

Question

The following code for quicksort does not work, and I cannot figure out what is the reason.

#include <iostream> using namespace std; void exch(int a[],int i,int j){ int s=a[i]; a[i]=a[j]; a[j]=s; } int partition(int a[],int l,int h); void quick(int a[],int l,int h){ if (h<=l) return ; int j=partition(a,l,h); quick(a,l,j-1); quick(a,j+1,h); } int partition(int a[],int l,int h){ int i=l-1; int j=h; int v=a[l]; while(true){ while( a[++i]<v); while(a[--j]>v) if (j==i) break; if (i>=j) break; exch(a,i,j); } exch(a,i,h); return i; } int main(){ int a[]={12,43,13,5,8,10,11,9,20,17}; int n=sizeof(a)/sizeof(int); quick(a,0,n-1); for (int i=0;i<n;i++){ cout<<a[i]<<" "; } return 0; } 

He outputs

 5 8 9 11 10 17 12 20 13 43 

Answer 1

In your partition method, this should be

 int v = a[h]; 

and not

 int v = a[l]; 

[Update: I just checked the code with this change and it works correctly, outputting:

 5 8 9 10 11 12 13 17 20 43 

Answer 2

Here is a clearer implementation of the section step:

 def quicksort(arr, low, high): if low > high or low == high: return pivot = randint(low, high) updated_pivot = partition(pivot,arr, low, high) quicksort(arr, low, updated_pivot-1) quicksort(arr, updated_pivot+1, high) def partition(pivot, arr, low, high): arr[low], arr[pivot] = arr[pivot], arr[low] #now pivot is at 'low' index of current subarray start_of_ = 1 curr = 1 while curr <= high: if arr[curr] <= arr[low]: arr[start], arr[curr] = arr[curr], arr[start] #making sure all values between index low and index start (exclusive) are less than or equal to the pivot. start+=1 curr += 1 new_pivot_location = start - 1 #the value at index start is the first value greater than the pivot (the range considered in the while loop is exclusive) arr[new_pivot_location], arr[low] =arr[low], arr[new_pivot_location] return new_pivot_location 

EXAMPLE OF WORK:

Input:

 [5,1,3,8, 0,2] | pivot 

Separation Algorithm:

 [3,1,5,8,0,2] --> after switching pivot position | pivot start | [3,1,5,8,0,2] --> initializing start and curr | curr start | [3,1,5,8,0,2] --> 1 < 3, so we swap 1 & 1, and start++, curr++ | curr start | [3,1,5,8,0,2] --> 5 > 3, so we don't swap. Don't move start, curr++ | curr start | [3,1,5,8,0,2] --> 8 > 3, so we don't swap. Don't move start, curr++ | curr start | [3,1,0,8,5,2] --> 0 < 3, so we swap 5 and 0. start++, curr++ | curr start | [3,1,0,2,5,8] --> 2 < 3, so we swap 8 and 2. start++, curr++ | curr [2,1,0,3,5,8] --> swap 2 and 3, and reset pivot index. 

Conclusion:

 [2,1,0,3,5,8] | pivot