From NOELL%DWIFH1.BITNET@wiscvm.wisc.edu Thu Sep 3 12:52:59 1987 Date: Thu, 03 Sep 1987 19:25 CET From: Karl-L. Noell ---------------- CUT HERE to get SORTDEMO.DOC ----------------------- Graphic Illustration of Sorting Algorithms K.L. Noell 03.Sep.87 It's difficult to explain sorting algorithms merely by verbose descrip- tions. 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 have 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 screen pixels ( x:[0...639], y:[0...199] ). 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 effects appropriate pattern 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 means sometimes the worst case. The frequencies of 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 - 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 ----------------------------- .