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 

Luokka:Lajittelualgoritmit

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