# Thread: is my C++ quicksort implementation correct?

1. ## is my C++ quicksort implementation correct?

hi can you please tell me if this is correct?

Code:
```void quickSort(int A[], int left, int right){

int i = left, j = right, pivot = A[left];

while(i<=j){

while(i!=(right + 1) && A[i]<=pivot) i++;
while(A[j]>pivot) j--;
if(j>i){
swap(A[i],A[j]);
j--;
i++;
}

}
swap(A[left],A[j]);
if(left<j)
quickSort(A,left,j-1);
if(right>i)
quickSort(A,i,right);

}```

Code:
` while(i!=(right + 1) && A[i]<=pivot) i++;`
i put i!=(right + 1)

because for input

3,9,3,8,4

the i will check values from index = 5, 6 of the array which do not exist at all,

but i dont need to check the same thing for j since at most the index of j will be the same of the pivot's index

2. With the very first pivot A[0] you get:
3,3,9,8,4

after the first iteration so I think the partitioning is correct.

One thing that you are wrong about though is that you can also stop the loop if this part is false:
while(i!=(right + 1) && A[i]<=pivot) i++;

It's a case that happens frequently in your sample array. In order to test the other part of the condition, you should create a test case that is always true for that. Then the only way you'd stop the loop is if i!=(right + 1) is false.

2,1,-1,-2,0,-3

Still, I don't see a problem. You'd get -3,1,-1,-2,0,2 after the first iteration.

"One thing that you are wrong about though is that you can also stop the loop if this part is false:
while(i!=(right + 1) && A[i]<=pivot) i++;
"
when you say that it's wrong you mean that I should use an OR instead of AND?

4. You were wrong when you said this:
the i will check values from index = 5, 6 of the array which do not exist at all,
The range the while loop will scan is at most i=0 to 4, and it stops when i==5.

But I went on to explain that you can also stop if A[i]<=pivot is false (That happens), so it isn't as though only i!=(right+1) matters. I created a case test where it didn't matter because it would always be true, thus we are only testing if the loop stops when i==5.

AND is correct.

I encourage you to check my work, but I see nothing wrong here.

5. oh now I see, you're right...

thanks for helping me out