Mitä harvinaisempia tai erikoisempia lajittelualgoritmeja on olemassa? Tiedän ainakin (laitan englanninkieliset nimet) patience sorting ja bead sorting (toiselta nimeltä muuten gravity sort). Patience sorting toimii tavallaan samalla periaatteella kuin perinteinen Klondike-pasianssi ja bead sort esitetään usein helmitauluna.
Ja hyvin lyhyesti selitettynä patience sorting perustuu siihen, että mahdollisimman vähän korttipinoilla muodostaa tilanne, mutta mikäli uusi kortti ei sovi edellisiin (ei siis täytä ehtoja) on muodostettava uusi korttipino. Tämän jälkeen, kun korttipinot on muodostettu, tapahtuu yhdistämisosio (eli merge), siihen en ole vielä tarkemmin perehtynyt miten se toimii (täytyy ottaa selvää).
Ja syy miksi toisen lajittelualgoritmin nimi on gravity sort, johtuu "helmien" putoamisesta alaspäin (visuaalisesti tämä on helpoiten hahmoteltavissa kuten myös patience sorting).
Ja on toki bogo sorting jos sitä edes voi lajitteluksi kutsua. Tavallisesti kursseilla ja vastaavilla käsitellään yleisempiä algoritmeja esimerkkeinä (nyt laitan myös vakiintuneet suomenkieliset nimet) lomituslajittelu (merge sort), pikalajittelu (quick sort), kantalukulajittelu (radix sort), laskentalajittelu (counting sort) ynnä muita.
Kokonaislukujen järjestäminen on mielenkiintoinen erikoistapaus ja kantalukulajittelun lisäksi on muitakin siihen kehitettyjä algoritmeja. Luennot 7 ja 8 täällä käsittelevät aihetta: https://courses.csail.mit.edu/6.851/spring21/
Prioriteettijonoja on todella paljon erilaisia ja niitä voi käyttää järjestämiseen. Luin ihan muutama päivä sitten optimoidusta QuickHeap-toteutuksesta: https://arxiv.org/abs/2604.25681. Heapsort ei kuitenkaan taida olla kovin suosittu käytännössä.
Quicksortin variaatio introsort oli ainakin joitain vuosia sitten useamman standardikirjaston käyttämä algoritmi. Timsort ja jotkut sen variaatiot ovat kuulemma nopeita, mutta en ole koskaan perehtynyt niihin.
Laskentalajittelu on ehkä tärkein algoritmi tietää, koska se on joissain tapauksissa ylivoimaisesti paras ratkaisu. Sitä lukuunottamatta harvoin tarvitsee välittää, mikä algoritmi kirjastossa on taustalla, vaikka ovathan nämä mielenkiintoisia.