home *** CD-ROM | disk | FTP | other *** search
/ 64'er 1985 August / 64er_Magazin_85-08_1985_Markt__Technik_de.d64 / quicksort (.txt) < prev    next >
Commodore BASIC  |  2022-10-26  |  2KB  |  100 lines
  1. 10 rem erstellen eines feldes zum
  2. 20 rem sortieren.
  3. 30 rem das erstellen kann zufaellig
  4. 40 rem oder gezielt (durch eingabe)
  5. 50 rem erfolgen.
  6. 60 rem
  7. 70 rem sortieralgorithmen erhalten die
  8. 80 rem zeilennummern von 10000 bis 50000
  9. 90 rem sie benoetigen jeweils diesen
  10. 99 rem vorspann zur ausfuehrung.
  11. 100 rem herstellung eines arrays:
  12. 110 rem arrayvariable      - a$
  13. 120 rem schleifenvariablen - x, y, z
  14. 130 rem hilfsvariablen     - b$, c$, d$
  15. 140 rem dreiecktausch mit  - s$
  16. 150 print"[147]":clr
  17. 160 print"soll von h[146]and oder z[146]ufaellig erstellt":print
  18. 170 input"werden ";x$
  19. 180 ifx$<>"h"andx$<>"z"then150
  20. 190 ifx$="h"thengosub220:gosub1000:goto210
  21. 200 gosub220:gosub2000
  22. 210 goto4000: rem weitermachen
  23. 220 rem anzahl der elemente bestimmen
  24. 230 print:input"anzahl der elemente ";a
  25. 240 if a>10000thenprint:print"zu viele elemente":goto230
  26. 250 ifa<10thenprint:print"zu wenige elemente":goto230
  27. 255 dim a$(a)
  28. 260 input"d[146]rucker oder b[146]ildschirm ";y$
  29. 270 ify$<>"d"andy$<>"b"then260
  30. 280 ify$="d"thend=4:goto300
  31. 290 d=3
  32. 300 return
  33. 1000 rem eingabe von hand
  34. 1010 print"[147]"
  35. 1020 print:print"sie muessen jetzt"a" elemente eingeben!":print:print
  36. 1030 print"jedes element besteht aus 3 zeichen.":print:print
  37. 1040 forx=1toa
  38. 1050 printx". ";:input"element";a$(x)
  39. 1060 iflen(a$(x))<>3then1050
  40. 1070 nextx
  41. 1080 return
  42. 2000 rem zufaellige eingabe
  43. 2010 print"[147]"
  44. 2020 print:print"es werden jetzt"a" elemente zufaellig":print:print"ausgewaehlt"
  45. 2030 print:print"jedes element besteht aus 3 zeichen.":print:print
  46. 2040 forx=1toa
  47. 2050 a$(x)=""
  48. 2060 fory=1to3:a$(x)=a$(x)+chr$(int(rnd(ti)*25)+65):nexty
  49. 2070 nextx
  50. 2080 return
  51. 3000 rem zwischenausgabe der elemente
  52. 3010 for i=1toa-9step10
  53. 3020 for j=itoi+9:print#1,a$(j)" ";:nextj
  54. 3030 print#1:nexti
  55. 3040 return
  56. 4000 rem weitermachen
  57. 4005 open1,d
  58. 4010 print"[147]ausgabe des erstellten feldes"
  59. 4020 print
  60. 4030 gosub3000
  61. 4040 rem sortierung startet
  62. 4050 rem
  63. 10000 rem sortieren durch zerlegen
  64. 10010 rem
  65. 10020 rem        quicksort
  66. 10030 rem
  67. 10040 rem lg = linke grenze
  68. 10050 rem rg = rechte grenze
  69. 10060 rem vg$ = vergleichselement
  70. 10070 rem
  71. 10080 rem eingang des hauptmoduls
  72. 10090 rem
  73. 10100 dimlg(100),rg(100):z=0:lg(1)=1:rg(1)=a
  74. 10110 gosub10200: rem quicksort
  75. 10120 goto50000:rem ende
  76. 10200 rem eingang der rekursivschleife
  77. 10210 z=z+1:iflg(z)>=rg(z)then10350
  78. 10220 x=lg(z):y=rg(z)
  79. 10225 rem vergleichselement holen
  80. 10230 vg$=a$(int((x+y)/2))
  81. 10240 ifx>ythen10320
  82. 10250 ifa$(x)<vg$thenx=x+1:goto10250
  83. 10260 ifa$(y)>vg$theny=y-1:goto10260
  84. 10270 ifx>ythen10320
  85. 10280 s$=a$(x):a$(x)=a$(y):a$(y)=s$
  86. 10290 x=x+1:y=y-1
  87. 10300 goto10240
  88. 10310 rem
  89. 10320 gosub3000
  90. 10330 rg(z+1)=y:lg(z+1)=lg(z):gosub 10200
  91. 10340 lg(z+1)=x:rg(z+1)=rg(z):gosub 10200
  92. 10350 z=z-1:return
  93. 10360 rem
  94. 50000 rem endebehandlung
  95. 50010 print#1
  96. 50020 gosub 3000
  97. 50030 print#1,a;" elemente"
  98. 50040 print#1:print#1:close1
  99. 50050 end
  100.