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ä

#include <stdio.h>
#include <stdlib.h>

void swap(void *valkio1, void *valkio2, int koko) /* kahden alkion paikkojen vaihtoa varten */
{
  if(koko > 0)
    {
      char *apu;
      if((apu=(char *)malloc(koko))!=NULL)
        {
          int i1=0;
          for(i1=0; i1<koko; i1++)
            *(apu+i1)=*((char *)valkio2+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio2+i1)=*((char *)valkio1+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio1+i1)=*(apu+i1);
          free(apu);
          apu=NULL;
        }
    }
}

void exchangesort(void *alkio, int lkm, int koko, int (*cmp)(void *valkio1, void *valkio2))
{
  if(alkio != NULL && lkm > 1 && koko > 0) /* jonkinlaiset järkevät alkuehdot */
    {
      int i1=lkm-2, i2=0;
      for(i1=0; i1<lkm-1; i1++)
        for(i2=i1+1; i2<lkm; i2++)
          if(cmp((char *)alkio+i1*koko, (char *)alkio+i2*koko) < 0)
            swap((char *)alkio+i1*koko, (char *)alkio+i2*koko, koko);
    }
}

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