From NOELL%DWIFH1.BITNET@wiscvm.wisc.edu Tue Sep 1 09:19:21 1987 Return-Path: Received: from anl-mcs.ARPA by dasher.mcs.anl (3.2/SMI-3.2) id AA01801; Tue, 1 Sep 87 09:19:17 CDT Received: from wiscvm.wisc.edu (wiscvm.wisc.edu.ARPA) by anl-mcs.ARPA (4.12/4.9) id AA06260; Tue, 1 Sep 87 09:23:02 cdt Message-Id: <8709011423.AA06260@anl-mcs.ARPA> Received: from DWIFH1.BITNET by wiscvm.wisc.edu ; Tue, 01 Sep 87 09:24:07 CDT Date: Tue, 01 Sep 1987 15:30 CET From: Karl-L. Noell Subject: contributing a PD - program To: Jack Dongarra Status: RO I'd like to contribute something for your NETLIBD math. library. It's a collection of Turbo-Pascal programs to study and illustrate various sorting algorithms by real time animated pixel graphics. Enclosed please find SORTDEMO.DOC and SHELL.PAS as *one* example. The whole package has about 800 recs. Please let me know, if you are interested, and tell me how to submit this stuff, which is designed to run on an IBM-AT or clone with CGA or EGA using Borland's Turbo-Pascal (Tm) under DOS. Regards Karl-L. Noell fhw (Wiesbaden, W.Germany) ---------------- CUT HERE to get SORTDEMO.DOC ------------------------ Graphic Illustration of Sorting Algorithms K.L. Noell 01.Sep.87 It's difficult to explain sorting algorithms merely by verbose expla- nations. They are either easy to understand and simple to design but they are very slow and inefficient; or they run fairly quick but their design and implementation is rather complex and troublesome. For teaching purpose I realized an idea which illustrates various sorting algorithms with the aid of real time animated pixel graphics. Keys to be sorted are 640 random integers distributed over the inter- val [0 ... 199]. These elements are stored in an array which is mapped to corresponding pixels ( x:[0...639], y:[0...200] ). In the beginning, this pixel distribution looks like a starry sky. After the sorting procedure is started, you can watch its progress directly. Swapping and moving of elements cause appropriate screen updates by shifting the pixels towards their final ascending order. Depending on the particular sorting strategy, this works very slow and fussy or it is intelligible sophisticated and quick. You can compare features and performance of different sorting algorithms; after processing the randomly distributed keys, the sorting can be started once more to deal with an array already sorted, but in opposite (descending) order which gives sometimes the worst case. Swaps and loops (comparisons) are counted. Turbo-Pascal programs are provided to demonstrate the following sorting algorithms: BubbleSort, HeapSort, LinearSort, QuickSort, ShakeSort, ShellSort . My examples are based on sorting algorithms from the following books: A.V. Aho; J.E. Hopcroft; J.D. Ullman: Data Structures and Algorithms. Addison-Wesley, Amsterdam etc (1983) Sara Baase: Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, Amsterdam etc (1978) I have written and tested these programs with Turbo-Pascal (3.01A) under DOS 3.1, running in an IBM-AT02 and also in clones with CGA and EGA. ===> Disclaimer Notice <=== This SORTDEMO.PAS - package is provided for educational purpose. Neither the author nor the distributor makes any warranty or assumes any liability or responsibility for accuracy, completeness or usefulness. All risk of use is on the user. It may be freely copied but may not be sold for profit. Please keep the credits which refer to author and provenance. Suggestions, problems: please send E-mail to NOELL@DWIFH1.BITNET or contact: Prof.Dr. Karl-L. Noell FHW - FB MND Am Brueckweg 26 D-6090 Ruesselsheim (W. Germany) ---------------- End of SORTDEMO.DOC ------------------------ ---------------- CUT HERE to get SHELL.PAS ------------------------ { K.L. Noell, fhw 09/01/87 } Program ShellSort_Demo (output); Const n = 639; { number of columns : x-coordinates } range = 199; { actual size : y-coordinates } clear_pixel = 0; set_pixel = 3; VAR k: INTEGER; num,loops,swaps,aloops,aswaps: REAL; A : ARRAY [1..n] of INTEGER; PROCEDURE Swap ( VAR x,y:INTEGER ); VAR temp: INTEGER; BEGIN temp := x; x := y; y := temp; swaps := swaps + 1; END; { Swap } PROCEDURE ShellSort ; VAR i,j,incr:INTEGER; BEGIN incr := n DIV 2; WHILE incr > 0 DO BEGIN FOR i := incr + 1 TO n do BEGIN j := i - incr; loops := loops + 1; WHILE j > 0 DO if A[j] > A[j+incr] THEN BEGIN loops := loops + 1; Plot (j,A[j],clear_pixel); Plot ((j+incr),A[j+incr],clear_pixel); Swap (A[j],A[j+incr]); Plot (j,A[j],set_pixel); Plot ((j+incr),A[j+incr],set_pixel); j := j - incr END ELSE j := 0 {break} END; incr := incr DIV 2; END; END; { ShellSort } BEGIN (************ Mainrogram ShellSort_Demo ******************) HiRes; HiResColor (Magenta); { a): generating and sorting } FOR k:=1 TO n DO BEGIN { randomly distributed keys } num := range*RANDOM; A [k] := TRUNC (num); Plot (k,A[k],set_pixel); END; GraphBackground (Magenta); Palette (2); {Sorting start:} loops := 0; swaps := 0; DELAY (1000); ShellSort ; aloops := loops; aswaps := swaps; Writeln (' Shell Sort a) Loops,Swaps: ',loops,swaps); Writeln; Writeln ('b) Press any key to process with an array already sorted,'); Writeln (' but in opposite direction.'); REPEAT UNTIL KeyPressed; Hires; { b): generating and sorting } FOR k:=1 TO n DO BEGIN { keys beeing in opposed order } num := (n-k)/(n/range); A [k] := TRUNC (num); Plot (k,A[k],set_pixel); END; {Sorting start:} loops := 0; swaps := 0; DELAY (1000); ShellSort ; Writeln (' Shell Sort a) Loops,Swaps: ',aloops,aswaps); Writeln (' Shell Sort b) Loops,Swaps: ',loops,swaps); Writeln; Writeln (' Press any key to exit.'); REPEAT UNTIL KeyPressed; TextMode; END. (************ Mainrogram ShellSort_Demo ******************) ---------------- End of SHELL.PAS ------------------------ .