# is my C++ quicksort implementation correct?

• 04-05-2011
nik
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
• 04-05-2011
whiteflags
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.
• 04-05-2011
nik

"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?
• 04-05-2011
whiteflags
You were wrong when you said this:
Quote:

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.
• 04-05-2011
nik
oh now I see, you're right...

thanks for helping me out :)