Archive | Sorting RSS feed for this section

Selection sort

16 Apr

Selection sort, nebo též Selectsort je velmi jednoduchý algoritmus pro třídění dat. Jeho nejlepší časová složitost je n2. Průměrná časová složitost je taktéž n2 a shodou okolností je nejhorší časová složitost též n2. Což je prostě  a jednoduše pomalé. Výhodou tohoto sortu je jeho jednoduchá aplikace. A u nízkého počtu dat nemusí pomalost algoritmu tolik vadit.  Pro větší množství dat jsou vhodnější náročnější sorty s časovou složitostí n log n jako kupříkladu merge sort.

Princip selection sortu je prostý. Představme si že máme náhodně seřazená data. Nejprve najdeme prvek s nejmenší hodnotou, dle které chceme řadit, v posloupnosti. Poté ho zaměníme s prvkem na první pozici. Tento krok se opakuje n-1 krát (kde n je počet prvků). Z principu je ihned vidět jeho velká časová složitost, avšak i jednoduchost sestavení algoritmu v libovolném jazyce.

 Princip selection sortu

Advertisements

Merge sort

24 Nov

Merge sort je primitivní řadící algoritmus fungují na následujícím principu:

  1. Rozdělit seznam čísel na dvě poloviny
  2. Opakovat krok 1 dokud nemám více jak dva elementy
  3. Seřadit je a poté oba podlisty smíchat

V praxi to znamená, že rekurzivně smíchávám dvojce seznamů, dokud nemám seřazeno.
Následující pomalá gif animace to výborně a polopaticky vysvětluje:

Merge sort má efektivnost O(n log n). Merge sort je, díky svému principu, velmi efektivní například na smíchání dvou seznamů čísel, které už seřazené jsou, nebo i přidávání neseřazeného seznamu k seřazenému. Může také výborně fungovat paraelně, jednotlivé poloviny se dají řadit nezávisle na sobě.

Implementace Merge sortu v pseudokódu:

function merge_sort(seznam):
  if len(seznam)<=1 return seznam
  leva = merge_sort(seznam[:len(seznam)//2])
  prava = merge_sort(seznam[len(seznam)//2:])
  vysledek = smichat(leva, prava)
  return vysledek

Funkce smichat může mít více implementací.


Zdroj obrázku: http://bamsoftware.com/hacks/sorts/ (podívejte se tam)

Radix sort

24 Nov

Radix sort, přezdíván „grupovací sort“, je jeden z těch lepších algoritmů na řazení čísel, třídí celá i desetinná čísla:

Radix sort nejprve upraví všechna čísla k setřídění tak, aby měla stejný počet číslic (před kratší než nejdelší a za desetinnou čárku přidá příhodný počet nul).

Potě přímým výběrem rozřadí čísla podle jejich posledních cifer do skupin 0-9 (frontou). z těchto čísel udělá novou řadu v pořadí 0 až9 agrupuje předposlední číslice. Ve chvíli, kdy dorazí na konec, výsledná řada (fronta 0, fronta 1, …) je výsledkem.

DEMNOSTRACE RADIXU, KTEROU BOHUŽEL NEVIDÍTE!

Pro zábavnější demonstraci je tu video plné Japonců s úchylnou japonskou hudbou:

Obrázek ukraden z http://chuck.ferzle.com/Notes/Notes/Sorting/RadixSort.pdf

Třídící algoritmy: Bubble sort

19 Nov

Bubble sort, neboli bublinkové řazení je nejjednodušší z řady třídících algoritmů. V praxi se již nepoužívá, pouze pro výukové účely.

Proč je bubble sort, nepoužívaný? Je totiž zbytečně zdlouhavý, používá metodu, kdy porovnává dvě hodnoty vedle sebe, pokud jsou ve špatném pořadí tak je prohodí. Z tohoto důvodu je bubble sort zbytečně zdlouhavý a i na principu porovnávání dvou buněk se dá vymyslet něco jednoduššího.

Princip bubble sortu se nejlépe znázorní na tomto obrázku:

Bubble sort je zbytečný při třídění velkých listů, prakticky čím větší je počet buněk tím bubble sort déle třídí a je méně a méně efektivní.

Shell sort

14 Nov

Shell sort funguje na principu Insert sortu, je ovšem výkonnější. Nevýhodou Shell sortu je, že nezachovává pořadí položek s rovnými hodnotami.

Na rozdíl od Insert sortu neporovnává nejprve sousední prvky, ale porovnává prvky s určitým odstupem (např. první, šestý, jedenáctý, šestnáctý prvek). Tento odstup se postupně snižuje, dokud neklesne na jedničku (poslední iterace porovnává všechny prvky, jako klasický insert sort).

Hledání ideálního odstupu

Otázkou je, jak najít na začátek nejvýkonnější vzdálenost mezi prvky.

Nejpoužívanější sekvencí je dnes Ciuraova (2001), která vychází z empirické analýzy Martina Ciury: 1, 4, 10, 23, 57, 132, 301, 701 a 1750. Sekvence nemá algoritmickou definici.

V pseudokódu

# řazení arraye a[0…n-1]
mezery = [1750, 701, 301, 132, 57, 23, 10, 4, 1]

foreach (mezera in mezery)
# insertion sort pro každou mezeru
for (i = mezera; i < n; i += 1)
temp = a[i]
for (j = i; j >= mezera and a[j – mezera] > a[i]; j -= mezera)
a[j] = a[j – mezera]
a[j] = temp

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;
  }

}

 

Bucket sort

13 Nov

Bucket sort, nebo také bin sort, je řadící algoritmus, který funguje na základě přihrádkovému řazení. Jednotlivé přihrádky jsou poté seřazeny za použití různých algoritmů.

Postup:

  1. Získá řadu čísel.
  2. Rozdělí daná čísla do jednotlivých přihrádek.
  3. Seřadí všechny využité přihrádky.

Postupně jde po přihrádkách a všechny elementy dá do původní řady.

Pseudokód:

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]
__________________________________________________________________
array = řada, která má být seřazena
n = počet přihrádek k použití
funkce msbits(x,k) = vrátí k nejvýznamnější články x (floor(x/2^(size(x)-k)))