Jako přípravu ke zkoušce z kurzu Algoritmy jsem v Ruby implementoval čtyři řadící algoritmy. Ruby jsem pro selectsort, insertsort, heapsort a quicksort zvolil, protože se v něm potřebuju trochu procvičit a taky mi to přišlo docela zajímavé. Ke každému algoritmu se sluší napsat, jaké má vlastnosti, takže článek je spíše studijní než v praxi použitelný.

Všechny algoritmy jsou psány pro řazení pole čísel typu integer, které je definováno jako globální. Při své implementaci jsem používal pole definované takto:

$A = [2, 5, 7, 9, 1, 3, 4, 6, 8, 0, 1]

Selectsort

Selectsort je algoritmus pracující na principu výběru. Sestává ze dvou cyklů. První cyklus prochází vždy jen neseřazenou část pole. Jinak řečeno začíná nad celým polem o velikosti N, ale každý nový i-tý průchod, kde i = 1..N, prochází vždy o jednu položku méně, tedy vždy N - i položek. Druhý vnořený cyklus hledá ve stále se zmenšující neseřazené části nejmenší hodnotu. Po dokončení druhého cyklu se nejmenší hodnota vymění s i-tou hodnotou cyklu prvního.

Složitost: kvadratická, O(N²)
Stabilita: nestabilní
Přirozenost: nepřirozená

Výhody: snadná implementace
Nevýhody: nízká rychlost

def selectSort
   $A.each_index do |i|
      min = i
      # hledání minima možno nahradit $A.min
      for x in i...$A.length
         min = x if $A[min] > $A[x]
      end
      $A[i], $A[min] = $A[min], $A[i]
   end
end

Insertsort

Insertsort je metoda jednoduchá metoda, která vkládá jednotlivé prvky přímo na své místo. Pole je rozděleno na dvě části - seřazenou část a neseřazenou část - tak, že na začátku je seřazená část tvořena jedním (prvním) prvkem. Algoritmus vyjme první prvek v neseřazené části, takže se jeho místo uvolní. Pokud je vyjmutý prvek větší než největší seřazený prvek, vrátí jej zpět. V opačném případě se největší seřazený prvek posune na uvolněné místo, čímž vznikne volný prostor na jeho původní pozici a vyjmutý prvek se může stejným způsobem porovnat s jeho menším následovníkem. Je-li vyjmutý prvek nejmenší, dojde takto až na začátek pole.

Složitost: kvadratická, O(N²)
Stabilita: stabilní
Přirozenost: přirozená

Výhody: snadná implementace, v nejlepším případě je jeho složitost lineární
Nevýhody: obecně pomalejší algoritmus

def insertSort
   for i in 1...$A.length
      value = $A[i] # hodnota prvního neseřazeného prvku
      j = i - 1 # index největšího seřazeného prvku
      while $A[j] > value and j >= 0
         $A[j + 1] = $A[j] # posun na volné místo
         j += 1
      end
      $A[j + 1] = value # insert
   end
   $A
end

Heapsort

Řazení hromadou je velmi elegantní a pokročilý řadící algoritmus. Pole je nejdříve přeměněno na stromovou strukturu zvanou hromada (halda), která má tu vlastnost, že její vrchol (první prvek) je největší ze všech prvků. Výměnou vrcholu hromady s posledním prvkem pole hromadu sice porušíme, ale efektivně tak řadíme od konce největší prvky, dokud nemá zmenšující se hromada velikost jednoho prvku, nejmenšího v poli. Porušenou hromadu musíme vždy opravit ("zatřepat s ní"), což je provedeno funkcí sift.

Složitost: lineárně logaritmická, O(N * log₂N)
Stabilita: nestabilní
Přirozenost: nepřirozená

Výhody: vždy lineárně logaritmická složitost
Nevýhody: nestabilní

def sift(root, length)
   i = root # kořen
   j = 2 * i # levý syn
   value = $A[i] # hodnota kořene
   while j <= length
      if j <  length # uzel má oba syny
         # výběr většího syna
         j += 1 if $A[j] < $A[j + 1]
      end
      if $A[j] < value
         break # kořen je větší, hotovo
      else
         $A[i] = $A[j] # syn stoupá výš
         i = j # syn se stává příštím otcem
         j = 2 * i
      end
   end
   $A[i] = value # uložení původního uzlu
end
 
def heapSort
   $A.insert(0,0) # vyplnění nultého prvku kvůli indexům
   last = $A.length - 1
   (last / 2).downto 1 do |l| # vytvoření hromady
      sift(l, last)
   end
   last.downto 2 do |l| # řazení hromadou
      $A[1], $A[l] = $A[l], $A[1] # vyjmutí největšího
      sift(1, l - 1)
   end
   $A.shift # smazání nultého prvku
   $A
end

Quicksort

Obecně nejrychlejší řadící metoda, která je založena na principu rozdělení. Pole je rozděleno na dvě části prvkem zvaným pivot a poté jsou prvky uspořádány tak, že nalevo od něj jsou prvky menší (než tento pivot) a napravo prvky větší. Tyto části jsou znovu rekurzivně děleny a řazeny na stále menší, až dokud je co dělit. Poté je pole seřazeno. Rychlost algoritmu je ovlivněna nalezením vhodného pivotu, což může být provedeno hned několika způsoby. Pivot se často hledá pomocí pseudomediánu tak, jak to původně vymyslel C. A. R. Hoare, vynálezce quicksortu. Quicksort jde implementovat rekurzivně(zde uvedeno) i nerekurzivně(nutno použít explicitní zásobník).

Složitost: obecně lineárně logaritmická, O(N * log₂N)
Stabilita: nestabilní
Přirozenost: nepřirozená

Výhody: na náhodných datech a při dobré volbě pivota nejrychlejší
Nevýhody: v nejhorším případě má kvadratickou složitost O(N * log₂N), nestabilní

# wrapper pro počátek rekurze
def quickSort
   qsort(0, $A.length - 1)
   $A
end
 
def qsort(left, right)
   i = left
   j = right
   pseudomedian = $A[(i+j) / 2]
   # hledání pivotu podle C.A.R.Hoare
   until i > j
      while $A[i] < pseudomedian
         i += 1
      end
      while $A[j] > pseudomedian
         j -= 1
      end
      if i <= j
         $A[i], $A[j] = $A[j], $A[i]
         i += 1
         j -= 1
      end
   end
   # zanoření do obou intervalů
   qsort(left, j)  if left < j
   qsort(i, right) if i < right
end

Víte, jak napsat tyto algoritmy, aby byly více "rubínové"? Dejte mi, prosím, vědět v komentáři.