!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! sorting.h v1.2, 17 Sep 2003
! Sort functions for Inform. Written by Fredrik Ramsberg.
! Thanks to Neil Cerutti and Roger Firth for submitting bug reports.
! Freely usable by anyone for any purpose. I request but don't demand
! that you give due credit if this code is used in something that is
! released to the public. I'd also appreciate if you'd mail me bug
! reports or your opinions if you use this little library.
! -- Fredrik Ramsberg, fredrik {AT} ramsberg {DOT} net
!
! Publically usable routines:
!
! QUICKSORT group
! ---------------
! inssort_bytes_idx(arr, index, from, to);
! inssort_words_idx(arr, index, from, to [, comparison]);
! qsort_bytes_idx(arr, index, from, to);
! qsort_words_idx(arr, index, from, to [, comparison]);
! inssort_bytes(arr, from, to);
! inssort_words(arr, from, to [, comparison]);
! qsort_bytes(arr, from, to);
! qsort_words(arr, from, to [, comparison]);
!
! SHELLSORT group
! ---------------
! shsort_bytes_idx(arr, index, from, to);
! shsort_words_idx(arr, index, from, to [, comparison]);
! shsort_bytes(arr, from, to);
! shsort_words(arr, from, to [, comparison]);
!
! Which one of these three sort algorithms is the fastest, depends
! on the data to be sorted. Here's a short guide:
!
! Use InsertionSort (inssort) when no value is expected to be far from
! its correct position (up to roughly ten positions away is fine). Many
! small disorders are quite ok. Also use InsertionSort when the sorting
! has to be stable. This means that if there are two equal values in
! the data, the one that is to the left of the other when the sorting
! starts must still be to the left of the other when the sorting ends.
! This is not often a demand, but it happens.
!
! Use QuickSort (qsort) when the data is expected to be entirely unsorted.
!
! Use ShellSort (shsort) when the data may or may not be nearly in order,
! when there may or may not be elements that are far from their correct
! position, and when you can't decide which algorithm is the best. It's
! a very good allround algorithm.
!
! The InsertionSort algorithm is very closely related to ShellSort.
! However, the InsertionSort functions are in the QuickSort group in this
! library. This is only because this particular QuickSort implementation
! utilises InsertionSort in the final stages of sorting, for better speed.
! This means that the InsertionSort routines can't be removed if one wants
! to use the QuickSort routines.
!
! All functions that take an index argument are called index-based sort
! functions. These will not alter the order of the original array, but
! will instead build an index on the side that says in which order the
! array elements should be. The index entries are always word-sized,
! regardless of the size of the data elements. This is quite powerful
! because it means you can keep track of related data on the side, i.e.
! if you sort an array containing people's salaries, you will still know
! what person had what salary even after sorting.
!
! All sort-functions that are not index-based are referred to as direct sort
! functions.
!
! The 'from' argument should contain the index of the first element to be
! sorted, usually 0 if the data is in an ordinary array, or 1 if it's in
! a table. The 'to' argument should hold the index of the last element to
! be sorted.
!
! For functions that take an optional comparison argument, this argument is
! expected to be a function that takes two arguments, a and b, and which
! returns a non-zero value iff a should end up after b in the sorted array.
! Important: Such a function must never return a non-zero value if a and b
! are equivalent, from a sorting point of view.
! Sample function to sort an array of words in descending order:
! [ lessthan a b; return a<b; ];
! Sample sorting call that utilises the sample function above:
! qsort_words(my_word_table, 1, my_word_table-->0, lessthan);
!
! All functions that sort word-data use the standard Inform signed comparison
! by default. If unsigned comparison is required, supply your own comparison
! function instead.
!
! To stop some of the routines from compiling (in order to save space), one
! can set one or more of the following constants, before including this file:
! NOQUICKSORT, NOSHELLSORT,
! NOINDEXSORT, NODIRECTSORT,
! NOBYTESORT, NOWORDSORT
! If no routines are removed in this manner, this package will take up roughly
! 3.5 KB in the story file, with debugging information turned off.
!
! There are two more constants which may be defined before including this file:
! QUICKSORTLIMIT
! SHELLSORTCONST
! If you're _really_ interested in fine-tuning your sorting, these constants
! may be of interest to you. Otherwise, feel free to forget about them right
! away. If any of them are defined, it must be set to a value greater than
! zero, or the sorting routines will crash. Any value higher than 20 is
! highly unlikely to be useful. Which values are the best (i.e. giving the
! fastest sorting) depends on which interpreter will be used to run the
! program, as well as the nature of the data to be sorted.
! The programmer is free to define both constants, define one of them, or
! leave both undefined. Leaving them undefined will set them to values
! optimised for sorting random data under WinFrotz (QUICKSORTLIMIT=10,
! SHELLSORTCONST=3), and this is generally good enough for any data under any
! interpreter. Of course, QUICKSORTLIMIT only affects QuickSort, and
! SHELLSORTCONST only affects ShellSort.
!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
System_file;
#Ifndef NOQUICKSORT;
Default QUICKSORTLIMIT 10;
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Index-based InsertionSort and QuickSort routines.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#Ifndef NOINDEXSORT;
#Ifndef NOBYTESORT;
[ _isbi_sub arr index from to i j v vi f1;
f1=from + 1;
for(i=f1, j=i, vi=index-->i, v=arr->vi : i<=to : index-->(j+1)=vi, i++, j=i, vi=index-->i, v=arr->vi )
while(j-- >= f1 && arr->(index-->j) > v)
index-->(j+1)=index-->j;
];
[ inssort_bytes_idx arr index from to i;
for(i=from:i<=to:i++)
index-->i=i;
_isbi_sub(arr, index, from, to);
];
[ _qsbi_sub arr index from to i j m temp vm vt p;
while(from>=0) {
i=from-1;
j=to;
m=from+(to-from)/2;
p=arr->(index-->from);
vm=arr->(index-->m);
vt=arr->(index-->to);
if((p<=vm && vm<=vt) || (vt<=vm && vm<=p)) {
p=vm;
temp=index-->m;
index-->m=index-->from;
index-->from=temp;
} else if((p<=vt && vt<=vm) || (vm<=vt && vt<=p)) {
p=vt;
temp=index-->to;
index-->to=index-->from;
index-->from=temp;
}
[ qsort_words_idx arr index from to comp i;
for(i=from:i<=to:i++)
index-->i=i;
if(comp) {
_qsgi_sub(arr, index, from, to, comp);
#Iftrue QUICKSORTLIMIT > 1;
_isgi_sub(arr, index, from, to, comp);
#Endif;
} else {
_qswi_sub(arr, index, from, to);
#Iftrue QUICKSORTLIMIT > 1;
_iswi_sub(arr, index, from, to);
#Endif;
}
];
#Endif; ! Not NOWORDSORT;
#Endif; ! Not NOINDEXSORT
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Direct InsertionSort and QuickSort routines.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#Ifndef NODIRECTSORT;
#Ifndef NOBYTESORT;
[ inssort_bytes arr from to i j v f1;
f1=from + 1;
for(i=f1, j=i, v=arr->i : i<=to : arr->(j+1)=v, i++, j=i, v=arr->i)
while(j-- >= f1 && arr->j > v)
arr->(j+1)=arr->j;
];
[ _qsb_sub arr from to i j m temp vm vt p;
while(from>=0) {
i=from-1;
j=to;
m=from+(to-from)/2;
p=arr->from;
vm=arr->m;
vt=arr->to;
if((p<=vm && vm<=vt) || (vt<=vm && vm<=p)) {
p=vm;
temp=arr->m;
arr->m=arr->from;
arr->from=temp;
} else if((p<=vt && vt<=vm) || (vm<=vt && vt<=p)) {
p=vt;
temp=arr->to;
arr->to=arr->from;
arr->from=temp;
}
[ shsort_bytes_idx arr index from to i vi j v h k len;
h=1;
len=to-from+1;
while(h < len)
h=SHELLSORTCONST*h+1;
for(i=from:i<=to:i++)
index-->i=i;
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
vi=index-->i;
v=arr->vi;
while((j=j-h) >= from && arr->(index-->j) > v)
index-->(j+h)=index-->j;
index-->(j+h)=vi;
}
];
#Endif; ! Not NOBYTESORT;
#Ifndef NOWORDSORT;
[ _ssgi_sub arr index from to comp h i vi j v k;
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
vi=index-->i;
v=arr-->vi;
while((j=j-h) >= from && comp(arr-->(index-->j), v))
index-->(j+h)=index-->j;
index-->(j+h)=vi;
}
];
[ shsort_words_idx arr index from to comp h i vi j v k len;
for(i=from:i<=to:i++)
index-->i=i;
h=1;
len=to-from+1;
while(h < len)
h=SHELLSORTCONST*h+1;
if(comp)
return _ssgi_sub(arr, index, from, to, comp, h);
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
vi=index-->i;
v=arr-->vi;
while((j=j-h) >= from && arr-->(index-->j) > v)
index-->(j+h)=index-->j;
index-->(j+h)=vi;
}
];
#Endif; ! Not NOWORDSORT;
#Endif; ! Not NOINDEXSORT;
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Direct ShellSort routines.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#Ifndef NODIRECTSORT;
#Ifndef NOBYTESORT;
[ shsort_bytes arr from to i j v h k len;
h=1;
len=to-from+1;
while(h < len)
h=SHELLSORTCONST*h+1;
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
v=arr->i;
while((j=j-h) >= from && arr->j > v)
arr->(j+h)=arr->j;
arr->(j+h)=v;
}
];
#Endif; ! Not NOBYTESORT;
#Ifndef NOWORDSORT;
[ _ssg_sub arr from to comp h i j v k;
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
v=arr-->i;
while(((j=j-h) >= from) && comp(arr-->j, v))
arr-->(j+h)=arr-->j;
arr-->(j+h)=v;
}
];
[ shsort_words arr from to comp i j v h k len;
h=1;
len=to-from+1;
while(h < len)
h=SHELLSORTCONST*h+1;
if(comp)
return _ssg_sub(arr, from, to, comp, h);
while((h=(h-1)/SHELLSORTCONST)>=1)
for(k=0: k<h: k++)
for(i=k+h+from: i<=to: i=i+h) {
j=i;
v=arr-->i;
while((j=j-h) >= from && arr-->j > v)
arr-->(j+h)=arr-->j;
arr-->(j+h)=v;
}
];
