quicksort implementation

Question

Following code for quicksort does not work and I can't understand what is 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;
 }

It outputs

5  8  9  11  10  17  12  20  13  43

Rosetterosewall

Did you try stepping through the code to see where it goes wrong? – Shane

no homework no,it is just training and testing codes from algorithmic books – Rosetterosewall

i have found that by using step into from debug result is this j -858993460 int why it is so? – Rosetterosewall

I've translated your code to Cython. It only ~2 times faster than qsort from clib. – Chinn

Answer 1

In your partition method, that should be

int v = a[h]; 

and not

int v = a[l];

[Update: I've just tested the code with that change, and it works correctly, outputting:

5  8  9  10  11  12  13  17  20  43 

Panada

one question @Mitch Wheat, first of all thank you very much for helping,but question is that what is difference?i mean if we denote pivot element by first or last element? does it means that sometimes quicksort does not work if pivot is not choosed correctly? – Rosetterosewall

The algorithm always works regardless of choice of pivot (although runtime might exhibit N^2 worst case, but that's another topic.) – Panada

if we want to use the condition as int v = a[l]; then where in the code should we make changes, I want to select the first element as pivot. – Aprilette

Answer 2

Here is a clearer implementation of the partition 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 RUN:

Input:

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

Partition algorithm:

[3,1,5,8,0,2] --> after switching pivot's 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.

Output:

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

Thy