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