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