Huge flaw in quickSort implementation of mine. Please help!

[incognito]

Hi Forum,

I am trying to implement quickSort algorithm. The program works fine and sorts the array but I guess internal implementation isn't the way it should be.
I am new to DS and really want to get this thing done :(

Here is the program (Sorry for the length :) I couldn't optimize it)

#include<iostream>
#include<vector>
using namespace std;
int partition(vector<int>&,int,int);

void quickSort(vector<int>& arr,int left, int right)
{
  int middle; //left it uninitialized. Was not sure whether to pass it or not.
              //Anyway, doesn't really affecting the program.

  cout<<"calling quickSort()"<<endl;
  cout<<"left is\t"<<left<<endl;
  cout<<"right is\t"<<right<<endl;
  cout<<"middle is\t"<<middle<<endl; 


  if(left < right)
  {
    middle = partition(arr,left,right);
    quickSort(arr,left,middle);
    quickSort(arr,middle+1,right);
  }

  return;
}

int partition(vector<int>& a,int left,int right)
{
 cout<<"Calling partition\n"<<endl;

  int x=  a[left];
  int i = left-1;  //out of bound. But brought back it back in the loop
  int j = right+1; //out of bound. But brought back it back in the loop

  int temp;
  do
  {
    cout<<"x is\t"<<x<<endl;
    cout<<"i is\t"<<i<<"\t"<<"a[i] is\t"<<a[i]<<endl;
    cout<<"j is\t"<<j<<"\t"<<"a[j] is\t"<<a[j]<<endl;
    cout<<endl<<endl;

    do
    {
      j--;
    }while(x>a[j]);

   do
   {
     i++;
   }while(x<a[i]);

   if(i<j)
   {
     temp=a[i];
     a[i]=a[j];
     a[j]=temp;
   }
  }while(i<j);

  return j;
}

int main()
{
  vector<int> array;


  array.push_back(20);
  array.push_back(10);
  array.push_back(30);
  array.push_back(60);
  array.push_back(40);
  array.push_back(50);

  cout<<"size of vector is\t"<<array.size()<<endl;

  quickSort(array,0,5);

  cout<<" sorted array is\t";
  for(int i=0;i<array.size();i++)
  {
    cout<<array[i]<<" ";
  }
  return 0;
}

output is

size of vector is       6
calling quickSort()
left is 0
right is        5
middle is       6
Calling partition

x is    20
i is    -1      a[i] is 43
j is    6       a[j] is 0


x is    20
i is    0       a[i] is 50
j is    5       a[j] is 20


x is    20
i is    1       a[i] is 40
j is    4       a[j] is 10

//first question : i is still less than j here. So why doesn't it keep calling the main while loop, that is, while(i<j). It seems control is returned to quicksort()

calling quickSort()
left is 0
right is        3
middle is       4
Calling partition

x is    50
i is    -1      a[i] is 43
j is    4       a[j] is 10


x is    50
i is    0       a[i] is 60  //second question:When did a[i] become 60 and
j is    3       a[j] is 50  //a[j] 50?


calling quickSort()
left is 0
right is        0
middle is       1
calling quickSort()
left is 1
right is        3
middle is       1
Calling partition

x is    40
i is    0       a[i] is 60
j is    4       a[j] is 10


x is    40
i is    1       a[i] is 50
j is    3       a[j] is 40


calling quickSort()
left is 1
right is        1
middle is       2
calling quickSort()
left is 2
right is        3
middle is       2
Calling partition

x is    30
i is    1       a[i] is 50
j is    4       a[j] is 10


x is    30
i is    2       a[i] is 40
j is    3       a[j] is 30


calling quickSort()
left is 2
right is        2
middle is       3
calling quickSort()
left is 3
right is        3
middle is       3
calling quickSort()
left is 4
right is        5
middle is       0
Calling partition

x is    10
i is    3       a[i] is 30
j is    6       a[j] is 0


x is    10
i is    4       a[i] is 20
j is    5       a[j] is 10


calling quickSort()
left is 4
right is        4
middle is       5
calling quickSort()
left is 5
right is        5
middle is       5

 sorted array is        60 50 40 30 20 10

//Question 3 : considering first two questions arise from a major flaw in the logic, I guess number of calls to quickSort and partitions are made more than the required calls. I wonder why is this thing still giving me a correct output? :D

Any insights, simple explanations, change in logic are most welcomed :)
Thanks in advance.

Forgive my lack of DS, I am still learning phase, so I know this code sucks!

[incognito]

Come on guys ! :( I know this forum has people who can answer my queries :)
Please help!

[Whovian]

I think I know why it might still be calling the while loop. (Well, it isn't, it's a do-while loop, but that's unimportant.) Maybe you're changing i and j inside the loop. It does not check to see if the end result will meet the conditions, and do the loop if it does, it does the loop, and if the conditon's met, does it again.

[cire]

First question: You print out the value of i and j at the beginning of (each iteration of) the loop, so you don't actually know the values of i and j when the loop ends. You should also keep in mind that the values of i and j that you actually print out are never used in the loop (each is immediately decremented or incremented before anything is done with it.)

Second question: Why don't you instrument the code to print out the vector each time you change it so you can see how the progress goes?

void Print(const vector<int>& v )
{
	cout << '{' ;
	unsigned i ;
	for (i=0; i<v.size()-1 ;  ++i)
		cout << v[i] << ", " ;
	cout << v[i] << "}\n" ;
}

int partition(vector<int>& a,int left,int right)
{
	cout<<"Calling partition\n"<<endl;

	int x=  a[left];
	int i = left-1;  //out of bound. But brought back it back in the loop
	int j = right+1; //out of bound. But brought back it back in the loop

	cout << "x is " << x << ".\n" ;
	int temp;
	do
	{
		//    cout<<"x is\t"<<x<<endl;
		//    cout<<"i is\t"<<i<<"\t"<<"a[i] is\t"<<a[i]<<endl;
		//    cout<<"j is\t"<<j<<"\t"<<"a[j] is\t"<<a[j]<<endl;
		//    cout<<endl<<endl;

		do
		{
			j--;
		}while(x>a[j]);

		cout << "j is " << j << ": \ta[j] is " << a[j] << ".\n" ;

		do
		{
			i++;
		}while(x<a[i]);

		cout << "i is " << i << ": \ta[i] is " << a[i] << ".\n" ;

		if(i<j)
		{
			cout << "Swapping a[i] and a[j].\n" ;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			Print(a) ;
		}
		else
			cout << "Not swapping.\n" ;
		cout << '\n' ;
	}while(i<j);

	cout << "Leaving partition.\n\n\n" ;
	return j;
}

edit: Code formatting had mixed tab/spacing indentation.

[incognito]

Thanks cire. That helps :) You are right. I wasn't actually keeping track of i and j. Mistake now corrected. Damn! How did I miss on such a small thing :(
Anyway, thanks again!