Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený.
Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely či v nenáročných aplikacích.
Algoritmus pracuje lokálně (nevyžaduje pomocnou paměť), je stabilní (prvkům se stejným klíčem nemění vzájemnou polohu) a patří mezi přirozené řadicí algoritmy (částečně seřazený seznam zpracuje rychleji než neseřazený).
Časová složitost je n2.
Selectsort
Algoritmus nejprve vyhledá mezi daty prvek s nejmenší hodnotou. Tento prvek zamění s prvkem na první pozici.
Na první pozici se nyní nachází správný prvek, zbytek dat se uspořádá opakováním těchto kroků pro zbylých n-1 prvků, dokud je n > 1.
Časová složitost je n2.
Insertsort
Algoritmus rozdělí množinu prvků na setříděnou část (1 prvek) a nesetříděnou část (zbytek). Z nesetříděné části pak zařazuje prvky do setříděné tak, aby zůstala setříděná.
Algoritmus postupuje následovně:
První prvek ponechá na místě.
Vezme druhý prvek a porovná ho s prvním. Je-li menší, zařadíme ho na první místo a první prvek posuneme, jinak je ponecháme na místě.
Vezmeme třetí prvek a porovnáme jej s prvními dvěma prvky. Je-li menší než některý z nich, zařadíme jej na odpovídající pozici a následující prvky podle potřeby posuneme. Jinak je ponecháme na původních místech.
Obdobně postupujeme i s ostatními prvky.
Časová složitost je n2.
Quicksort
Princip algoritmu:
Zvolme v zadaném poli prvek a říkejme mu pivot. Nyní můžeme pole přeházet tak, aby na jedné straně byly prvky menší než pivot, na druhé větší než pivot a pivot samotný byl umístěn přesně mezi těmito částmi.
Tento postup můžeme zopakovat pro obě rozdělené části (bez pivota, ten je již umístěn na správném místě).
Proceduru opakujeme tak dlouho, dokud nedojde k seřazení pole (nenarazíme na podproblémy jednotkové velikosti, které jsou vyřešeny triviálně).
Časová složitost je průměrně n log2 2 v nejhorším případě však až n2.
Heapsort
Vlastnosti haldy: každý potomek je v haldě menší než jeho otec. (V minimální haldě naopak větší.)
Princip spočívá v opakovaném odebírání vrcholu haldy a jejímu následnému znovuvytvoření.
Z pole vytvoříme haldu.
Odtrhneme vrchol (největší či nejnižší prvek dle způsobu řazení).
Vrchol prohodíme s posledním prvkem haldy a haldu zmenšíme o 1.
Opravíme haldu, aby znovu splňovala požadované vlastnosti.
Tyto kroky opakujeme, dokud má halda prvky.
Časová složitost je n log2 2, je ovšem o něco pomalejší než Quicksort.
