Algoritmy usporadúvania

Radix sort

Implementácia

void int_radix_vzostup(int *pole, int dlzka)
{
	int i, j;
	//rad, podla ktoreho prave usporaduvame (rozdelujeme prvky do skupin)
	int rad = 1;
	int ptr;		//ptr = aktualna pozicia
	int rad_pom = 0;	
	//rad_pom urcuje pocet prvkov usporaduvanej postupnosti, 
	//ktore su nizsieho radu nez je rad, podla ktoreho sa aktualne radi do skupin
	//ked rad_pom == dlzka koncime

	//najhorsie riesenie
	//(skupiny = polia rovnakej dlzky ako usporaduvane pole, index do kazdeho pola)
	int *nulta_skup;
	nulta_skup = (int*) malloc(dlzka*sizeof(int));
	int nulta;
	int *prva_skup;
	prva_skup = (int*) malloc(dlzka*sizeof(int));
	int prva;
	int *druha_skup;
	druha_skup = (int*) malloc(dlzka*sizeof(int));
	int druha;
	int *tretia_skup;
	tretia_skup = (int*) malloc(dlzka*sizeof(int));
	int tretia;
	int *stvrta_skup;
	stvrta_skup = (int*) malloc(dlzka*sizeof(int));
	int stvrta;
	int *piata_skup;
	piata_skup = (int*) malloc(dlzka*sizeof(int));
	int piata;
	int *siesta_skup;
	siesta_skup = (int*) malloc(dlzka*sizeof(int));
	int siesta;
	int *siedma_skup;
	siedma_skup = (int*) malloc(dlzka*sizeof(int));
	int siedma;
	int *osma_skup;
	osma_skup = (int*) malloc(dlzka*sizeof(int));
	int osma;
	int *deviata_skup;
	deviata_skup = (int*) malloc(dlzka*sizeof(int));
	int deviata;

	//pokial este ostavaju prvy vyssieho radu nez je ten, podla ktoreho radime do skupin
	while(rad_pom < dlzka){
		//atualna pozicia a pozicie v skupinach su na danych prvych prvku
		ptr = 0;
		nulta = 0;
		prva = 0;
		druha = 0;
		tretia = 0;
		stvrta = 0;
		piata = 0;
		siesta = 0;
		siedma = 0;
		osma = 0;
		deviata = 0;
		//pokial je aktualna pozicia(=ptr) mensia ako zadana dlzka pola
		while(ptr < dlzka){
			//do premennej i dame hodnotu vyssich radov
			//(nez aktualny rad) prvku na aktualnej pozicii 
			i = pole[ptr]/(rad*10);
			//ak je i = 0, je aktualny rad najvyssim radom daneho prvku
			if(i == 0){
				rad_pom++;
			}
			//do premennej i dame hodnotu aktualneho radu
			i = ( pole[ptr]%(rad*10) ) / rad;

			//podla hodnoty tohto radu rozhodneme, 
			//do ktorej skupiny prvok na aktualnej pozicii zaradime
			switch(i){
			case 0:
				nulta_skup[nulta] = pole[ptr];
				nulta++;
				break;
			case 1:
				prva_skup[prva] = pole[ptr];
				prva++;
				break;
			case 2:
				druha_skup[druha] = pole[ptr];
				druha++;
				break;
			case 3:
				tretia_skup[tretia] = pole[ptr];
				tretia++;
				break;
			case 4:
				stvrta_skup[stvrta] = pole[ptr];
				stvrta++;
				break;
			case 5:
				piata_skup[piata] = pole[ptr];
				piata++;
				break;
			case 6:
				siesta_skup[siesta] = pole[ptr];
				siesta++;
				break;
			case 7:
				siedma_skup[siedma] = pole[ptr];
				siedma++;
				break;
			case 8:
				osma_skup[osma] = pole[ptr];
				osma++;
				break;
			case 9:
				deviata_skup[deviata] = pole[ptr];
				deviata++;
				break;
			}
			//aktualna pozicia(=ptr) = dalsi prvok pola
			ptr++;
		}
		//spojenie skupin do jedneho pola, zaciname od nultej
		for(j = 0; j < nulta; j++){
			pole[j] = nulta_skup[j];
		}
		int pom = nulta;
		for(j = 0; j < prva; j++){
			pole[j+pom] = prva_skup[j];
		}
		pom += prva;
		for(j = 0; j < druha; j++){
			pole[j+pom] = druha_skup[j];
		}
		pom += druha;
		for(j = 0; j < tretia; j++){
			pole[j+pom] = tretia_skup[j];
		}
		pom += tretia;
		for(j = 0; j < stvrta; j++){
			pole[j+pom] = stvrta_skup[j];
		}
		pom += stvrta;
		for(j = 0; j < piata; j++){
			pole[j+pom] = piata_skup[j];
		}
		pom += piata;
		for(j = 0; j < siesta; j++){
			pole[j+pom] = siesta_skup[j];
		}
		pom += siesta;
		for(j = 0; j < siedma; j++){
			pole[j+pom] = siedma_skup[j];
		}
		pom += siedma;
		for(j = 0; j < osma; j++){
			pole[j+pom] = osma_skup[j];
		}
		pom += osma;
		for(j = 0; j < deviata; j++){
			pole[j+pom] = deviata_skup[j];
		}
		//zvysenie radu
		rad*=10;

	}

	return;
}