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.

3. hi whiteflags thanks for your answer

"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

Popular pages Recent additions