2 replies to this topic

[Alucard648]

Classical programming exercise in Zscript:

//Sorts the given array within the range between index1 and index2 and by the given order:
//true-ascending, false-descending.
void QSort(int array, int index1, int index2, bool order){
	int median = array[(index1 + index2)/2];
	int step1=index1;
	int step2=index2;
	int temp=0;
	while(step1<=step2){
		if(order){
			while(array[step1]<median) step1++;
			while(array[step2]>median) step2--;
		}
		else{
			while(array[step1]>median) step1++;
			while(array[step2]<median) step2--;
		}
		if (step1<=step2){
			temp = array[step1];
			array[step1]=array[step2];
			array[step2]=temp;
			step1++;
			step2--;
		}
	}
	if (step1<index2) QSort(array, step1, index2, order);
	if (step2>index1) QSort(array, index1, step2, order);
}

//A shorthand function for sorting entire array.
void QSort(int array, bool order){
	int index2 = SizeOfArray(array)-1;
	 QSort(array, 0, index2, order);
}

//Generates a randomized array, sorts it and prints it into allegro.log
//D0 - switch between ascending and desending order
ffc script Qsorttest{
	void run(int order){
		int array[1000];
		for (int i=0; i<SizeOfArray(array); i++){
			array[i]= Rand(999);
		}
		if (order>0) QSort(array, true);
		else QSort(array, false);
		Game->PlaySound(32);
		for (int i=0; i<1000; i++){
			Trace(array[i]);
		}
		Game->PlaySound(32);
	}
}

Any thoughts?

[grayswandir]

Looks decent, from briefly reading over it.

 

I wrote QSort for my own game at one point, but I ended up not using it. I was keeping an array sorted every frame, so while one or two elements would be out of order every frame, most of the array was already sorted. In that situation, insertion sort turned out to be a lot faster, since an already sorted list is QSort's worst case scenario.

 

On that note, you might want to pick a random element for your median instead of the one exactly in the middle of the list.

[Saffith]

It's a clever way of working around ZScript's limitations, but with all the work it takes to split the array in two, I wonder how quick it really is. And the small stack size means you can't sort large arrays without risking overflow. You might be better off in both regards with a more traditional implementation using the maximum allowed array size for each sub-array. Arrays are heap allocated and initialized, which adds a fair amount of overhead, but I suspect it's still faster. Hard to say for sure, though.

As an academic exercise, at least, it looks good.