qsort

[tokra]

I was brushing up on sorting algorithims so I went and wrote a quick sort.It runs successfully and its fast. I looked at some source code online and my code bore no resemlence whatsoever to it so I will post it and ask the following questions.
1:Is this a correct implementation of the quicksort?
1a:If not what is it and how does it differ?
1b:If it is then why is my code so different that all the implementations I see online. Rephrased: Whay poor design desicions did I make?

void Qsort(int *list, int size,bool tomuchrecursion)
{
	if (!tomuchrecursion)
		_Qsort(list,0,size-1);
	else
		_QsortIt(list,size);
}

void _Qsort(int *list, int low, int high)
{
	if (low>=high) return;
	bool anchor = false;
	int l=low;
	int h=high;
	int tempi;//variable for swapping
	while (l<h)
	{
		if (list[l]>list[h]) //swap if out of order
		{
			tempi=list[l];
			list[l]=list[h];
			list[h]=tempi;
			anchor =!anchor;
		}
		if (anchor)
			l++;
		else
			h--;
	}
	_Qsort(list,low,h-1);//low side
	_Qsort(list,l+1,high);//high side
}
void _QsortIt(int *list, int size)
{
	std::stack< int> thestack;
	thestack.push(0);
	thestack.push(size-1);
	int low,l,high,h,tempi;//declared outside loop because it (should be) tight
	bool anchor;
	
	while(!thestack.empty())
	{
		high=thestack.top();
		thestack.pop();
		low=thestack.top();
		thestack.pop();
		if (low<high)
		{
			 anchor = false;
			l=low;
			h=high;	
			while (l!=h)
				{
					if (list[l]>list[h]) //swap if out of order
					{
						tempi=list[l];
						list[l]=list[h];
						list[h]=tempi;
						anchor =!anchor;
					}
					if (anchor)
						l++;
					else
						h--;
				}
	thestack.push(low);
	thestack.push(h-1);
	thestack.push(l+1);
	thestack.push(high);
	

		}
	}
}

WR

 

[apatterno]

>> 1: Is this a correct implementation of the quicksort?

I don't know, test it--does it work?

>> 1a:If not what is it and how does it differ?

See answers to 1 and 1b

>> 1b:If it is then why is my code so different that all the implementations I see online.

I don't know. If you have found implementations online and you think they are better than what you wrote, then you should just use those instead.

 

[tokra]

It works just fine. The question is not whether or not I have a working sorting algorithim it's whether or not that code is a correct implementation of the qsort algothim. I am not writing this code for use, there is a function already in the standard library;they are written for my understanding.

WR

 

[RbgoWeb]

I think this is the QuickSort Algoritm, but is implemented only for integers, which can make it easier to understand.

void QuickSort(long* array, long iF, long iL)
{
long i, j, iSwp, iMid;

i = iF;
j = iL;
iMid = array[(iF + iL) / 2];


do{
while(array < iMid) i++;
while(iMid < array[j]) j--;

if(i <= j){

iSwp = array;
array = array[j];
array[j] = iSwp;

i++;
j--;
}

}while(i <= j);


if(iF < j)QuickSort(array, iF, j);
if(i < iL)QuickSort(array, i, iL);
}

 

[tokra]

Thank you. I think I understand. It seems that logicaly your code is the similar with a couple of tweaks for optmizations. I'm gonna try and benchmark it against a couple of random datasets and a few preformated ones, cause the recursive logic of trying to figure out exactly how much those tweaks gained was making my head hurt. I'll post when I get some results

WR