home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / SORTDEMO.ZIP / SORTDEMO.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1992-04-15  |  11.0 KB  |  293 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Source File : SORTDEMO.PAS                               ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO                                                        ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Demonstration of various sorting algorithms. Requires VGA (uses mode 13h, ║
  12. ║ 320x200x256 colors).                                                      ║
  13. ║                                                                           ║
  14. ║ Since the reason for creating this program is to demonstrate sorting      ║
  15. ║ algorithms, and due to the many different aspects involved in writing     ║
  16. ║ this program, the source code has been broken down into several include   ║
  17. ║ files to make it easier to find the desired section of code for studying. ║
  18. ║                                                                           ║
  19. ║ The include files are...                                                  ║
  20. ║                                                                           ║
  21. ║   SDGRAF  .INC  == basic graphics routines                                ║
  22. ║   SDKEY   .INC  == keyboard routines                                      ║
  23. ║   SDTIME  .INC  == time-keeping routines                                  ║
  24. ║   SDFILE  .INC  == file related routines                                  ║
  25. ║   SDDISP  .INC  == info-display & menuing routines                        ║
  26. ║   SDMISC  .INC  == misc routines                                          ║
  27. ║   SDSORT01.INC  == bubble sort routine                                    ║
  28. ║   SDSORT02.INC  == short-bubble sort routine                              ║
  29. ║   SDSORT03.INC  == selection sort routine                                 ║
  30. ║   SDSORT04.INC  == merge sort routine                                     ║
  31. ║   SDSORT05.INC  == quick sort #1 routine                                  ║
  32. ║   SDSORT06.INC  == quick sort #2 routine                                  ║
  33. ║   SDSORT07.INC  == heap sort routine                                      ║
  34. ║                                                                           ║
  35. ╚═══════════════════════════════════════════════════════════════════════════╝
  36.                                                                            *)
  37. program SortDemo;
  38. {$M 65520, 0, 655360}  (* StackSize, HeapMin, HeapMax *)
  39.  
  40. uses
  41.   Crt, Dos, Graph, BGIFont;
  42.  
  43. (*
  44. ╔═══════════════════════════════════════════════════════════════════════════╗
  45. ║                             GLOBAL DECLARATIONS                           ║
  46. ╚═══════════════════════════════════════════════════════════════════════════╝
  47. ┌───────────────────────────────────────────────────────────────────────────┐
  48. │                           sort-info declarations                          │
  49. └───────────────────────────────────────────────────────────────────────────┘
  50.                                                                            *)
  51. const
  52.   MaxNumElements = 8000;
  53.  
  54. type
  55.   IndexType = 0..MaxNumElements;
  56.  
  57.   MethodType = (Bubble,ShortBubble,Selection,Merge,Quick1,Quick2,Heap);
  58.  
  59.   OperationType = (Mix, Sort, Quit);
  60.  
  61.   ListElemType = record
  62.                    Key   : longint;  (* field to be sorted on  *)
  63.                    Color : byte;     (* designates block color *)
  64.                  end; (* ListElemType *)
  65.  
  66.   ListType = array[1..MaxNumElements] of ListElemType;
  67.  
  68.   InfoType = record
  69.                xElems    : word;           (* # of block rows          *)
  70.                yElems    : word;           (* # of block columns       *)
  71.                Len       : IndexType;      (* effective size of array  *)
  72.                Method    : MethodType;     (* sorting method to use    *)
  73.                Operation : OperationType;  (* operation to perform     *)
  74.                Save      : boolean;        (* save info to file toggle *)
  75.                Sorted    : boolean;        (* status flag              *)
  76.                List      : ListType;       (* the array to be sorted   *)
  77.              end; (* ListType *)
  78.  
  79. var
  80.   Info : InfoType;
  81.  
  82. (*
  83. ┌───────────────────────────────────────────────────────────────────────────┐
  84. │                          sort-titles declarations                         │
  85. └───────────────────────────────────────────────────────────────────────────┘
  86.                                                                            *)
  87. const
  88.   NumTitles = 7;
  89.  
  90. type
  91.   SortTitlesType = array[1..NumTitles] of string;
  92.  
  93. const
  94.   SortTitles : SortTitlesType = (
  95.     'Bubble Sort',
  96.     'Short Bubble',
  97.     'Selection Sort',
  98.     'Merge Sort',
  99.     'QuickSort #1',
  100.     'QuickSort #2',
  101.     'Heap Sort');
  102.  
  103. (*
  104. ┌───────────────────────────────────────────────────────────────────────────┐
  105. │                          time-keeping declarations                        │
  106. └───────────────────────────────────────────────────────────────────────────┘
  107.                                                                            *)
  108. type
  109.   TimeType = record
  110.                Hour   : word;
  111.                Minute : word;
  112.                Second : word;
  113.                Sec100 : word;
  114.              end; (* TimeType *)
  115.  
  116.   DateType = record
  117.                Year      : word;
  118.                Month     : word;
  119.                Day       : word;
  120.                DayOfWeek : word;
  121.              end; (* DateType *)
  122.  
  123.   TimeDateType = record
  124.                    Time : TimeType;
  125.                    Date : DateType;
  126.                  end; (* TimeDateType *)
  127.  
  128.   DiffType = record
  129.                Days    : word;
  130.                Hours   : word;
  131.                Minutes : word;
  132.                Seconds : word;
  133.                Sec100s : word;
  134.              end; (* DiffType *)
  135.  
  136. (*
  137. ┌───────────────────────────────────────────────────────────────────────────┐
  138. │                            keyboard declatations                          │
  139. └───────────────────────────────────────────────────────────────────────────┘
  140.                                                                            *)
  141. type
  142.   KeyRecType = record
  143.                  Extended : boolean;
  144.                  Ch       : char;
  145.                end; (* KeyRecType *)
  146.  
  147. const
  148.   UpArrowKey = #072;  (* extended *)
  149.   DnArrowKey = #080;  (* extended *)
  150.   LfArrowKey = #075;  (* extended *)
  151.   RtArrowKey = #077;  (* extended *)
  152.   EnterKey   = #013;  (* non-extended *)
  153.  
  154. var
  155.   KeyRec : KeyRecType;
  156.  
  157. (*
  158. ┌───────────────────────────────────────────────────────────────────────────┐
  159. │                        graphics-related declarations                      │
  160. └───────────────────────────────────────────────────────────────────────────┘
  161.                                                                            *)
  162. const
  163.   xMax = 320;
  164.   yMax = 200;
  165.  
  166. type
  167.   ColorsType = record
  168.                  Red : byte;
  169.                  Grn : byte;
  170.                  Blu : byte;
  171.                end; (* ColorsType *)
  172.  
  173.   PaletteType = array[0..255] of ColorsType;
  174.  
  175. var
  176.   DefaultPalette : PaletteType;
  177.   Palette        : PaletteType;
  178.   OldExitProc    : pointer;
  179.  
  180. (*
  181. ┌───────────────────────────────────────────────────────────────────────────┐
  182. │                                include files                              │
  183. └───────────────────────────────────────────────────────────────────────────┘
  184.                                                                            *)
  185. {$I SDGRAF.INC}
  186. {$I SDKEY.INC}
  187. {$I SDTIME.INC}
  188. {$I SDFILE.INC}
  189. {$I SDDISP.INC}
  190. {$I SDMISC.INC}
  191. {$I SDSORT01.INC}
  192. {$I SDSORT02.INC}
  193. {$I SDSORT03.INC}
  194. {$I SDSORT04.INC}
  195. {$I SDSORT05.INC}
  196. {$I SDSORT06.INC}
  197. {$I SDSORT07.INC}
  198.  
  199. (*─────────────────────────────────────────────────────────────────────────*)
  200.  
  201.  
  202. (*
  203. ╔═══════════════════════════════════════════════════════════════════════════╗
  204. ║                           INITIALIZATION ROUTINES                         ║
  205. ╚═══════════════════════════════════════════════════════════════════════════╝
  206.                                                                            *)
  207. procedure Initialize (var Info           : InfoType;
  208.                       var DefaultPalette : PaletteType;
  209.                       var Palette        : PaletteType;
  210.                       var OldExitProc    : pointer);
  211.  
  212. begin  (* Initialize *)
  213.   Randomize;
  214.   InitMode13h;
  215.   InitFonts;
  216.   InitExitProc(OldExitProc);
  217.   InitPalettes(DefaultPalette, Palette);
  218.   InitList(Info);
  219.   TitleScreen;
  220. end;   (* Initialize *)
  221.  
  222. (*
  223. ╔═══════════════════════════════════════════════════════════════════════════╗
  224. ║                                MAIN ROUTINES                              ║
  225. ╚═══════════════════════════════════════════════════════════════════════════╝
  226.                                                                            *)
  227. procedure Run (var Info           : InfoType;
  228.                    DefaultPalette : PaletteType);
  229.  
  230. var
  231.   StartTD : TimeDateType;
  232.   StopTD  : TimeDateType;
  233.   Diff    : DiffType;
  234.  
  235.   (*───────────────────────────────────────────────────────────────────────*)
  236.  
  237.   procedure CallSort (var Info  : InfoType;
  238.                       var Start : TimeDateType;
  239.                       var Stop  : TimeDateType;
  240.                       var Diff  : DiffType);
  241.  
  242.   begin  (* CallSort *)
  243.     ShowArray(Info);
  244.  
  245.     GetTimeDate(Start);
  246.  
  247.     case Info.Method of
  248.       Bubble      : BubbleSort(Info);
  249.       ShortBubble : ShortBubbleSort(Info);
  250.       Selection   : SelectionSort(Info);
  251.       Merge       : MergeSort(Info, 1, Info.Len);
  252.       Quick1      : QuickSort1(Info, 1, Info.Len);
  253.       Quick2      : QuickSort1(Info, 1, Info.Len);
  254.       Heap        : HeapSort(Info);
  255.     end; (* case *)
  256.  
  257.     GetTimeDate(Stop);
  258.     Beep;
  259.     CalcTimeDateDifference(Start,Stop,Diff);
  260.     FlushAndWait;
  261.   end;   (* CallSort *)
  262.  
  263.   (*───────────────────────────────────────────────────────────────────────*)
  264.  
  265.   procedure Terminate ( DefaultPalette : PaletteType);
  266.   begin  (* Terminate *)
  267.     SetRGBPalette(DefaultPalette);
  268.     Halt(0);
  269.   end;   (* Terminate *)
  270.  
  271.   (*───────────────────────────────────────────────────────────────────────*)
  272.  
  273. begin  (* Run *)
  274.   repeat
  275.     Menu(Info);
  276.     case Info.Operation of
  277.       Mix  : MixArray(Info);
  278.       Sort : begin
  279.                CallSort(Info, StartTD, StopTD, Diff);
  280.                ShowAnalysis(Info, StartTD, StopTD, Diff);
  281.              end;
  282.       Quit : Terminate(DefaultPalette);
  283.     end; (* case *)
  284.   until true = false;
  285. end;   (* Run *)
  286.  
  287. (*═════════════════════════════════════════════════════════════════════════*)
  288.  
  289. begin (* SortDemo / main *)
  290.   Initialize(Info, DefaultPalette, Palette, OldExitProc);
  291.   Run(Info, DefaultPalette);
  292. end.  (* SortDemo / main *)
  293.