Thread: Quicksort

Hi, i'm trying to implement a nonrecursive quicksort. I have written this code but it doesn't work. It simply doesn't sort the array. Can you give same advice?

Code:

void quicksort_it(int *dataset,int dataset_size)
{
	StackType<int> stack;
	int i,j,first,last,pivot;
	
	for(i=0;i<dataset_size;i++)
		stack.Push(dataset[i]);
		
	first= 0;
	last = dataset_size-1;
	while(!(stack.IsEmpty()))
	{
		for(i=first;i<=last;i++)
			dataset[i] = stack.Pop();
		while(first<last)
		{
			// Split
			pivot = median3(dataset, first, last);
			i = first, j= last -1 ;
			for(;;)
			{
				while(dataset[++i] <pivot) {};
				while(pivot<dataset [--j]){};
				if(i<j)
					swap(dataset[i],dataset[j]);
				else
					break;
			}
			swap(dataset[i],dataset[last-1]);
			for(i=pivot+1;i<=last;i++)
				stack.Push(dataset[i]);
			last = pivot-1;
		}
	}
}

const int & median3( int *dataset, int left, int right )
{
	int center = ( left + right ) / 2;
        if( dataset[ center ] < dataset[ left ] )
            swap( dataset[ left ], dataset[ center ] );
        if( dataset[ right ] < dataset[ left ] )
            swap( dataset[ left ], dataset[ right ] );
        if( dataset[ right ] < dataset[ center ] )
            swap( dataset[ center ], dataset[ right ] );

        // Place pivot at position right - 1
          swap( dataset[ center ], dataset[ right - 1 ] );
          return dataset[ right - 1 ];
}

since you're using the stl, you should know that it includes a pretty fast sort already... i think its a combination q-sort and some kind of smaller sort.