

Sorting Algorithm  Hypercard
Name: Brian Allen
Status: N/A
Age: N/A
Location: N/A
Country: N/A
Date: Around 1993
Question:
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 78 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.
Replies:
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 !!
John Hawley
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 Pascallike
pseudo code for quicksort:
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.
Clayton S. Ferner
Click here to return to the Computer Science Archives
 
Update: June 2012

