home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1989 / 01 / einstieg / sortdemo.bas < prev    next >
Encoding:
BASIC Source File  |  1988-10-25  |  13.9 KB  |  529 lines
  1. REM * ---------------------------------------------------- *
  2. REM *                  SORTDEMO.BAS                        *
  3. REM *       Anschauliches Sortieren am Bildschirm          *
  4. REM *          (c) 1989 Gerd Kraus & TOOLBOX               *
  5. REM * ---------------------------------------------------- *
  6. REM *            Compiler: Quick Basic 4.0                 *
  7. REM *    Die Änderungen für Turbo Basic sind kommentiert   *
  8. REM * ---------------------------------------------------- *
  9.  
  10. REM -------- keine Deklarationen in Turbo Basic! ----------
  11. DECLARE SUB CursorTasten (Ch$)
  12. DECLARE SUB HolZeichen (Taste$)
  13. DECLARE SUB Auswahl (von%, Bis%, Eingabe$)
  14. DECLARE SUB Titel (Ext$)
  15. DECLARE SUB Originalwerte ()
  16. DECLARE SUB Fensterloeschen ()
  17. DECLARE SUB Markieren (Zahl%, Ort%)
  18. DECLARE SUB SchreibZeile (Start%, Ziel%, Anzahl%)
  19. DECLARE SUB ZeilenZaehler (LineNr%, Steps%, von%, nach%)
  20. DECLARE SUB ENDE (Nummer%, Anzahl%)
  21. DECLARE SUB Vorspann (Title$, LineNr%, Steps%)
  22. DECLARE SUB Zwischenschritt ()
  23. DECLARE SUB RippleSort ()
  24. DECLARE SUB BubbleSort ()
  25. DECLARE SUB ShellSort ()
  26. DECLARE SUB InsertionSort ()
  27. DECLARE SUB HeapSort ()
  28. DECLARE SUB HEAP (ii%, jj%, nn%, mm%, HHilf%)
  29. DECLARE SUB QuickSort ()
  30. DECLARE SUB HolArray (Max%, Feld%())
  31. DECLARE SUB Menue ()
  32.  
  33. REM -------------  allgemeine Variablen -------------------
  34.  
  35. Title$ = "Sortier-Demo"
  36. CO$ = "(c) 1989 G. Kraus & TOOLBOX"
  37. Version$ = "V.1.0"
  38. ENT$ = CHR$(13)
  39. DoppelAn$ = CHR$(27) + CHR$(69)         ' Doppeldruck an
  40. DoppelAus$ = CHR$(27) + CHR$(70)        ' Doppeldruck aus
  41. DruckerAn% = 0
  42.  
  43. ON KEY(3) GOSUB Drucker: KEY(3) ON
  44.  
  45. REM ------ ARRAYs für das Menü und zum Sortieren ----------
  46.  
  47. MaxMenue% = 7
  48. DIM Menu$(MaxMenue%)
  49. MaxSort% = 15       'max. 16 für gewählten Bildschirmaufbau
  50. DIM Sort%(1 TO MaxSort%)         '(1: MaxSort%) Turbo Basic
  51.  
  52. CALL Menue          'das ist das Hauptprogramm !!!
  53. END
  54.  
  55. REM ------ Ein "konventionelles" Unterprogramm ------------
  56. Drucker:
  57. REM DruckerAn% ist keine globale Variable,
  58. REM wird deshalb im Hauptmenue immer auf "0" gesetzt !
  59.  
  60.   LOCATE 25, 18: PRINT "     ";
  61.   DruckerAn% = NOT DruckerAn%
  62.   LOCATE 25, 18: COLOR 2, 4:
  63.   IF DruckerAn% THEN
  64.     PRINT " an ";
  65.   ELSE
  66.     COLOR 4, 2: PRINT " aus ";
  67.   END IF
  68.   COLOR 7, 0
  69.  
  70. RETURN
  71.  
  72.  
  73. REM -------------------------------------------------------
  74. SUB Auswahl (von%, Bis%, Eingabe$)
  75. REM liest Zeichen aus einer bestimmten Menge ein
  76.  
  77. REM 'LOCAL OK% in Turbo Basic
  78.  
  79.   DO
  80.     Eingabe$ = ""
  81.     CALL HolZeichen(Eingabe$)
  82.     Eingabe$ = UCASE$(Eingabe$)
  83.     OK% = 1
  84.     IF VAL(Eingabe$) < von% OR VAL(Eingabe$) > Bis% THEN
  85.       BEEP
  86.       OK% = 0
  87.     END IF
  88.   LOOP UNTIL OK% = 1
  89.  
  90. END SUB
  91.  
  92. REM -------------------------------------------------------
  93. SUB BubbleSort
  94. REM das 1. Element wird mit der gesamten Liste verglichen
  95.  
  96. SHARED MaxSort%, Sort%()
  97. REM LOCAL  Zeile%, Schritte%, i%, j% -- in Turbo Basic
  98.  
  99.   CALL Vorspann("Bubblesort", Zeile%, Schritte%)
  100.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  101.   FOR i% = 1 TO MaxSort% - 1
  102.     FOR j% = i% + 1 TO MaxSort%
  103.       IF Sort%(i%) > Sort%(j%) THEN
  104.         SWAP Sort%(i%), Sort%(j%)
  105.       END IF
  106.       CALL ZeilenZaehler(Zeile%, Schritte%, i%, j%)
  107.     NEXT j%
  108.   NEXT i%
  109.   CALL ENDE(Zeile%, Schritte%)
  110.  
  111. END SUB
  112.  
  113. REM -------------------------------------------------------
  114. SUB CursorTasten (Ch$)
  115. REM Abfrage der Scan-Codes wird im Programm nicht gebraucht
  116.  
  117.   IF ASC(Ch$) = 0 THEN
  118.     SELECT CASE ASC(MID$(Ch$, 2, 1))
  119.       CASE 60:    '  F1     ..  usw.
  120.       CASE ELSE
  121.         Ch$ = CHR$(0)
  122.     END SELECT
  123.   END IF
  124.  
  125. END SUB
  126.  
  127. REM -------------------------------------------------------
  128. SUB ENDE (Nummer%, Anzahl%)
  129. SHARED ENT$, MaxSort%, Sort%()
  130.  
  131.   BEEP
  132.   IF Nummer% >= 19 THEN CALL Fensterloeschen: Nummer% = 3
  133.   PRINT
  134.   PRINT MaxSort%; " Zahlen in"; Anzahl% - 1;
  135.   PRINT "Schritten sortiert"
  136.   PRINT
  137.   FOR j% = 1 TO MaxSort%
  138.     PRINT USING "####"; Sort%(j%);
  139.   NEXT j%
  140.   IF Nummer% + 3 > 21 THEN CALL Fensterloeschen
  141.   PRINT : PRINT
  142.   PRINT TAB(30); : COLOR 0, 7
  143.   PRINT " Weiter mit "; CHR$(17); CHR$(217); CHR$(32);
  144.   COLOR 7, 0
  145.   DO
  146.     CALL HolZeichen(Taste$)
  147.   LOOP UNTIL Taste$ = ENT$
  148.  
  149. END SUB
  150.  
  151. REM -------------------------------------------------------
  152. SUB Fensterloeschen
  153. REM löscht die sortierten Werte
  154. REM LOCAL   k% für Turbo Basic
  155.  
  156.   CALL HolZeichen("")
  157.   LOCATE 3, 1
  158.   FOR k% = 3 TO 23: PRINT SPACE$(80); : NEXT
  159.   LOCATE 3, 1
  160.  
  161. END SUB
  162.  
  163. REM -------------------------------------------------------
  164. SUB HEAP (ii%, jj%, nn%, mm%, HHilf%)
  165. SHARED MaxSort%, Sort%(), Zeile%, Schritte%
  166. REM LOCAL  dummy%, temp% für Turbo Basic
  167.  
  168.   ii% = nn%
  169.   dummy% = 2 * ii%
  170.   DO WHILE dummy% <= mm%
  171.     jj% = 2 * ii%
  172.     IF jj% < mm% THEN
  173.       IF Sort%(jj% + 1) > Sort%(jj%) THEN jj% = jj% + 1
  174.     END IF
  175.     IF HHilf% < Sort%(jj%) THEN
  176.       Sort%(ii%) = Sort%(jj%)
  177.       CALL ZeilenZaehler(Zeile%, Schritte%, jj%, ii%)
  178.       temp% = ii%
  179.       ii% = jj%
  180.       jj% = 2 * ii%
  181.       dummy% = jj%
  182.     ELSE
  183.       dummy% = mm% + 1
  184.     END IF
  185.   LOOP
  186.   Sort%(ii%) = HHilf%
  187.   CALL ZeilenZaehler(Zeile%, Schritte%, temp%, ii%)
  188.  
  189. END SUB
  190.  
  191. REM -------------------------------------------------------
  192. SUB HeapSort
  193. REM Ausgabe grün - rot  = Zwischenstand
  194. REM Ausgabe rot  - grün = Endstand
  195. SHARED MaxSort%, Sort%(), Zeile%, Schritte%   ' global !
  196. REM LOCAL  i%, j%, m%, n%, Hilf% für Turbo Basic
  197.  
  198.   CALL Vorspann("Heap Sort", Zeile%, Schritte%)
  199.   CALL Zwischenschritt
  200.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  201.  
  202.    ' Stufe 1 : das größte Element wird gesucht und ..
  203.    '           .. an die erste Stelle gesetzt
  204.  
  205.   m% = MaxSort%
  206.   FOR n% = INT(MaxSort% / 2) TO 1 STEP -1
  207.     Hilf% = Sort%(n%)
  208.     CALL HEAP(i%, j%, n%, m%, Hilf%)
  209.   NEXT n%
  210.  
  211.    ' Stufe 2 : das größte Element wird jeweils entfernt ..
  212.    '           .. und das nunmehr größte Element an die ..
  213.    '           .. 1. Stelle (des Restfeldes !!) gesetzt !
  214.  
  215.   n% = 1
  216.   FOR m% = MaxSort% - 1 TO 1 STEP -1
  217.     Hilf% = Sort%(m% + 1)
  218.     Sort%(m% + 1) = Sort%(1)
  219.     CALL HEAP(i%, j%, n%, m%, Hilf%)
  220.   NEXT m%
  221.   CALL ENDE(Zeile%, Schritte%)
  222.  
  223. END SUB
  224.  
  225. REM -------------------------------------------------------
  226. SUB HolArray (Max%, Feld%(1))
  227. REM das ARRAY wird mit den Zahlen 15..1 gefüllt,
  228. REM lässt sich einfach auf eigene Zahlenfolgen umstellen
  229. REM interessanter Test : Feld bereits sortiert
  230. REM LOCAL i% Turbo Basic
  231.  
  232.   FOR i% = Max% TO 1 STEP -1
  233.     Feld%(Max% + 1 - i%) = i%
  234.   NEXT
  235.  
  236.   ' FOR i% = 1 TO Max%  : Feld% (i%) = i% : NEXT
  237.  
  238. END SUB
  239.  
  240. REM -------------------------------------------------------
  241. SUB HolZeichen (Taste$)
  242. REM liest ein Zeichen von der Tastatur einschl. Scan-Codes
  243.  
  244.   DO
  245.     Taste$ = INKEY$
  246.   LOOP UNTIL Taste$ <> ""
  247.   CALL CursorTasten(Taste$)
  248.  
  249. END SUB
  250.  
  251. REM -------------------------------------------------------
  252. SUB InsertionSort
  253. REM Ausgabe grün - rot  = Zwischenstand
  254. REM Ausgabe rot  - grün = Endstand
  255. SHARED MaxSort%, Sort%()
  256. REM LOCAL  Zeile%, Schritte%, i%, j%, dummy%, Hilf% (Turbo)
  257.  
  258.   CALL Vorspann("Insertion Sort", Zeile%, Schritte%)
  259.   CALL Zwischenschritt
  260.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  261.   FOR j% = 1 TO MaxSort% - 1
  262.     Hilf% = Sort%(j% + 1)
  263.     FOR i% = j% TO 1 STEP -1
  264.       IF Hilf% > Sort%(i%) THEN EXIT FOR
  265.       Sort%(i% + 1) = Sort%(i%): dummy% = i% + 1
  266.       CALL ZeilenZaehler(Zeile%, Schritte%, i% + 1, i%)
  267.     NEXT i%
  268.     Sort%(i% + 1) = Hilf%
  269.     CALL ZeilenZaehler(Zeile%, Schritte%, i% + 1, j% + 1)
  270.   NEXT j%
  271.   CALL ENDE(Zeile%, Schritte%)
  272.  
  273. END SUB
  274.  
  275. REM -------------------------------------------------------
  276. SUB Markieren (Zahl%, Ort%)
  277. SHARED DruckerAn%, DoppelAn$, DoppelAus$
  278.  
  279.   IF Ort% = 2 THEN COLOR 2, 4 ELSE COLOR 4, 2
  280.   PRINT USING "####"; Zahl%;
  281.   COLOR 7, 0
  282.   IF DruckerAn% THEN
  283.     LPRINT DoppelAn$;
  284.     LPRINT USING "####"; Zahl%;
  285.     LPRINT DoppelAus$;
  286.   END IF
  287.  
  288. END SUB
  289.  
  290. REM -------------------------------------------------------
  291. SUB Menue
  292. SHARED MaxMenue%, Menu$(), MaxSort%, Sort%()
  293. REM LOCAL  Schleife%, Laenge%, Zeile%, Wahl$ (Turbo Basic)
  294.  
  295.   Menu$(1) = "Ripplesort "
  296.   Menu$(2) = "Bubblesort "
  297.   Menu$(3) = "Shell-Sort "
  298.   Menu$(4) = "Insertion Sort "
  299.   Menu$(5) = "Heap Sort "
  300.   Menu$(6) = "Quicksort "
  301.   Menu$(7) = "ENDE "
  302.  
  303. ' ausprobieren : Binary Sort, Maximum-Sort ...
  304.  
  305.   DO
  306.     CALL Titel("")
  307.     CALL HolArray(MaxSort%, Sort%())
  308.     Zeile% = 3
  309.     FOR Schleife% = 1 TO MaxMenue%
  310.       LOCATE Zeile% + Schleife% * 2, 14
  311.       Laenge% = 50 - LEN(Menu$(Schleife%))
  312.       PRINT Menu$(Schleife%) + STRING$(Laenge%, ".");
  313.       PRINT Schleife%
  314.     NEXT
  315.     LOCATE 25, 5: PRINT "F3 = Drucker ";
  316.     COLOR 4, 2:
  317.     IF DruckerAn% THEN PRINT " an  ";  ELSE PRINT " aus ";
  318.     COLOR 7, 0
  319.     CALL Auswahl(1, MaxMenue%, Wahl$)
  320.     SELECT CASE Wahl$
  321.       CASE "1": CALL RippleSort
  322.       CASE "2": CALL BubbleSort
  323.       CASE "3": CALL ShellSort
  324.       CASE "4": CALL InsertionSort
  325.       CASE "5": CALL HeapSort
  326.       CASE "6": CALL QuickSort
  327.       CASE "7":
  328.     END SELECT
  329.   LOOP UNTIL Wahl$ = "7"
  330.  
  331. END SUB
  332.  
  333. REM -------------------------------------------------------
  334. SUB Originalwerte
  335. REM "Statuszeile"
  336. SHARED MaxSort%, Sort%()
  337. REM LOCAL   j% (Turbo Basic)
  338.  
  339.   LOCATE 25, 1
  340.   COLOR 1, 4: PRINT SPACE$(80);
  341.   LOCATE 25, 7: PRINT "Start :";
  342.   FOR j% = 1 TO MaxSort%
  343.     PRINT USING "####"; Sort%(j%);
  344.   NEXT
  345.   COLOR 7, 0
  346.  
  347. END SUB
  348.  
  349. REM -------------------------------------------------------
  350. SUB QuickSort
  351. SHARED MaxSort%, Sort%()
  352. REM LOCAL  Zeile%, Schritte%, i%, j%, m%, k%, n%
  353. REM LOCAL  Links%, Rechts%, temp% ()       für Turbo Basic
  354.  
  355.   CALL Vorspann("Quicksort", Zeile%, Schritte%)
  356.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  357.   m% = 2 * MaxSort%
  358.   DIM temp%(m%, 0 TO 1)             '(m%, 0 : 1) -> Turbo!
  359.   k% = 1: temp%(1, 0) = 1: temp%(1, 1) = MaxSort%
  360.  
  361.   DO
  362.     Links% = temp%(k%, 0)
  363.     Rechts% = temp%(k%, 1): k% = k% - 1
  364.     DO
  365.       i% = Links%: j% = Rechts%
  366.       n% = Sort%(INT(Links% + Rechts%) / 2)
  367.       DO
  368.         WHILE Sort%(i%) < n%
  369.           i% = i% + 1
  370.         WEND
  371.         WHILE Sort%(j%) > n%
  372.           j% = j% - 1
  373.         WEND
  374.         IF i% <= j% THEN
  375.           SWAP Sort%(i%), Sort%(j%)
  376.           CALL ZeilenZaehler(Zeile%, Schritte%, i%, j%)
  377.           i% = i% + 1
  378.           j% = j% - 1
  379.         END IF
  380.       LOOP UNTIL i% > j%
  381.       IF i% < Rechts% THEN
  382.         k% = k% + 1
  383.         temp%(k%, 0) = i%
  384.         temp%(k%, 1) = Rechts%
  385.       END IF
  386.       Rechts% = j%
  387.     LOOP UNTIL Links% >= Rechts%
  388.   LOOP UNTIL k% <= 0
  389.   CALL ENDE(Zeile%, Schritte%)
  390.  
  391. END SUB
  392.  
  393. REM -------------------------------------------------------
  394. SUB RippleSort
  395. REM jeweils 2 aufeinanderfolgende Elemente vergleichen
  396. SHARED MaxSort%, Sort%()
  397. REM LOCAL  Zeile%, Schritte%, i%, Vertauscht% -> Turbo!
  398.  
  399.   CALL Vorspann("Ripplesort", Zeile%, Schritte%)
  400.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  401.   DO
  402.     Vertauscht% = 0
  403.     FOR i% = 1 TO MaxSort% - 1
  404.       IF Sort%(i%) > Sort%(i% + 1) THEN
  405.         SWAP Sort%(i%), Sort%(i% + 1)
  406.         Vertauscht% = 1
  407.       END IF
  408.       CALL ZeilenZaehler(Zeile%, Schritte%, i%, i% + 1)
  409.     NEXT i%
  410.   LOOP UNTIL Vertauscht% = 0
  411.   CALL ENDE(Zeile%, Schritte%)
  412.  
  413. END SUB
  414.  
  415. REM -------------------------------------------------------
  416. SUB SchreibZeile (Start%, Ziel%, Anzahl%)
  417. SHARED MaxSort%, Sort%(), DruckerAn%
  418. REM LOCAL   i%  -> Turbo Basic
  419.  
  420.   PRINT TAB(7);
  421.   COLOR 6, 1: PRINT USING "#### : "; Anzahl%;
  422.   FOR i% = 1 TO MaxSort%
  423.     IF Anzahl% / 2 = INT(Anzahl% / 2) THEN
  424.       COLOR 0, 3
  425.     ELSE
  426.       COLOR 0, 7
  427.     END IF
  428.     IF i% = Ziel% THEN
  429.       CALL Markieren(Sort%(i%), 1)
  430.     ELSEIF i% = Start% THEN
  431.         CALL Markieren(Sort%(i%), 2)
  432.       ELSE
  433.         PRINT USING "####"; Sort%(i%);
  434.         IF DruckerAn% THEN LPRINT USING "####"; Sort%(i%);
  435.       END IF
  436.   NEXT i%
  437.   PRINT : IF DruckerAn% THEN LPRINT
  438.   COLOR 7, 0
  439. END SUB
  440.  
  441. REM -------------------------------------------------------
  442. SUB ShellSort
  443. REM die Liste wird in 2 gleichgrosse Teillisten zerlegt
  444. REM erweitert auf Shell-Metzner-Sort
  445. SHARED MaxSort%, Sort%()
  446. REM LOCAL  Zeile%, Schritte%, i%, j%, k%, n%
  447. REM LOCAL  dummy%, Mitte%            -> Turbo Basic
  448.  
  449.   CALL Vorspann("Shell-Sort", Zeile%, Schritte%)
  450.   CALL ZeilenZaehler(Zeile%, Schritte%, 0, 0)
  451.   Mitte% = MaxSort%
  452.   Mitte% = INT(Mitte% / 2)
  453.   DO
  454.     j% = 1: k% = MaxSort% - Mitte%
  455.     DO
  456.       i% = j%
  457.       DO
  458.         n% = i% + Mitte%
  459.         IF Sort%(i%) > Sort%(n%) THEN
  460.           SWAP Sort%(i%), Sort%(n%)
  461.           dummy% = i%
  462.           i% = i% - Mitte%
  463.         ELSE
  464.           dummy% = i%: i% = 0
  465.         END IF
  466.         CALL ZeilenZaehler(Zeile%, Schritte%, dummy%, n%)
  467.       LOOP UNTIL i% < 1
  468.       j% = j% + 1
  469.     LOOP UNTIL j% > k%
  470.     Mitte% = INT(Mitte% / 2)
  471.   LOOP UNTIL Mitte% = 0
  472.   CALL ENDE(Zeile%, Schritte%)
  473.  
  474. END SUB
  475.  
  476. REM -------------------------------------------------------
  477. SUB Titel (Ext$)
  478. REM Titelbild
  479. SHARED Title$, CO$, Version$
  480. REM LOCAL    Spalte%, Help$   -> Turbo Basic
  481.  
  482.   CLS
  483.   COLOR 1, 4: PRINT SPACE$(80)
  484.   LOCATE 1, 5: PRINT Version$
  485.   Help$ = Title$ + Ext$
  486.   Spalte% = INT(80 - LEN(Help$)) / 2
  487.   LOCATE 1, Spalte%: PRINT Help$
  488.   LOCATE 1, 63: PRINT CO$
  489.   COLOR 7, 0
  490.  
  491. END SUB
  492.  
  493. REM -------------------------------------------------------
  494. SUB Vorspann (Title$, LineNr%, Steps%)
  495.  
  496.   LineNr% = 2: Steps% = 0
  497.   CALL Titel(" : " + Title$)
  498.   CALL Originalwerte
  499.   LOCATE 3, 1
  500.  
  501. END SUB
  502.  
  503. REM -------------------------------------------------------
  504. SUB ZeilenZaehler (LineNr%, Steps%, von%, nach%)
  505.  
  506.   CALL SchreibZeile(von%, nach%, Steps%)
  507.   Steps% = Steps% + 1
  508.   LineNr% = LineNr% + 1
  509.   IF LineNr% = 23 THEN
  510.     CALL Fensterloeschen
  511.     LineNr% = 2
  512.   END IF
  513.  
  514. END SUB
  515.  
  516. REM -------------------------------------------------------
  517. SUB Zwischenschritt
  518. REM "Zwischenergebnisse" werden in umgekehrter Reihenfolge
  519. REM farbig markiert
  520.  
  521.   LOCATE 24, 45: PRINT "Zwischenstand = Farbfolge : ";
  522.   COLOR 4, 2: PRINT "  "; : COLOR 2, 4: PRINT "  ";
  523.   COLOR 7, 0: LOCATE 3, 1
  524.  
  525. END SUB
  526.  
  527. REM -------------------------------------------------------
  528. REM                Ende von SORTDEMO.BAS
  529.