Kuplalajittelu

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 väreillä

Kuplalajittelun havainnollistava esitys.

Kuplalajittelu on hyvin alkeellinen ja siksi mainitaan useissa yhteyksissä sekä käytetään opetuksessa. Toisena etuna mainitaan, että se johtaa keskusteluun ongelmakohdista.

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;
        }
    }
}

Aiheesta muualla

• NIST:in kuvaus kuplalajittelusta
• Kuplalajittelu Pascalilla