Kuplalajittelu

Kuplalajittelu väreillä

Kuplalajittelu (engl. bubble sort) on erittäin hidas (O(n²)) lajittelualgoritmi, jolla ei ole etuja nopeampiin algoritmeihin edes muistinkäytön suhteen. Se toimii seuraavasti:

1. 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.
2. 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