partition quicksort algorithm problem

[mahmoud2592]

I am trying to code a partition quicksort but the problem here is at the output is in an infinite loop:
the input : 4 3 5 7 2
the expected output : 2 3 4 5 7
but my output is infinite :
2 3 4 5 7
2 3 4 5 7
2 3 4 5 7
.
.
and so on


what is the solu ?

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
/* Head ends here */
void partition(vector <int>  ar) {
int temp,j=ar.size()-1,i=1,k=0,turn = 0,on_off=1;
do{
    if(ar[j]<ar[k]&&turn==1&&on_off==1)
    {
        temp = ar[j];
        for(int x = j;x>=k;x--)
        {
            if(x!=0&&j!=k)
            {ar[x] = ar[x-1];}
        }
        k++;
        j--;
        ar[0] = temp;
        turn = 0;
        on_off = 0;
        }
        if(ar[j]>ar[k]&&turn==1&&on_off == 1)
        {
            j--;
            turn = 0;
            on_off = 0;
        }
        if(ar[i]<ar[k]&&turn==0&&on_off == 1)
        {
        temp = ar[i];
        for(int x = i;x>=k;x--)
        {
            if(x!=0&&i!=k)
            {ar[x] = ar[x-1];}

        }
        k++;
        i++;
        ar[0] = temp;
        turn = 1;
        on_off = 0;
        }
        if(ar[i]>ar[k]&&turn==0&&on_off == 1)
        {
            i++;
            turn = 1;
            on_off = 0;
        }
        on_off = 1;
         for(int z = 0;z<ar.size();z++)
        {
            cout<<ar[z];
        }
        cout<<endl;
        }while(j+1!=i);

        }

/* Tail starts here */
int main(void) {
   vector <int>  _ar;
   int _ar_size;
cin >> _ar_size;
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
   int _ar_tmp;
   cin >> _ar_tmp;
   _ar.push_back(_ar_tmp);
}

partition(_ar);

   return 0;
}

[abhishekm71]

It seems that your do-while loop termination condition is not being met. I haven't read your code in detail, but you can try changing:

while(j+1!=i);

to

while(j+1 > i);

[mahmoud2592]

still doesn't work.

[abhishekm71]

I would suggest using your debugger to check the values of j and i at each iteration and to check why the termination condition is not being reached.

Ofcourse, there is a possiblity that the error lies elsewhere but you can trace it through the debugger or just outputting some status messages to the console.

[cire]

This is not quicksort and your partition function... doesn't partition. The variables are ill-named. There is no whitespace used to make the code more readable and the indentation is horrible and inconsistent.

Make your code readable. You might want to write out or refer to the algorithm before (and while) you attempt to code it because you're nowhere near a quicksort implementation.

[Yueeng]

hey madh
In my opinion, the quicksort's partition alogrithm is like:
1. Choose a number as pivot.
2. Throw numbers that samller than the pivot to the left, and the bigger ones to the right.
3. Repeat above steps till you only have 2 or 1 number in partition.

I didn't check these code, but i think it should do the explaination:

void partition(int *low, int *high)
{
	int key;
	key=*low;
	
	while (low<heigh)
	{
		while ((low<high)&&(*high>key)) high--;
		*low=*high;
		while ((low<high)&&(*low<key)) low++;
		*high=*low;
	}
	*low=key;
}

And i also think that a right implementation of an algorithm should be elegant, your first post was ,well, obviously not much elegant.(:
Anyway, cheer up!