Ask A Scientist© Computer Science Archive

Index Key:   CSI024
Author:      Brian Allen
Subject:     Sorting Algorithm - Hypercard
Text:        Could you tell me the fastest sorting algorithm?  I am using 
Hypercard.  I need to sort fields that are about 125 entries in length.  I am 
using an algorithm that I think is called boolean.  Is there a faster method?  
Right now it takes about 7-8 minutes to sort on a Mac Classic 2.  If  you 
could explain the principle behind the algorithm I think I could  extrapolate 
the code into hypertalk. I appreciate your help.

Response #: 1 of 2
Author:     John Hawley
Text:       An entire chapter of NUMERICAL RECIPES is devoted to sorting 
algorithms. The authors say that the "straight insertion" method  is adequate 
for small (<50) sorts, and they strongly recommend the "heapsort" for larger 
jobs. I will list the C code for the straight insertion:
 for( j=2; j<=N; j++ )
   {
   a = arr[j];
   i = j - 1;
 while( i>0 && arr[i]>a )
   {
   arr[i+1] = arr[i];
    i--;
    }
  arr[i+1] = a;
  } /* end for loop */

An added caveat: the C code in NUMERICAL RECIPES assume that array indices 
start at 1 NOT 0 !!



Response #: 2 of 2
Author:     Clayton S. Ferner
Text:       The fastest sorting algorithm depends on what you are sorting. 
But, in general, quicksort and heapsort are about the fastest you can do.  
Insertion sort is efficient for small lists, but quicksort and heapsort will 
out perform it as the input gets larger and larger.  Here is the Pascal-like 
pseudo code for quicksort:
   quicksort (Array, left, right);
   begin
  if left < right then begin
q := partition (Array, left, right);
quicksort (Array, left, q);
quicksort (Array, q + 1, right);
end;
end;
  partition (Array, left, right) : integer;
begin
pivot := Array[left];
i := pivot - 1;
j := right + 1;
   while true do begin
    repeat j := j - 1 until Array[j]   <= pivot;
    repeat i := i + 1 until Array[i]   >= pivot;
    if i < j then begin
    temp := Array[i];
    Array[i] := Array[j];
    Array[j] := temp;
    end else
    return j;
    end;
    end;

Quicksort has the disadvantage of having very bad performance on an array that 
is already sorted.  However, there exists an  algorithm called 
Random_Quicksort which overcomes this for the  most part.  Also, quicksort is 
recursive.  There does exist a version which is nonrecursive which I can give 
to you if you need.