Algoritmy usporadúvania

Insert sort

Implementácia
Nasleduje funkcia v jazyku C, ktorá implementuje algoritmus Insert sort. Uvedená funkcia vstupné pole celých čísel usporiada vzostupne.

//******INSERT SORT*******
//vstup: pole celych cisel urcene na usporiadanie, dlzka zadaneho pola
//ucel: vzostupne usporiadanie zadaneho pola
//algoritmus: Insert sort
//vystup: (void) 
void int_insert_vzostup(int *pole_int, int dlzka)
{
	int presuny = 0;
	int porovnania = 0;

	int ptr = 1;		//ptr = aktualna pozicia
		             //druhy prvok postupnosti
	int vkladany;	//vkladany prvok
	int pom_ptr;		//pomocny index
	int i;			//i = prehladavana pozicia
	
	//pokial je aktualna pozicia(=ptr) mensia ako zadana dlzka pola
	while(ptr < dlzka){
		//vyber vkladaneho prvku (z aktualnej pozicie=ptr)
		presuny++;
		vkladany = pole_int[ptr];

		//hladanie pozicie vkladaneho prvku v dosial usporiadanej casti pola, 
		//tj. od zaciatku pola po aktualnu poziciu(=ptr)
		for(i = 0; i < ptr; i++){
			porovnania++;
			//pre zostupne usporiadanie bude podmienka: 
			//if( vkladany > pole_int[i] )
			if( vkladany < pole_int[i] ){
				//vloz ho tam
				//presun prvkov, ktore budu v usporiadanom poli za vkladanym
				pom_ptr = ptr;
				while(pom_ptr > i){
					presuny++;
					pole_int[pom_ptr] = pole_int[pom_ptr-1];
					pom_ptr--;
				}
				//vlozenie vkladaneho prvku na jeho miesto
				//i == ptr
				pole_int[i] = vkladany;
				presuny++;
				break;
			}
		}
		//if(i == ptr) netreba vkladany prvok vkladat, 
		//pretoze je vacsi nez vsetky prvky v usporiadanej casti pola 
		//aktualna pozicia(=ptr) = dalsi prvok pola
		ptr++;
	}
	
	//vypis konecnych hodnot porovnani a presunov
	printf("Pocet porovnani: %d\n", porovnania);
	printf("Pocet presunov: %d\n", presuny);

	return;
}