Algoritmy usporadúvania

Merge sort

Implementácia

void int_merge_vzostup(int *pole, int dlzka)
{
	//ak je dlzka rozna od 1, je potrebne zadane pole usporiadat
	if(dlzka > 1){ 
		//dve casti povodnej postupnosti
		int *lava;
		int *prava;
		int dlzka_lava, dlzka_prava;

		//rozdelenie zadaneho pola na dve polivice
		dlzka_lava = dlzka/2;
		dlzka_prava = dlzka-dlzka_lava;

		lava = (int *) malloc(dlzka_lava*sizeof(int));
		prava = (int *) malloc(dlzka_prava*sizeof(int));

		for(int i = 0; i < dlzka_lava; i++){
		lava[i] = pole[i];
			prava[i] = pole[i+dlzka_lava];
		}
		//ak v povodnej casti postupnosti este nieco zostalo
		//dame to do pravej postupnosti
		if(dlzka_lava != dlzka_prava){
		//if(i+dlzka_lava < dlzka-1){
			for(i = dlzka_lava; i < dlzka_prava; i++){
				//presuny++;
				prava[i] = pole[i+dlzka_lava];
			}
		}

		//rekurzivne volanie
		rek_volania = rek_volania+2;
		int_merge_vzostup(lava, dlzka_lava);
		int_merge_vzostup(prava, dlzka_prava);
		
		//zlucenie == MERGE
		int i_lava = 0, i_prava = 0;	//aktualne pozicie v zlucovanych poliach
		//pre cele pole, ktore vznika zlucovanim
		//i = aktualna pozicia vo vystupnom poli
		for(i = 0; i < dlzka; i++){
			//ak v lavej zlucovanej casti uz nie su ziadne prvky
			if(i_lava > dlzka_lava-1){
				//skopiruj vsetko z pravej casti do vysledneho pola
				presuny++;
				pole[i] = prava[i_prava];
				i_prava++;
			}else{
				//ak v pravej zlucovanej casti nie su uz ziadne prvky
				if(i_prava > dlzka_prava-1){
					//skopiruj vsetko z lavej casti do vysledneho pola
					presuny++;
					pole[i] = lava[i_lava];
					i_lava++;
				}else{
					//inak treba porovnat prve prvky v lavej a pravej casti
					porovnania++;
					if(lava[i_lava] < prava[i_prava]){
						//presun prvku z lavej casti do vysledneho pola
						presuny++;
						pole[i] = lava[i_lava];
						i_lava++;
					}else {
						//presun prvku z pravej casti do vysledneho pola
						presuny++;
						pole[i] = prava[i_prava];
						i_prava++;
					}
				}
			}
		}
	}

	return;
}