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 ];
}