Author: Ed Schröder
Date: 02:27:20 08/01/00
Go up one level in this thread
On July 31, 2000 at 13:17:20, Larry Griffiths wrote:
>I am currently using a bubble sort to sort my captures list.
>
>I plan to change it to a selection sort.
>
>Do any of you use another type of sort like quicksort to sort your lists or do
>you have any preferences?
>
>Larry :)
Below is the code of a "quicksort" routine I once (1978 or so) found in a
magazine. At the time it was written in BASIC which I later translated to
Turbo Pascal and then to C. The thing is extremely fast using big tables
and I still use it to build an EOC. It is also very useful if you want to
sort your book in case your book is based on hash keys.
It for instance sorts 20 million items in a couple of seconds if you have
only a few items to swap in a table (or structure). It also compares good
against other sorts using small tables such as a move-list in chess.
Some basic information:
ARRAY is the table to sort (in this case a structure with only one item "key").
NUMBER_OF_ITEMS_TO_SORT is self understood I think.
Swapping takes place in the label "swap".
To change from descending to ascending and vice versa just change the signs
of the compares in "lab10" and "lab20".
That's all here goes...
Ed
void quicksort()
{ unsigned int h,zz;
int t1,l,i,j,r;
int st1[2500],st2[2500];
t1=1; st1[1]=0; st2[1]=NUMBER_OF_ITEMS_TO_SORT;
lab8: l=st1[t1]; r=st2[t1]; t1=t1-1;
lab9: i=l; j=r;
h=ARRAY[(l+r) >> 1].key;
lab10: if (ARRAY[i].key >= h || i >= r) goto lab20;
i=i+1; goto lab10;
lab20: if (ARRAY[j].key <= h || j <= l) goto lab30;
j=j-1; goto lab20;
lab30: if (i > j) goto lab40;
swap: zz=ARRAY[i].key; ARRAY[i].key=ARRAY[j].key; ARRAY[j].key=zz;
i=i+1; j=j-1;
lab40: if (i <= j) goto lab10;
if (r-i <= j-l) goto lab60;
if (l >= j) goto lab50;
t1=t1+1; st1[t1]=l; st2[t1]=j;
lab50: l=i; goto lab80;
lab60: if (i >= r) goto lab70;
t1=t1+1; st1[t1]=i; st2[t1]=r;
lab70: r=j;
lab80: if (r > l) goto lab9;
if (t1) goto lab8;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.