nonrecursive quick sort

[Micko]

Hello, sorry to open same question on this forum but, I have no choice since I'm trying to implement nonrecursive quicksort using C++ STL.

i'm trying to correct code earlier posted on the board,
http://cboard.cprogramming.com/showt...sive+quicksort
but I have problem with an infinite loop:

#include <stack>
/*...*/
void quicksort_it(int *dataset,int dataset_size)
{
	stack<int> st;
	int i,j,first,last,pivot;
	
	for(i=0;i<dataset_size;i++)
		st.push(dataset[i]);
		
	first= 0;
	last = dataset_size-1;
	while(!(st.empty()))
	{
		for(i=first;i<=last;i++)
		{
			dataset[i] = st.top();
			st.pop();
		}
		while(first<last)
		{
			// Split
			pivot = dataset[first];
			i = first, j= last -1 ;
			for(;;)
			{
				while(dataset[i] <= pivot && i <= last) {i++;}
				while(pivot < dataset[j] && j >= first){j--;}
				if(i<j)
					swap(dataset[i],dataset[j]);
				else
					break;
			}
			swap(dataset[i],dataset[last-1]);
			for(i=pivot+1;i<=last;i++)
				st.push(dataset[i]);
			pivot=last-1;
		}
	}
}

Please can you look this and correct it, I don't know what is wrong.
Thanks

[pianorain]

while(first<last)
{
// Split

You never update either first or last, so if you enter this while loop, you'll stay in it forever.

[Micko]

Well, I think I made it.

void quicksort_it(int *dataset,int l,int r)
{
	stack<int> st;
	int j;
	st.push(r);
	st.push(l);
	while(!st.empty())
	{
		l=st.top();
		st.pop();
		r=st.top();
		st.pop();

		j=partition(dataset,l,r);

		if(l < (j-1))
		{
			st.push(j-1);
			st.push(l);
		}
		if((j+1) < r)
		{
			st.push(r);
			st.push(j+1);
		}
	}
	
}

int partition(int* array, int l, int r)
 {
	 int pivot,i,j;

	
	pivot=array[l];
	 i=l+1;
	 j=r;

	 for(;;)
	 {
		 while((array[i] <= pivot) && (i <= r))i++;
		 while((array[j] > pivot) && (j > l))j--;
		
		 if(i < j)
			 swap_in_array(array,i,j);
		 else 
			 break;
	 }
	 swap_in_array(array,j,l);

	 return j;
 }

  void swap_in_array(int* array, int i, int j)
 {
	 int tmp;
	 tmp=array[i];
	 array[i]=array[j];
	 array[j]=tmp;
 }

I think this is correct.
All I need was a good sleep.