c - quicksort program provides partially sorted output -

below simple quick sort code last element pivot,almost works except last element fails sorted. thoughts program went wrong?

here's output:

$a.out  4 3 5 2 1 3 2 3 //input  1 2 2 3 3 3 5 4 //output 

simple swap looks fine

void swap ( int* a, int* b ) {     int t = *a;     *a = *b;     *b = t; } 

hmm..fine ..may issue end?

int partition(int a[],int start,int end){ int pivot = a[end]; int pindex=start;int i;      ( i=start; <= end-1; i++){        if (a[i] <= pivot){            swap(&a[i],&a[pindex]);pindex++;        }     }     swap(&a[pindex],&a[pivot]);     return (pindex + 1); } 

surely looks good.

void quicksort(int a[],int start,int end){ int pindex;      if (start < end){         pindex = partition(a,start,end-1);         quicksort(a,start,pindex-1);         quicksort(a,pindex+1,end);     } } 

simple main call

int main(){     int a[8] = {4, 3, 5, 2, 1, 3, 2, 3};     int i=0;      for(i=0;i<8;i++)         printf(" %d", a[i]);     quicksort(a,0,8);     printf("\n");     for(i=0;i<8;i++)         printf(" %d", a[i]); } 

please review partition function.

it should return

 return pindex; 

instead of pindex+1.

because, take following case:

1 2 3 4 5

as 5 chosen pivot, should return 4, not 5 pivot index.

check invariant pindex must lie between start , end (both inclusive). if pivot lie @ end, must not pass end.

generally, partition starts both end. starting 1 end. try both end efficiency. otherwise, in 1 2 3 4 5, keep swapping same element (1 1, 2 2 , on).

and in partition:

swap(&a[pindex],&a[pivot]); 

should be

 swap(&a[pindex],&a[end]); 

pivot value, not index.

another change, required quicksort,

  if (start < end){   pindex = partition(a,start,end-1);   //as here index 1 past last, make start..pindex   quicksort(a,start,pindex);   quicksort(a,pindex+1,end);   } 

your partition function should

int partition(int a[],int start,int end){  int pivot = a[end]; int pindex=start;int i;  ( i=start; <= end-1; i++){     if (a[i] <= pivot){         swap(&a[i],&a[pindex]);pindex++;         }     }      swap(&a[pindex],&a[end]);     return (pindex); } 

see https://en.wikipedia.org/wiki/quicksort#lomuto_partition_scheme. partition scheme used here.