Vaihtolajittelu

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

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 

Lajittelualgoritmit

ar:ترتيب إنتقائي
hy:Selection sort