Built In Sorting?

BlitzMax Forums/BlitzMax Beginners Area/Built In Sorting?

fredborg(Posted 2005) [#1]
Hi,

Which sorting algorithm does the built in .sort() method use for arrays?


RiK(Posted 2005) [#2]
Looking at the source (blitz_array.c):

#define SWAP(X,Y) {t=*(X);*(X)=*(Y);*(Y)=t;}
#define QSORTARRAY( TYPE,IDENT )\
static void IDENT( TYPE *lo,TYPE *hi ){\
	TYPE t;\
	TYPE *i;\
	TYPE *x;\
	TYPE *y;\
	if( hi<=lo ) return;\
	if( lo+1==hi ){\
		if( LESSTHAN(hi,lo) ) SWAP(lo,hi);\
		return;\
	}\
	i=(hi-lo)/2+lo;\
	if( LESSTHAN(i,lo) ) SWAP(i,lo);\
	if( LESSTHAN(hi,i) ){\
		SWAP(i,hi);\
		if( LESSTHAN(i,lo) ) SWAP(i,lo);\
	}\
	x=lo+1;\
	y=hi-1;\
	do{\
		while( LESSTHAN(x,i) ) ++x;\
		while( LESSTHAN(i,y) ) --y;\
		if( x>y ) break;\
		if( x<y ){\
			SWAP(x,y);\
			if( i==x ) i=y;\
			else if( i==y ) i=x;\
		}\
		++x;\
		--y;\
	}while( x<=y );\
	IDENT(lo,y);\
	IDENT(x,hi);\
}


Pretty basic quicksort..


fredborg(Posted 2005) [#3]
Cool, thanks!


RiK(Posted 2005) [#4]
Well I looked it up in the 'official documentation' ;)

Fingers crossed that the promised documentation overhaul will deliver the goods eh.