Kuplalajittelu

alt=Kuplalajittelu väreillä|pienoiskuva|Kuplalajittelu väreillä pienoiskuva|300px|Kuplalajittelun havainnollistava esitys. Kuplalajittelu () 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.Kampalajittelu (eng. comb sort) on tehostettu versio kuplalajittelussa ja siinä alkioiden välinen väli jaetaan aina 1,3:llla joka kierroksella ja lajittelupäättyy kun alkioiden välinen väli on 1.

Esimerkkejä 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

Aiheesta muualla

NIST:in kuvaus kuplalajittelusta Kuplalajittelu Pascalilla

Luokka:Lajittelualgoritmit

no:Sorteringsalgoritme#Boblesortering