Kirjautuminen

Haku

Tehtävät

Keskustelu: Koodit: QB: QuickSort-lajittelu

Antti Laaksonen [24.02.2002 12:30:39]

#

QuickSort-lajittelu on yksi parhaimmista lajittelutavoista. Tämän menetelmän muuten keksi C. A. R. Hoare vuonna 1962. Rekursiivisen lajittelualiohjelman teko onnistuu myös QBasicilla, ja se on esitetty tässä.

Ensin pääohjelma, joka esittelee QuickSort-komentoa:

DIM SHARED maara% 'vaihtojen määrän laskuri
CLS
DIM t(1 TO 15) AS INTEGER
RANDOMIZE TIMER
FOR i = 1 TO UBOUND(t)
  t(i) = INT(RND * 89) + 10
  PRINT t(i); 'alkuperäinen rivi
NEXT
PRINT
PRINT

x% = QuickSort(t(), 1, UBOUND(t))

FOR i = 1 TO UBOUND(t)
  PRINT t(i); 'järjestelty rivi
NEXT
PRINT
PRINT
PRINT " Vaihtoja:"; maara%

Ja varmaan itse funktiostakin on hyötyä:

FUNCTION Lajittele (t() AS INTEGER, vasen%, oikea%)
  a% = t(vasen%)
  b% = vasen% - 1
  c% = oikea% + 1
  DO
    DO
      c% = c% - 1
    LOOP WHILE t(c%) > a%
    DO
      b% = b% + 1
    LOOP WHILE t(b%) < a%
    IF b% < c% THEN
      SWAP t(b%), t(c%)
      maara% = maara% + 1 'laskee vaihdot; tämä rivi tulee
                          'poistaa lopullisesta ohjelmasta
    ELSE
      Lajittele = c%
      EXIT FUNCTION
    END IF
  LOOP
END FUNCTION

FUNCTION QuickSort (t() AS INTEGER, vasen%, oikea%)
  IF vasen% < oikea% THEN
    kohta% = Lajittele(t(), vasen%, oikea%)
    x% = QuickSort(t(), vasen%, kohta%)
    x% = QuickSort(t(), kohta% + 1, oikea%)
  END IF
END FUNCTION

Viisas [25.07.2002 12:54:39]

#

Mää olen viisas ja keksin frontensiivisen järjestely tavan luvuille. Se on niin yksinkertainen että sen voi toteuttaa jopa näissä textikentissä. Seuraavat luvut ovat järjestelty käyttäen frontensiivista järjesteelymekaniikkaa:

9+03 4300948 44874737 02 218923 74984 2172728 3737189 273738713 48717832 8743

Eikö ollutkin uskomatonta... mutta totta se on.

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta