STRANGE CASE QUICKSORT

[paoloben9]

Well I am following the program with this line of numbers to sort it with quicksort, I am writing every step on a blackboard to understand it better, but there is a point, where the program uses for the first time the second recursion, the one with if i<right. The problem is at a certain point of the algorithm the values change in these left=0 right=1 i=1 j=-1, so at this point the two if conditions are not satisfied and the program should end even if the sort is not completed, but i put some cout to and I also debugged to see how the values change, so magically between the two if conditions, the two recursions all the values I wrote below change in new ones, but there s no instruction that says that, I am even out of the while cicles. I don t understand while the values change, Ive been trying it days and days with blackboard but nothing.


#include<iostream>
using namespace std;

void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
cout<<"pivot is"<<pivot<<endl;

/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
cout<<"entering first big while loop"<<endl;
for(int i=0;i<16;i++)
cout<<arr[i]<<" "<<endl ;
}
}
cout<<"recursion"<<endl;

/* recursion */
if (left < j)
quickSort(arr, left, j);

cout<<"i and j are "<<i<<" "<<j<<endl;
cout<<"left and right are "<<left<<" "<<right<<endl<<getchar();

if (i< right)
quickSort(arr, i, right);
}
int main(){
int arr[16]= {81,90,5,4,59,71,77,31,69,82,66,80,31,82,69,5};
for(int i=0;i<16;i++)
cout<<arr[i]<<" " ;
quickSort(arr,0,15);
cout<<endl;
for(int i=0;i<16;i++)
cout<<arr[i]<<" " ;
int wait;
cin>>wait;
return 0;
}

[Duthomhas]

I'm not sure how you get i=1 and j=-1.
Can you show us the input that does that?

[paoloben9]

I tried doing it with paper and pen and I tried to debug it too so I saw that the values that came out are i=1 and j=-1 so it should stop. But instead it goes on IDK help please lol

[paoloben9]

I SOLVED IT