sarjumaharaj
Junior Member level 1
This is my code for quick sort. Needless to say it doesn't work. I tried to see the program step by step but got so confused in the recursion part. Can someone tell me what the problem is and also teach me how to analyze a recursive program. How do you find errors in recursive program. The function calls itself and makes multiple copies of itself in runtime and while checking I always lose track of where or what it is returning.
Code:
#include<iostream>
using namespace std ;
int partition (int x[] , int lb , int ub )
{
int a , i , j , temp;
i = lb -1;
j = ub +1 ;
a = x[ub] ;
while (1)
{
do
{
j--;
}while (x[j] >= a); // repeat this loop until you dont get a value that is a[j] <= a
do
{
i++;
}while (x[i] <= a); // repeat this loop until you dont get a value that is a[i] >= a
if (i <j) // i think it is less than or equal to (but no equal to doesnt need to be swapped
{
temp = x[j] ;
x[j]= x[i] ;
x[i] = temp;
}
else if ( i > j )
{
return j ;
}
}
}
void quicksort ( int x[] ,int lb , int ub)
{
int newp;
if ( lb < ub )
{
newp = partition (x , lb , ub );
quicksort (x , lb , newp ) ;
quicksort (x, newp + 1 , ub ) ;
return ;
}
else if (lb >= ub )
{
return ;
}
}
void display (int x[] , int size)
{
for (int i =0 ; i < size ;i++)
{
cout << x[i] << endl;
}
}
int main ()
{
int size;
int num;
int a[100] ;
cout << "Enter a size of array :" ;
cin >> size;
cout << "Enter the values inside the array: " ;
for (int i =0 ; i< size ;i++)
{
cin >> num ;
a[i] = num ;
}
quicksort (a , 0 , size -1 ) ;
display (a, size);
return 0 ;
}