Quicksort in C - Just a number not sorted

Question

i'm trying to implement a quicksort algorithm, it went well to be honest,except for a single detail, one number is not sorted at the end... then i tried doing it very similar as i saw in a book, still the same (i'm sure it is a very small detail in the code, but i just can't find it)

i'll post it here

#include <stdio.h>
#include <stdlib.h>

int i,j,x,y;

void qs(int *vect,int start, int end);

int main() {
    int arr[] = {0,4,5,6,9,3,2,1};
    int amount;
    amount= sizeof(arr)/sizeof(arr[0]);
    //print array
    for ( i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        printf("before = [%d]\n",arr[i]);
    }

    qs(arr,0,amount-1);

    for ( i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        printf("after: [%d]\n",arr[i]);
    }
    return 0;

}



void qs(int *vect,int start, int end){

    i = start;
    j = end;
    x = vect[(start + end)/2];

    do {
        while(vect[i] < x && i < end){
            i++;
        }

        while (vect[j] > x && j > start){
            j--;
        }

        if (i<=j) {
            y = vect[i];
            vect[i] = vect[j];
            vect[j] = y;
            i++;
            j--;
        }
    }
    while(i<=j);

    if (start<j) {
        qs(vect,start,j);
    }
    else{
        if (i<end) {
            qs(vect,end,i);
        }
    }
    return ;
}

and the result:

before = [0]

before = [4]

before = [5]

before = [6]

before = [9]

before = [3]

before = [2]

before = [1]

__

after: [0]

after: [1]

after: [2]

after: [3]

after: [4]

after: [5]

after: [9]

after: [6] <---------- this little guy

Answer 1

When start < j is satisfied, i < end can be also satisfied. else-if usage prevent to take into account that case. Moreover, I agree with define cindy const's saying that qs(vect,end,i) ought to be qs(vect, i, end). So, change your recursive cases like,

if (start < j) {
    qs(vect, start, j);
}
if (i < end) {
    qs(vect, i, end); 
}

But, I think better,

void qs(int *vect,int start, int end) {

    int i,j,x,y;

    if (start < end)
    {
        i = start;
        j = end;
        x = vect[((unsigned int)start + (unsigned int)end) >> 1];

        do {
            while ( vect[i] < x && i < end ) {
                i++;
            }

            while ( vect[j] > x && j > start ) {
                j--;
            }

            if ( i <= j ) {
                y = vect[i];
                vect[i] = vect[j];
                vect[j] = y;
                i++;
                j--;
            }
        } while ( i <= j );

        qs(vect, start, j);
        qs(vect, i, end);
    }
}

---

Additionally, (start + end) / 2 is not good because it may give raise to overflow. Instead, you can use ((unsigned int)start + (unsigned int)end) >> 1.