Algoritmy usporadúvania

Radix sort

Implementácia
Nasleduje funkcia v jazyku C, ktorá implementuje algoritmus Radix sort. Uvedená funkcia vstupné pole celých čísel usporiada vzostupne.
V implementácii je použitá funkcia int digit(int cislo, int rad), ktorá vráti hodnotu číslice, ktorá sa nachádza v zadanom čísle na zadanom ráde. Implementáciu tejto funkcie nechávam na čitateľovi.

//******RADIX SORT*******
//vstup: pole celych cisel urcene na usporiadanie, dlzka zadaneho pola
//ucel: volanie funkcie pass(...) pre vsetky rady (od najnizsieho po najvyssi rad prvku v poli) //ucinok: vzostupne usporiadanie zadaneho pola
//algoritmus: Radix sort
//vystup: (void) 
void radixSort(int *pole, int dlzka)
{ 
	int rad;
	for(rad=0; rad < najvyssi_rad; rad++)
	      pass(pole, dlzka, rad);
}

//zadane pole danej dlzky usporiada podla daneho radu vzostupne
void pass(int *pole, int dlzka, int rad){
	//pomocne polia
	int counter[10];
	int temp[dlzka];

	//nulovanie
	for(int d = 0; d < 10; d++ ) 
		counter[d] = 0;

	//spocitanie kolko cisel z pola ma na danom rade danu cislicu
	for(int i = 0; i < dlzka; i++ ) 
		counter[ digit(pole[i], rad) ] ++;

	//upravime si pomocne pole pre dlasie pouzitie
	for(d = 1; d < 10; d++ ) 
		counter[d] += counter[d-1];

	//od konca zadaneho pola usporiadavame prvky do pomocneho pola
	for(i = dlzka; i > 0; i-- ){
		temp[ counter[ digit(pole[i], rad) ] -- ] = pole[i];
	}

	//prekopirovanie usporiadaneho do povodneho pola
	for(i = 0; i < dlzka; i++ ) 
		pole[i] = temp[i];
}