tutorial/qsort3.bas

   1 DECLARE SUB sort (x1!, x2!)\r
   2 DECLARE SUB check ()\r
   3 DECLARE SUB di (r1!, r2!, c!)\r
   4 DECLARE SUB disp ()\r
   5 DIM SHARED siz\r
   6 siz = 15000\r
   7 DIM SHARED arr(1 TO siz)\r
   8 DIM SHARED mark(1 TO siz)\r
   9 DIM SHARED bck(1 TO siz)\r
  10 DIM SHARED dbg\r
  11 WIDTH 80, 50\r
  12 \r
  13 dbg = 1\r
  14 CLS\r
  15 FOR i = 1 TO 1000\r
  16 LOCATE 5, 40\r
  17 PRINT i\r
  18 RANDOMIZE i\r
  19 siz = 45\r
  20 \r
  21 FOR a = 1 TO siz\r
  22   arr(a) = INT(RND * 100)\r
  23   bck(a) = arr(a)\r
  24 NEXT a\r
  25 11\r
  26 \r
  27 sort 1, siz\r
  28 disp\r
  29 \r
  30 \r
  31 fail = 0\r
  32 FOR i2 = 1 TO siz - 1\r
  33   IF arr(i2) > arr(i2 + 1) THEN\r
  34     PRINT "wrong!"\r
  35     a$ = INPUT$(1)\r
  36     fail = 1\r
  37     GOTO 10\r
  38   END IF\r
  39 NEXT i2\r
  40 10\r
  41 \r
  42 IF fail = 1 THEN\r
  43   FOR i2 = 1 TO siz\r
  44     arr(i2) = bck(i2)\r
  45   NEXT i2\r
  46   dbg = 1\r
  47   GOTO 11\r
  48 END IF\r
  49 \r
  50 NEXT i\r
  51 \r
  52 SUB di (r1, r2, c)\r
  53 \r
  54 mark(r1) = c\r
  55 mark(r2) = c\r
  56 disp\r
  57 mark(r1) = 0\r
  58 mark(r2) = 0\r
  59 \r
  60 \r
  61 END SUB\r
  62 \r
  63 SUB disp\r
  64 FOR i = 1 TO siz\r
  65   LOCATE i, 1\r
  66   COLOR 15, mark(i)\r
  67   PRINT arr(i), "    ", i\r
  68 NEXT i\r
  69 \r
  70 IF dbg = 1 THEN a$ = INPUT$(1)\r
  71 'SOUND 0, .05\r
  72 END SUB\r
  73 \r
  74 SUB sort (x1, x2)\r
  75 min = 99999\r
  76 max = -99999\r
  77 FOR i = x1 TO x2\r
  78   IF arr(i) > max THEN max = arr(i)\r
  79   IF arr(i) < min THEN min = arr(i)\r
  80 NEXT i\r
  81 sv = (max + min) / 2\r
  82 LOCATE 1, 50\r
  83 PRINT sv\r
  84 'disp\r
  85 di x1, x2, 4\r
  86 IF x1 >= x2 THEN GOTO 3\r
  87 \r
  88 IF x1 + 1 = x2 THEN\r
  89   IF arr(x1) > arr(x2) THEN SWAP arr(x1), arr(x2)\r
  90   GOTO 3\r
  91 END IF\r
  92 \r
  93 xl1 = x1\r
  94 xl2 = x2\r
  95 \r
  96 \r
  97 1\r
  98 di xl1, xl2, 1\r
  99 IF arr(xl1) > sv THEN\r
 100 2\r
 101   IF arr(xl2) < sv THEN\r
 102     SWAP arr(xl1), arr(xl2)\r
 103     xl1 = xl1 + 1\r
 104     xl2 = xl2 - 1\r
 105   ELSE\r
 106     xl2 = xl2 - 1\r
 107     di xl1, xl2, 1\r
 108     IF xl1 = xl2 THEN GOTO 4\r
 109     GOTO 2\r
 110   END IF\r
 111 ELSE\r
 112   xl1 = xl1 + 1\r
 113 END IF\r
 114 \r
 115 IF xl1 < xl2 THEN GOTO 1\r
 116 'IF arr(xl1) < sv THEN xl1 = xl1 + 1\r
 117 'IF arr(xl1) < sv THEN xl1 = xl1 + 1\r
 118 4\r
 119 mark(xl1) = 14\r
 120 disp\r
 121 mark(xl1) = 0\r
 122 \r
 123 IF xl1 = x2 THEN\r
 124   sort x1, xl1 - 1\r
 125 ELSE\r
 126   IF arr(xl1) > sv THEN\r
 127     sort x1, xl1 - 1\r
 128     sort xl1, x2\r
 129   ELSE\r
 130     sort x1, xl1\r
 131     sort xl1 + 1, x2\r
 132   END IF\r
 133 END IF\r
 134 3\r
 135 END SUB\r
 136 \r