Pole v jazyku Pascal (tretia časť)

prvá časť -- druhá časť -- tretia časť

Polia nám umožňujú pracovať s mnohými číslami naraz. Ale opakované zadávanie mnohých čísel z klávesnice je nuda. Napíšme si teda krátky program, ktorý načíta údaje do poľa z textového súboru "vstup.txt". Takto môžeme program mnohokrát spustiť s rovnakými číslami; a ak budeme potrebovať iné čísla, stačí zmeniť súbor, alebo zmeniť v programe názov použitého súboru.

const MAX_PRVKOV = 100;

var
  prvky : Array[1..MAX_PRVKOV] of Integer;
  pocet : Integer;

procedure nacitaj_prvky;
var
  subor : Text;
  i : Integer;
begin
  Assign(subor, 'vstup.txt');
  Reset(subor);
  ReadLn(subor, pocet);
  for i := 1 to pocet do begin
    ReadLn(subor, prvky[i])
  end;
  Close(subor)
end;

var i : Integer;

begin
  nacitaj_prvky;
  for i := 1 to pocet do begin
    Write(prvky[i], ' ');
  end;
  WriteLn('-- spolu ', pocet, ' prvkov.')
end

Čítanie údajov z textového súboru je podobné ako čítanie údajov z klávesnice, len je tu pár pomocných funkcií navyše. Premenná typu "Text" označuje textový súbor. Funkcia "Assign" povie, s ktorým súborom budeme pomocou tejto premennej pracovať. Funkcia "Reset" otvorí existujúci súbor, a funkcia "Close" ho zase uzavrie. Zo súboru čítame pomocou príkazu "ReadLn", podobne ako z klávesnice, akurát ako prvý parameter doplníme, z ktorého súboru práve čítame.

Pomocný súbor "vstup.txt" môže vyzerať napríklad takto. (Prvé číslo udáva počet prvkov v poli, nasledujú jednotlivé prvky poľa, každé číslo na samostatnom riadku.)

Ak chceme s hodnotami v poli pracovať aj neskôr, môžeme si ich uložiť do textového súboru. Postup je opäť podobný ako pri písaní na obrazovku, len máme navyše funkcie "Assign", "Rewrite" a "Close". Funkcia "Rewrite" vytvorí nový súbor s daným názvom; ak taký súbor už existuje, vymaže ho a začne s novým prázdnym súborom.

Vytvoríme si pole s 50 náhodnými číslami. Funkcia "Random(10000)" vráti náhodné celé číslo od 0 do 9999. Čísla v skutočnosti nie sú celkom náhodné; síce tak vyzerajú, ale keď program spustíme znova, vytvorí tie isté čísla. Ale pre nás to momentálne postačí.

const MAX_PRVKOV = 100;

var
  prvky : Array[1..MAX_PRVKOV] of Integer;
  pocet : Integer;

procedure zapis_prvky;
var
  subor : Text;
  i : Integer;
begin
  Assign(subor, 'vystup.txt');
  Rewrite(subor);
  WriteLn(subor, pocet);
  for i := 1 to pocet do begin
    WriteLn(subor, prvky[i])
  end;
  Close(subor)
end;

var i : Integer;

begin
  pocet := 50;
  for i := 1 to pocet do begin
    prvky[i] := Random(10000)
  end;
  zapis_prvky;
  WriteLn('Hotovo, udaje su zapisane v subore vystup.txt.')
end

Takže teraz už môžeme pohodlne pracovať aj s veľkými poľami čísel. (Ak budete chcieť vytvárať aj väčšie polia, nezabudnite primerane zväčšiť konštantu "MAX_PRVKOV".) Čo s nimi urobíme? Poďme ich napríklad zoradiť podľa veľkosti; od najmenšieho čísla po najväčšie.

Jednoduchý postup na zoradenie: budeme postupne porovnávať susediace čísla (prvé s druhým, druhé s tretím, atď). Ak sú v nesprávnom poradi, čiže ak to skoršie je väčšie ako to neskoršie, tak ich vymeníme. Takto prejdeme všetky susedné dvojice. Ak už bolo všetko v poriadku, čiže ak sme nemuseli vymieňať žiadnu dvojicu, máme všetky čísla usporiadané a končíme. Ak sa niečo zmenilo, tak zase prejdeme cez všetky dvojice... a zase, a zase, až kým sa všetky čísla správne neusporiadajú.

Výmena dvoch čísel je v jazyku Pascal trochu komplikovaná tým, že môžeme v jednom príkaze priradiť hodnotu iba do jednej premennej. Výmena typu "x:=y; y:=x" by nefungovala, pretože pri prvom kroku by sa do premennej "x" priradila hodnota z premennej "y", a potom by už obe premenné mali rovnakú hodnotu, a pôvodná hodnota premennej "x" by sa nám tak stratila. Môžeme si ju však dočasne zapamätať do pomocnej premennej "p" a urobiť výmenu takto: "p:=x; x:=y; y:=p".

Ešte poznámka k opakovaniu: keď v počítačovom programe napíšeme, že sa nejaká činnosť má opakovať, oplatí sa zamyslieť nad rizikom, že pri určitých vstupných údajoch sa program "zacyklí" a bude opakovať donekonečna. Pri príkaze "for" toto nebezpečenstvo nehrozí, pretože je vopred známe, koľko opakovaní bude. Nebezpečné sú v tomto zmysle príkazy "while" a "repeat until", a takisto rekurzia. Na porovnávanie všetkých susediacich čísel sa hodí príkaz "for". Ale na opakovanie tohoto prechádzania dovtedy, kým nebude všetko v poriadku, sa viac hodí "repeat until".

Treba sa teda zamyslieť, či náš algoritmus určite vedie k usporiadanému stavu čísel, keď sa bude môcť vypnúť. Našťastie sa dá jednoducho logicky ukázať (nad detailmi sa zamyslite sami), že po prvom prechode všetkými susednými dvojicami sa najväčšie číslo dostane na posledné miesto; po druhom prechode sa aj druhé najväčšie číslo dostane na správne miesto... takže sa postupne usporiadajú všetky.

Dosť bolo špekulovania, ideme programovať. Ak chcete pracovať s pekne veľkým poľom čísel, môžete si súbor "vystup.txt" vytvorený v poslednom príklade premenovať na "vstup.txt", takže vytvorené náhodné čísla teraz usporiadame.

const MAX_PRVKOV = 100;

var
  prvky : Array[1..MAX_PRVKOV] of Integer;
  pocet : Integer;

procedure nacitaj_prvky;
...viď vyššie...

procedure zapis_prvky;
...viď vyššie...

var
  i : Integer;
  pomocne : Integer;
  koniec : Boolean;

begin
  nacitaj_prvky;
  repeat
    koniec := true;
    for i := 1 to pocet-1 do begin
      if prvky[i] > prvky[i+1] then begin
        pomocne := prvky[i];
        prvky[i] := prvky[i+1];
        prvky[i+1] := pomocne;
        koniec := false
      end
    end
  until koniec;
  zapis_prvky;
  WriteLn('Hotovo, vysledky su zapisane v subore vystup.txt.')
end

Ak všetko dobre dopadlo, usporiadané čísla sú uložené v súbore "vystup.txt". Nezabudnite, že prvý riadok v súbore označuje počet prvkov v poli, až tie ďalšie sú samotné prvky.

Existuje mnoho algoritmov ako zoradiť čísla v poli. Tento algoritmus je jeden z najpomalších (ale zato sa najľahšie vysvetľuje). Existujú aj omnoho rýchlejšie algoritmy. Presná rýchlosť závisí od počtu zoraďovaných prvkov; čím viac ich je (predstavte si tisíc alebo milión prvkov; milión prvkov v poli vám však Pascal z technických príčin nedovolí), tým výraznejší je rozdiel v rýchlosti medzi jednotlivými algoritmami.

Časová náročnosť tohoto algoritmu sa nazýva kvadratická a označuje sa vzorcom "N²"; znamená to, že napríklad pre tisíc prvkov bude treba urobiť približne milión porovnaní. Keď porovnávame susedné prvky, urobíme približne tisíc porovnaní (presnejšie 999, pri 1000 prvkoch). A kým usporiadame všetky prvky, budeme možno musieť takýchto prechodov urobiť tisíc, a to je spolu tisíckrát tisíc, čiže milión porovnaní. (Aj keby sme nezaokrúhľovali, a počítali by sme, že pri prvom prechode urobíme 999 porovnaní, a pri ďalšom už len 998, keďže podľa horeuvedenej úvahy je po prvom prechode už najväčší prvok na svojom mieste, takže ten viac porovnávať netreba... aj tak by to bolo 999 + 998 + ... + 1 = 499500 porovnaní. A to je približne milión. Takéto veľkorysé zaokrúhľovanie je pri výpočtoch zložitosti typické.)

Najrýchlejšie algoritmy na zoraďovanie majú zložitosť logaritmickú, vyjadrenú vzorcom "N×log(N)". To znamená, že pre tisíc prvkov bude treba urobiť približne tritisíc porovnaní. (Číslo tritisíc vyjde, keď z počtu 1000 robíme desiatkový logaritmus; pri dvojkovom by vyšlo zhruba desaťtisíc, a pri prirodzenom logaritme zhruba sedemtisíc. V rámci nášho veľkorysého zaokrúhľovania považujeme tieto čísla za približne rovnaké. Rozsah tohoto článku mi neumožňuje vysvetliť to lepšie. Berte to skrátka tak, že aj tritisíc aj desaťtisíc je stále omnoho menej ako milión alebo pol milióna. A pri väčšom počte prvkov by rozdiely boli ešte väčšie.)

Túto vysokú rýchlosť možno dosiahnuť pomerne jednoducho úpravou nášho algoritmu: namiesto porovnávania susediacich prvkov začneme porovnávaním prvkov vzdialených, a budeme sa takisto snažiť prekladať malé na začiatok a veľké na koniec poľa. Vzdialenosť medzi porovnávanými prvkami budeme postupne zmenšovať až na 1, a záver bude rovnaký ako pri pôvodnom algoritme. (Zmenšovať budeme vždy na 2/3 predchádzajúcej vzdialenosti. Namiesto vzorca "x×2/3" však použijeme "(x×2+1)/3", aby nám program zaokrúhľujúc nadol klesol iba na jednotku, nie na nuli. Namiesto znamienka "/" použijeme "div", lebo chceme ako výsledok delenia dostať celé číslo, nie desatinné.)

const MAX_PRVKOV = 100;

var
  prvky : Array[1..MAX_PRVKOV] of Integer;
  pocet : Integer;

procedure nacitaj_prvky;
...viď vyššie...

procedure zapis_prvky;
...viď vyššie...

var
  vzdialenost : Integer;
  i : Integer;
  pomocne : Integer;
  koniec : Boolean;

begin
  nacitaj_prvky;
  vzdialenost := pocet;
  repeat
    vzdialenost := (2 * vzdialenost + 1) div 3;
    koniec := (vzdialenost = 1);
    for i := 1 to pocet - vzdialenost do begin
      if prvky[i] > prvky[i + vzdialenost] then begin
        pomocne := prvky[i];
        prvky[i] := prvky[i + vzdialenost];
        prvky[i + vzdialenost] := pomocne;
        koniec := false
      end
    end
  until koniec;
  zapis_prvky;
  WriteLn('Hotovo, bolo to rychle ako blesk.')
end

Existujú aj iné algoritmy na usporiadanie poľa podľa veľkosti (často sa spomína rekurzívny "quicksort"), ale tie už v porovnaní s týmto zrýchleným algoritmom omnoho rýchlejšie byť nemôžu.

Komentáre: 2