Vaihtolajittelu

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

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

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ä]

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

Algoritmeista[muokkaa | muokkaa wikitekstiä]

Muita lajittelualgoritmeja[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]