Vaihtolajittelu

Vaihtolajittelu (engl. exchange sort, ei kuitenkaan sama kuin bubble sort) on tietojenkäsittelytieteessä tehoton, mutta yksinkertainen lajittelualgoritmi. Sen asymptoottinen suoritusaika on O(n²).

Algoritmi

Vaihtojärjestäminen voidaan ilmaista seuraavasti:

• Verrataan ensimmäistä alkiota yksi kerrallaan kaikkiin sen jälkeen tuleviin alkioihin ja vaihdetaan alkiot, jos ne ovat väärässä järjestyksessä.
• Nyt ensimmäisenä on kaikkein pienin alkio.
• Tehdään sama toiselle alkiolle, kolmannelle alkiolle...
• Kun toiseksi viimeinen on saatu käsiteltyä, koko taulukko on järjestyksessä.

T: taulukko
first: ensimmäinen lajiteltava indeksi
last: viimeinen lajiteltava indeksi

for i := first to last – 1
    for j := i + 1 to last
        if T[i] > T[j]
            vaihda T[i] <–> T[j]

Ulomman silmukan invariantti on:

• T[first] ... T[i] on järjestyksessä
• T[i–1] ≤ T[i] ... T[last], kun i > 0

Sisemmän silmukan invariantti on:

• T[i] ≤ T[i+1] ... T[j–1], kun j > i + 1

Esimerkkitoteutus C-kielellä

void    exchangesort(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 < ts - 1)
                {
                        j = i;
                        while (++j < ts)
                                if ((*cmp)(ctab + i * vs, ctab + j * vs) > 0)
                                        swap(ctab + i * vs, ctab + j * vs, vs);
                }
        }
}

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

Katso myös

Algoritmeista

• Asymptoottinen suoritusaika
• Lajittelualgoritmi

Muita lajittelualgoritmeja

• Kuplalajittelu (perinteinen tehoton mutta helppo lajittelualgoritmi)
• Valintalajittelu (hyvin samanlainen periaate)
• Lisäyslajittelu (yksinkertainen ja todella nopea, jos lajiteltavaa on vähän)
• Pikalajittelu (asymptoottisesti keskimäärin tehokkaampi)
• Lomituslajittelu (pahimmassakin tapauksessa asymptoottisesti tehokkaampi)

Lähteet

• Arto Wikla: Ohjelmoinnin perusteita Java-kielellä: 2.8 Taulukko-olioista
• Opetusmateriaalia, jossa lasketaan vaihtolajittelun asymptoottinen suoritusaika (Arkistoitu – Internet Archive)