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.
Harjoituskysymys (aloittelijalle tai kelle vaan muulle, mutta älkää spoilatko heti): millä aikakompleksisuudella pystyt järjestämään N merkkijonoa, jos niiden yhteenlaskettu pituus on M bittiä?
Provosoiva mielipide 😄
Lajittelualgoritmin itse toteuttaminen on hyvää treeniä - ja ihan hauskaa 🤓 (Itsekin olen joskus vuosikymmeniä sitten 1980-luvulla juhlinut, kun sain pascal-kielellä quicksortin toimimaan… vaikka sain vain numerot riviin.)
Mutta.
Miksi me oikeastaan lajittelemme? 🤔 Lajittelu on väline, ei päämäärä.
Ohjelmoinnissa puhutaan vähän arvoista. Oma ykkönen on luovuus 🎨 Siksi käytän valmiita kirjastoja ja keskityn siihen, mikä on oikeasti uutta.
“Kirjoitin oman sortin” on siistiä.
“Tein jotain merkityksellistä” on siistimpää 🙂
Eli: opettele algoritmit - mutta älä unohda kysyä, miksi.
PetriKeckman kirjoitti:
Ohjelmoinnissa puhutaan vähän arvoista. Oma ykkönen on luovuus 🎨 Siksi käytän valmiita kirjastoja ja keskityn siihen, mikä on oikeasti uutta.
“Kirjoitin oman sortin” on siistiä.
“Tein jotain merkityksellistä” on siistimpää 🙂
Niin tuo on tietysti sinun arvojärjestys ja toisella voi olla erilainen arvojärjestys. En oikein näe mitä provosoivaa sen toteamisessa on.
Onneksi joillekin voi olla intohimona vaikkapa se lajittelualgoritmi, niin sitten sinulle on tarjolla hyviä valmiita välineitä.
jlaire kirjoitti:
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ä.
Tuo vaikuttaa mielenkiintoiselta lähteeltä. Hieman ehdin jo vilkaisemaan sitä, täytyy tutkia tarkemmin. Ja joo Heapsort toki kuuluu itsessään jokaisen koodarin ja tietojenkäsittelijän perussivistykseen. Itse luin ja opiskelin Fibonacci Heap rakennetta, joka on tehokkaampi kuin Binary Heap varsinkin lisäyksen ja yhdistämisen kannalta.