Lisäyslajittelu
Siirry navigaatioon
Siirry hakuun
Lisäyslajittelu (insertion sort) on hidas (O(n2)) ja vakaa lajittelualgoritmi, joka toimii 'paikallaan' (eli ei vaadi lisämuistia). Lisäyslajittelun asymptoottinen suoritusaika on yhtä suuri kuin kuplalajittelulla, mutta käytännössä sen ajoaika on kuitenkin usein huomattavasti tätä pienempi. Yksinkertaisuutensa vuoksi se onkin usein nopein vaihtoehto lajittelualgoritmiksi hyvin pienillä taulukoilla.
Algoritmi toimii pitämällä taulukon alkuosan koko ajan järjestyksessä lisäämällä yksitellen jokaisen alkion käsittelemättömästä loppuosasta oikealle paikalleen alkuosaan.
Ohessa lisäyslajittelun pseudokielinen toteutus:
algoritmi Lisäyslajittelu(taulukko t) n := taulukon t alkioiden lukumäärä // Käydään taulukon jokainen (paitsi ensimmäinen) alkio läpi for i = 2 to n j := i // Siirretään alkio oikealle paikalleen järjestettyyn alkuosaan while(t[j] < t[j-1] ja j > 1) Vaihda alkioiden t[j] ja t[j-1] arvot keskenään j := j - 1 end while end for
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 insertionsort(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=0, i2=0;
for(i1=1; i1<lkm; i1++)
{
i2=i1;
while(i2>0 && cmp((char *)alkio+i2*koko, (char *)alkio+(i2-1)*koko)>0)
{
swap((char *)alkio+i2*koko, (char *)alkio+(i2-1)*koko, koko);
i2--;
}
}
}
}