Counting Sort

13 Nov

Lze třídit prvky bez nutnosti je mezi sebou porovnávat? Je vůbec možno třídit v lineárním čase? Ano, je to možné a jedním z algoritmů založených na tomto principu je právě Counting Sort!

Algoritmus třídí pouze celá čísla, což nemusí být problém, protože v drtivé většině případů třídíme celá čísla a ve zbytku případů většinou můžeme objekty na celá čísla převést (např. čísla s 2 desetinnými místy pronásobit stem, setřídit a poté znovu vydělit). Třídí na principu pomocného pole, kterému se říká sčítací pole, někdy také indexovací pole. To bude dlouhé tak, jak je dlouhý rozsah prvků v původním poli a budou v něm zatím samé nuly. Původní pole se lineárně projede a prvky v něm jsou brány jako indexy do sčítacího pole. Pro každý prvek si ve sčítacím poli zvýšíme hodnotu (započítáme ho). Potom druhým lineárním průchodem projedeme sčítací pole a podle počtů na jednotlivých indexech do původního pole zleva zapisujeme indexy zpět jako prvky. O časové složitosti až na konci článku, nyní si ukážeme průběh na ukázkovém poli.

Průběh

Máme pole následujících prvků:

Nejprve si musíme zjistit rozsah prvků, potřebujeme tedy nalézt minimum a maximum, oboje zvládneme jednoduchým lineárním průchodem. V našem případě bude minimum 2 a maximum 12.

Nyní si vytvoříme pomocné sčítací pole, které bude mít velikost (maximum – minimum + 1), tedy (12 – 2 + 1) = 11

Sčítací pole (nahoře indexy, dole hodnoty):

Nyní projedeme původní pole a jeho prvky budeme brát jako indexy do pole sčítacího. Začneme tedy prvním prvkem (3), ten snížíme o minimum (2), tedy index je 3-2 = 1. Na tomto indexu zvýšíme hodnotu.

Sčítací pole:

Takto to uděláme i u dalších prvků, výsledné sčítací pole bude vypadat následovně:

Sčítací pole:

Všimněte si, že na indexu 3 je ve sčítacím poli hodnota 2, protože prvek 5 byl v původním poli 2x. Nyní již není nic jednoduššího, než projet sčítací pole od záčátku do konce a obráceným způsobem vrátit prvky do původního pole. Musíme si však v paměti udržovat, na jaké jsme pozici v původním poli, zpočátku tuto proměnnou nastavíme na 0.

Začněme tedy prvním indexem (indexem 0), je na něm počet 1, do původního pole tedy na pozici pozice (0) vložíme prvek index + minimum, tedy 0 + 2 = 2. Počítadlo pozice zvýšíme o jedna (na hodnotu 1).

Sčítací pole:

Na indexu 1 máme jedničku, obdobně tedy do původního pole vložíme prvek 1 + 2 = 3 na pozici pozice (1), kterou opět zvýšíme.

Sčítací pole:

Na indexu 2 máme počet 0, neděláme tedy nic a posuneme se na index 3. Tam máme dvojku, přidáme tedy 2x prvek 3 + 2 = 5 na pozici pozice a pozice + 1. Pozice se nám pochopitelně zvýší o 2.

Sčítací pole:

Analogicky pokračujeme až do konce, kdy bude pole setříděné. Bude tedy vypadat takto:

Sčítací pole zahodíme a máme vyhráno.

Na závěr ještě video pro ilustraci:

Časová složitost

Jistě jste si všimli, že byly třeba 3 průchody pole. Jeden pro nalezení extrémů, další pro vytvoření sčítacího pole a poslední pro vypsání prvků ve správném pořadí. Oba extrémy jistě najdeme v čase O(n), další 2 akce nás však budou stát čas O(n + m), kde m je rozsah pole. Zde se skrývá nástraha Counting sortu – jeho rychlost je přímo závislá na rozsahu prvků v poli.

Představte si, že máme pole, ve kterém jsou jen 2 prvky [1, 1000000] . I ten nejhloupější Bubblesort by ho setřídil okamžitě. Counting sort si vytvoří sčítací pole dlouhé milion prvků a s ním bude poté operovat. To jistě není nejšťastnější případ pro použití Counting sortu.

Stejně tak se nám však může naskytnou případ, kdy přesně víme, jaký rozsah budou prvky mít (tedy víme, co třídíme) a můžeme si být jisti, že se do milionů nedostaneme. V tuto chvíli může být algoritmus velmi zajímavý, pokud dokonce známe minimální a maximální prvek, můžeme si odpustit i první průchod.

Na závěr ještě kód v jazyku C.

public static void counting_sort(int[] list) {

  //nalezeni minima a maxima
  int min = list[0];
  int max = list[0];
  for (int i = 0; i < list.Length; i++) {
    if (list[i] < min)
      min = list[i];
    if (list[i] > max)
      max = list[i];
  }
  int[] carray = new int[max - min + 1]; //vytvoreni scitaciho pole
  for (int i = 0; i < carray.Length; i++)
    carray[i] = 0; //vynulovani
  for (int i = 0; i < list.Length; i++)
    carray[list[i] - min] += 1; //naplneni
  int k = 0; //pozice ve vyslednem poli
  for (int i = min; i <= max; i++)
  for (int j = 1; j <= carray[i - min]; j++) {
    k++;
    list[k] = i;
  }

}

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: