Triediace algoritmy

Čo je triedenie a prečo je dôležité?

Triedenie znamená usporiadanie kolekcie položiek v definovanom poradí — zvyčajne od najmenšej po najväčšiu (vzostupne) alebo od najväčšej po najmenšiu (zostupne). Každý deň počítače triedia obrovské množstvá dát: výsledky vyhľadávania podľa relevantnosti, produkty podľa ceny, správy podľa dátumu, mená abecedne.

Bez triedenia by bolo vyhľadávanie informácií bolestne pomalé. Keby bol telefónny zoznam vytlačený v náhodnom poradí, museli by sme prečítať každý záznam, aby sme našli jedno meno. Zotriedené dáta umožňujú počítačom využívať oveľa efektívnejšie vyhľadávacie techniky. Triedenie patrí k najzákladnejším operáciám v informatike.

Bublinkové triedenie: krok za krokom

Bublinkové triedenie (bubble sort) je jeden z najjednoduchších algoritmov na pochopenie. Princíp spočíva v opakovanom prechode zoznamom, porovnávaní susedných párov prvkov a ich výmene, ak sú v nesprávnom poradí. Po každom úplnom prechode „vybublá" najväčšia nezotriedená hodnota na svoje správne miesto na konci.

Príklad krok za krokom

Začneme s týmto zoznamom piatich čísel:

[5, 3, 8, 1, 4]

Prechod 1:

• Porovnáme 5 a 3 → 5 > 3, vymeníme → [3, 5, 8, 1, 4]
• Porovnáme 5 a 8 → 5 < 8, nevymieňame → [3, 5, 8, 1, 4]
• Porovnáme 8 a 1 → 8 > 1, vymeníme → [3, 5, 1, 8, 4]
• Porovnáme 8 a 4 → 8 > 4, vymeníme → [3, 5, 1, 4, 8]

Po prvom prechode je najväčšia hodnota (8) na svojom konečnom mieste.

Prechod 2:

• Porovnáme 3 a 5 → nevymieňame → [3, 5, 1, 4, 8]
• Porovnáme 5 a 1 → vymeníme → [3, 1, 5, 4, 8]
• Porovnáme 5 a 4 → vymeníme → [3, 1, 4, 5, 8]
• Porovnáme 5 a 8 → nevymieňame

Po druhom prechode sú 5 aj 8 na mieste.

Prechod 3:

• Porovnáme 3 a 1 → vymeníme → [1, 3, 4, 5, 8]
• Porovnáme 3 a 4 → nevymieňame
• Porovnáme 4 a 5 → nevymieňame

Zoznam je teraz úplne zotriedený: [1, 3, 4, 5, 8].

Bublinkové triedenie v pseudokóde

PROCEDURA bublinkoviTriedenie(zoznam):
  n = dlzka zoznamu
  PRE prechod OD 1 DO n - 1:
    PRE i OD 0 DO n - prechod - 1:
      AK zoznam[i] > zoznam[i + 1]:
        vymen zoznam[i] a zoznam[i + 1]
  VRAT zoznam

Každý vonkajší cyklus predstavuje jeden úplný prechod. Každý vnútorný cyklus prechádza nezotriedenenou časťou. Trik n - prechod zabraňuje opätovnej kontrole prvkov, ktoré sú už potvrdenéna správnom mieste na konci.

Triedenie výberom: stručný úvod

Triedenie výberom (selection sort) funguje inak. Namiesto bublania hodnôt hore opakovane vyberá minimum z nezotriedenej časti zoznamu a presúva ho na začiatok.

[5, 3, 8, 1, 4]

• Nájdeme minimum celého zoznamu → 1 → vymeníme s prvým prvkom → [1, 3, 8, 5, 4]
• Nájdeme minimum zo zvyšku [3, 8, 5, 4] → 3 → je už na mieste → [1, 3, 8, 5, 4]
• Minimum z [8, 5, 4] → 4 → vymeníme → [1, 3, 4, 5, 8]
• Minimum z [5, 8] → 5 → je na mieste

Výsledok: [1, 3, 4, 5, 8].

Triedenie výberom robí menej výmen ako bublinkové, ale rovnaký počet porovnaní. Ani jeden algoritmus nie je zvlášť rýchly pre veľké zoznamy.

Prečo záleží na efektívnosti

Bublinkové triedenie aj triedenie výberom sú vhodné pre malé zoznamy. Ale predstav si, čo sa stane, keď má zoznam 1 000 000 položiek. Oba algoritmy porovnajú zhruba n × n prvkov v najhoršom prípade — to je bilión porovnaní pre milión položiek.

Pokročilejšie algoritmy ako merge sort a quicksort dokážu zoradiť milión položiek s iba asi 20 miliónmi porovnaní. To je rozdiel medzi čakaním zlomku sekundy a čakaním hodiny.

Kľúčový poznatok je, že výber správneho algoritmu môže znamenať rozdiel medzi programom, ktorý reaguje okamžite, a programom, ktorý trvá tak dlho, že vyzerá ako zamrznutý.