Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne 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 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.



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 Pascal-like 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

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory