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 voidaan toteuttaa esimerkiksi seuraavalla Python-kielisellä koodilla:

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

Esimerkkitoteutus C-kielellä 

void    bubblesort(void *tab, int ts, int vs, int (*cmp)(void *a, void *b))
{
        register int    i;
        register int    j;
        register 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)
{
        register char           c;
        register int            i;

        if (a != b)
        {
                i = -1;
                while (++i < vs)
                {
                        c = *((char *)a + i);
                        *((char *)a + i) = *((char *)b + i);
                        *((char *)b + i) = c;
                }
        }
}

Aiheesta muualla 

 NIST:in kuvaus kuplalajittelusta
 Kuplalajittelu Pascalilla

Lajittelualgoritmit

no:Sorteringsalgoritme#Boblesortering