Bubble-sort ensimmäisenä algoritmina

Johdanto

Minua ihmetyttää suuresti, miksi on niin yleisesti levinnyt tapa opettaa bubble-sort ensimmäisenä järjestämisalgoritmina ohjelmoinnin kursseilla.

Yleensä perusteluna sanotaan, että bubble-sort on kaikista yksinkertaisin ja helpommin ymmärrettävä järjestämisalgoritmi. Tämä ei kuitenkaan pidä alkuunkaan paikkansa.

Bubble-sort käyttää sinänsä jännää kikkaa, mutta sen ymmärtäminen, miksi se todella toimii voi olla hankalaa, erityisesti sellaiselle ihmiselle jolla ei ole kokemusta algoritmisesta ajattelusta tai ohjelmoinnista.

Insertion-sort sen sijaan on erittäin intuitiivinen ja helppo ymmärtää. Insertion-sort on myös huomattavasti lähempänä sitä, miten ihminen luonnostaan järjestää alkioita oikeassa elämässä kuin bubble-sort. Bubble-sort on hyvin keinotekoinen järjestämisalgoritmi oikeaa fyysistä tilannetta ajatellen.

Ja mikä tärkeintä, insertion sort ei ole ainoastaan intuitiivisempi ja helpompi ymmärtää, se on myös bubble-sortia huomattavasti tehokkaampi O(n²)-algoritmi. Insertion sort on erittäin tehokas pienillä alkiomäärillä ja siksi soveltuu erittäin hyvin esimerkiksi quick-sortin optimointiin, kun taas bubble-sort ei sovellu oikeastaan mihinkään.

Määritelmät

Jotta saadaan hieman kuvaa siitä, kuinka paljon helpompi insertion-sort on ymmärtää kuin bubble-sort, yritän mahdollisimman yksinkertaisesti kuvata kummankin algoritmin:

Kummassakin tapauksessa tehtävänä on järjestää jono alkioita suuruusjärjestykseen:

Insertion-sort:: Siirrä jonon toinen alkio kohti jonon alkua kunnes se on oikealla paikallaan. Tee sama jonon kolmannelle alkiolle, sitten neljännelle jne. kunnes olet tehnyt sen jonon viimeiselle alkiolle. Alkion siirtäminen kohti jonon alkua tapahtuu siirtämällä välissä olevia alkioita pykälän verran loppua kohti.
Bubble-sort:: Käy jono läpi alusta loppuun niin, että vertaat jokaista peräkkäistä alkioparia ja vaihda niiden paikkoja mikäli ensimmäinen on suurempi kuin toinen (ts. vertaa ensin 1. ja 2. alkiota ja vaihda tarvittaessa, sitten vertaa 2. ja 3. alkiota ja vaihda tarvittaessa, sitten 3. ja 4. alkiota jne. kunnes olet vertaillut toiseksi viimeistä ja viimeistä alkiota). Tee sama uudestaan kaikille alkioille paitsi viimeiselle, jonka jälkeen tee se uudestaan kaikille paitsi kahdelle viimeiselle jne. kunnes jäljelle jää vain kahden ensimmäisen alkion läpikäynti, jonka jälkeen algoritmi on valmis.

Bubble-sort ei ole ainoastaan huomattavasti vaikeampi selittää, se on myös huomattavasti vaikeampi ymmärtää. On myös vaikeampi ymmärtää se, miksi se toimii oikein. (On sinänsä jännä efekti, että ensimmäisen läpikäynnin jälkeen jonon viimeisenä alkiona on suurin alkio, mutta sen hoksaaminen ja sen ymmärtäminen miksi näin on, voi tuottaa vaikeuksia kokemattomalle.) Insertion-sortin ymmärtäminen ei pitäisi tuottaa kenellekään vaikeuksia.

Nopeus

Yksi insertion-sortin hyvistä puolista on se, että se on hyvin nopea mikäli alkiot ovat jo valmiiksi tietyssä osittaisessa järjestyksessä. Näin käy esimerkiksi silloin kun sillä halutaan optimoida quick-sortia. Se tapahtuu seuraavasti:

Quick-sort perustuu siihen, että järjestettävä jono partitioidaan kahteen osaan niin, että partitiointikohdan vasemmalla puolella olevat alkiot ovat kaikki pienempiä kuin sen oikealla puolella. Algoritmi toteutetaan sen jälkeen rekursiivisesti kummallekin puolelle.

Quick-sort on hieman tehoton silloin kun nämä partitiot ovat kovin pieniä (esimerkiksi 10 alkiota tai vähemmän). Tätä ongelmaa voi optimoida siten, että jos järjestettävä partitio on pienempi kuin tietty määrä (esimerkiksi vaikka 10 alkiota), niin sitä ei järjestetäkään enää. Kun jono on tällä tavalla "järjestetty", se koostuu korkeintaan 10 alkion pätkistä, joiden sisällä alkiot ovat kyllä sekajärjestyksessä, mutta pätkät ovat keskenään järjestyksessä (ts. seuraavassa pätkässä olevat alkiot ovat kaikki suurempia kuin sitä edeltävässä).

Tälläinen asettelu on hyvin optimaalinen insertion-sortille sen takia, että algoritmin "alkuunpäin siirtäminen" on aina hyvin lyhyt operaatio (korkeintaan 10 alkion verran taaksepäin siirtämistä). Quick-sortia voikin siis tehostaa merkittävästi lopettamalla partitiointi noin 10-15 alkion kokoisiin lohkoihin ja järjestämällä sen jälkeen koko jono käyttämällä insertion-sortia (järjestäminen nopeutuu tällä tavalla tyypillisesti noin 20-40% verrattuna puhtaaseen quick-sortiin).

Bubble-sort sen sijaan ei soveltuisi tähän alkuunkaan koska se käy jonoa läpi kerta toisensa jälkeen alusta loppuun, sillä se ei pysty mitenkään käyttämään yllä kuvattua osittaista järjestystä hyväksi.

Yksinkertainen esimerkki joka kuvastaa insertion- ja bubble-sortin eroa on ajatella jonoa, joka on muuten täysin järjestyksessä, mutta pienin alkio sijaitsee jonon viimeisenä. Jos taulukossa on vaikkapa 1000 alkiota, bubble-sort tekee noin puoli miljoonaa vertailua, kun taas insertion-sort tekee noin 2000 vertailua (koska se yksinkertaisesti käy taulukon läpi kerran alusta loppuun ja lopusta alkuun).

Käytännön esimerkki opetuksen haitallisuudesta

Bubble sortin opettaminen "perusjärjestämisalgoritmina" on oikeasti haitallista. Tässä esimerkki todellisesta tapauksesta: gnu-flex-ohjelmassa on seuraavanlainen koodinpätkä:

/* We sort the states in sns so we
 * can compare it to oldsns quickly.
 * We use bubble because there probably
 * aren't very many states.
 */
bubble (sns, numstates);

Ei ole mitään järjellistä syytä, miksi tässä on käytetty bubble sorttia insertion sortin sijasta. Bubble sort voi olla ainoastaan hitaampi, eikä se ole yhtään sen helpompi toteuttaa.

Tämä on elävä esimerkki siitä, kuinka bubble sortin opettaminen jonkinnäköisenä varteenotettavana vaihtoehtona laskee ihan käytännössä koodin laatua.

(Takaisin)