Lisäyslajittelu

Mureakuha

Lisäyslajittelu (Insertion Sort) on hidas lajittelualgoritmi, kun verrataan nopeisiin lajittelualgoritmeihin kuten QuickSort.

Sen asymptoottinen suoritusaika on O(n²). Käytännössä lajitteluaika on huomattavasti tätä pienempi ja algoritmi on hyvin nopea melkein järjestyksessä olevalle datalle.

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 C-kielinen toteutus:

#include <stdio.h>
 
void lisaa(int *taulukko, int num, int x)
{
	int i;
 
	for (i = num-1; i >= 0; i--)
	{		
		if (x < taulukko[i]) 
			taulukko[i+1] = taulukko[i];
		else 
			break;
	}
	taulukko[i+1] = x;
}
 
void lisays_lajittelu(int *taulukko, int n)
{
	int i;
	int a;
 
	for (i=0; i<n; i++)
	{
		for(a=0; a<n; a++)
			printf("%d ", taulukko[a]);
		printf("\n");
			
    		lisaa(taulukko, i, taulukko[i]);
	}  
}
 
int main(void)
{
	int numerot[] = { 6, 3, 0, 4, 1, 7, 5, 9, 8, 2 };
	int i;
	
	lisays_lajittelu(numerot, sizeof(numerot)/sizeof(int));
	for(i=0; i<10; i++)
		printf("%d ", numerot[i]);
	return 0;
}
 
Esimerkkiohjelman tulostus:
 
6 3 0 4 1 7 5 9 8 2
6 3 0 4 1 7 5 9 8 2
3 6 0 4 1 7 5 9 8 2
0 3 6 4 1 7 5 9 8 2
0 3 4 6 1 7 5 9 8 2
0 1 3 4 6 7 5 9 8 2
0 1 3 4 6 7 5 9 8 2
0 1 3 4 5 6 7 9 8 2
0 1 3 4 5 6 7 9 8 2
0 1 3 4 5 6 7 8 9 2
0 1 2 3 4 5 6 7 8 9