Algoritmy usporadúvania

Shell sort

Implementácia

void int_shell_vzostup(int *pole_int, int dlzka)
{
	int porovnania = 0;
	int presuny = 0;

	int krok = dlzka;
	int ptr;		//ptr = aktualna pozicia
	int ptr_zac;		//prt_zac = pociatocna aktualna pozicia
	int i;			//i = prehladavana pozicia
	int pom_ptr;		//pomocny index
	int vkladany;	//vkladany prvok
	int poc_skup;	//pocet skupin
	
	//aspon raz vykonaj
	do{
		//zmensenie kroku o polovicu
		krok = krok/2;
		poc_skup = krok;
		ptr_zac = 0;

		while(poc_skup > 0){	//pre vsetky skupiny
			poc_skup--;
			ptr = ptr_zac;

			//pre kazdu skupinu
			//pokial je aktualna pozicia(=ptr)+krok mensia ako zadana dlzka pola
			while(ptr+krok < dlzka){	
				ptr = ptr+krok;
				//vyber vkladaneho prvku z aktualnej pozicie(=ptr)
				presuny++;
				vkladany = pole_int[ptr];		//insert sort
				//hladanie pozicie vkladaneho prvku v dosial usporiadanej casti skupiny, 
				//tj. od zaciatku skupiny po aktualnu poziciu(=ptr) v skupine
				for(i = ptr_zac; i < ptr; ){
					porovnania++;
					//pre zostupne usporiadanie bude 
					//nasledujuca podmienka: if( vkladany > pole_int[i] )
					if( vkladany < pole_int[i] ){
						//vloz ho tam
						pom_ptr = ptr;
						//presun prvkov( budu v usporiadanej skupine za vkladanym)
						while(pom_ptr > i){
							presuny++;
							pole_int[pom_ptr] = pole_int[pom_ptr-krok];
							pom_ptr = pom_ptr-krok;
						}
						//vlozenie vkladaneho prvku na jeho miesto
						//i == ptr
						presuny++;
						pole_int[i] = vkladany;
						break;
					}
					//prehladavana pozicia sa zvacsi o krok, 
					//tzn. dalsi prvok danej skupiny
					i = i+krok;
				}
				//if(i == ptr) netreba vkladany vkladat, pretoze je 
				//vacsi nez vsetky prvky v usporiadanej casti skupiny
			}
			//zaciatocna aktualna pozicia(=ptr_zac) = dalsi prvok pola, 
			//tj. prvy prvok dalsej skupiny
			ptr_zac++;
		}
	// opakuj tento cyklus pokial nie je krok=1, vtedy je zadane pole usporiadane
	} while(krok != 1);

	//vypis konecnych hodnot porovnani a presunov
	printf("Pocet porovnani: %d\n", porovnania);
	printf("Pocet presunov: %d\n", presuny);

	return;
}