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[muokkaa | muokkaa wikitekstiä]

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ä[muokkaa | muokkaa wikitekstiä]

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