Kuplalajittelu
Kuplalajittelu (engl. bubble sort) on erittäin hidas (O(n2)) lajittelualgoritmi, jolla ei ole etuja nopeampiin algoritmeihin edes muistinkäytön suhteen. Se toimii seuraavasti:
- Käydään jono läpi vertaillen kutakin jonon peräkkäistä kahta alkiota toisiinsa. Jos ne ovat väärässä järjestyksessä, vaihdetaan ne keskenään.
- Mikäli vaihtoja tehtiin, toistetaan ensimmäinen vaihe.
Kuplalajittelu on hyvin alkeellinen ja siksi mainitaan useissa yhteyksissä sekä käytetään opetuksessa. Toisena etuna mainitaan, että se johtaa keskusteluun ongelmakohdista.[1]
Esimerkkejä
[muokkaa | muokkaa wikitekstiä]Esimerkki Python-kielellä:
def bubblesort(a): """bubblesort(a) -> list Järjestää taulukon a järjestykseen pienimmästä suurimpaan. """ # Tähän muuttujaan tallennetaan tieto siitä, onko vaihtoja tehty changes = True # Toistetaan niin kauan, kuin vaihtoja tulee while changes: changes = False # Iteroidaan järjestettävän taulukon yli for i in xrange(1, len(a)): # Tarkistetaan alkioiden järjestys if a[i] < a[i - 1]: # Alkiot ovat väärin päin, joten vaihdetaan ne keskenään a[i], a[i - 1] = a[i - 1], a[i] # Vaihto on tapahtunut, joten iterointi on toistettava changes = True # Se, että olemme päässeet tähän kohtaan koodia, tarkoittaa että # taulukko on järjestyksessä; palautetaan se siis kutsujalle return a Esimerkki C-kielellä:
void bubblesort(void *tab, int ts, int vs, int (*cmp)(void *a, void *b)) { int i; int j; char *ctab; if (tab != NULL && ts > 1 && vs > 0) { i = 1; ctab = (char *)tab; while (i > 0) { i = 0; j = 0; while (++j < ts) { if ((*cmp)(ctab + vs * (j - 1), ctab + vs * j) > 0) { swap(ctab + vs * (j - 1), ctab + vs * j, vs); i = 1; } } } } } void swap(void *a, void *b, int vs) { char c; int i; if (a != b) { i = -1; while (++i < vs) { c = *((char *)a + i); *((char *)a + i) = *((char *)b + i); *((char *)b + i) = c; } } } Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Owen Astrachan: Bubble Sort: An Archaeological Algorithmic Analysis users.cs.duke.edu. Viitattu 5.5.2024. (englanniksi)
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]
Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Kuplalajittelu.