Vaihtolajittelu
Siirry navigaatioon
Siirry hakuun
Vaihtolajittelu (engl. exchange sort, ei kuitenkaan sama kuin bubble sort) on tietojenkäsittelytieteessä tehoton, mutta yksinkertainen lajittelualgoritmi. Sen asymptoottinen suoritusaika on O(n2).
Sisällysluettelo
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ä]
- 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)
