/*
 * Counting Sort Algorithm
 **************************************************************
 * podstawowa wersja, liczby calkowite
 * [c] piotao, 20051121, c++/c
 *
 * Ten program to elementarnie prosta implementacja algorytmu counting-sort
 * Zadaniem programu jest posortowanie tablicy MAX_ARRAY_SIZE liczb calkowitych
 * ktore nie przekraczaja wielkosci MAX_DATA_SIZE.
 */

/* dolaczamy do programu bibliteke standardowa obslugi plikow, klawiatury oraz
 * pisania na ekran, tzw. standardowego wejscia-wyjscia (ang. [st]an[d]ard
 * [i]nuput/[o]utput (ta biblioteka potrzebna jest po to, aby dzialala funkcja
 * printf) Jest to tzw. dyrektywa preprocesora, czyli specjalnego programu,
 * ktory przed kompilacja przetworzy nasz zrodlowy program - tak, wlasnie to,
 * co jest w ogole ponizej napisane :)
 */
#include <stdio.h>

/* dolaczamy tez biblioteke obslugujaca funkcje do losowania (potrzebne do
 * losowego zapelniania tablicy) */
#include <stdlib.h>

/* deklarujemy maksymalny rozmiar tablicy (mozemy tu okreslic malo elementow
 * aby wypisac je na ekranie i sprawdzic czy program dziala albo duzo
 * elementow, zeby program pracowal dluzej i wtedy mierzyc jego czas wykonania
 * poleceniem time)
 */

#define MAX_ARRAY_SIZE 10

/* okreslamy maksymalna rozpietosc danych */
#define MAX_DATA_SIZE 100

/* ponizsze definicje okreslaja jak ma sie wyswietlic tablica, czy w pionie,
 * czy w poziomie, a uzyte zostana w procedurze wypisz, ktora jak kazdy student
 * sie domysli, jest do wyswietlania zawartosci tablicy :)
 */

#define PIONOWO 1
#define POZIOMO 0

/* prosta procedurka do wypisania wynikow, jezeli tablica jest mala
 * tutaj mozna podac, czy ma byc pisane w pionie, czy w poziomie (wg. wartosci 1 lub 0) */
void wypisz( int A[], int kierunek ){
	int i=0;
	if(kierunek){
		while(i<MAX_ARRAY_SIZE){ printf("A[%i]=%i\n",i,A[i]); i++; }
	}
	else{
		while(i<MAX_ARRAY_SIZE){ printf("%i ",A[i]); i++; }
	}
	printf("\n");
}

/* funkcja zapelnia tablice losowymi danymi od min, do max */
void generuj_losowo_od_do( int A[], int min, int max){
	int i;
	for(i=0;i<MAX_ARRAY_SIZE;i++){
		A[i] = min + (int)((max-min) * (float)rand()/(RAND_MAX+1.0));
	}
}

/* glowna procedura sortujaca, jest bardzo prosta: zlicza elementy z tablicy
 * podanej, a nastepnie wpisuje je w ich naturalnej kolejnosci do tejze tablicy */
void countingsort(int A[]){
	int T[MAX_DATA_SIZE];
	int i;
	for(i=0;i<MAX_DATA_SIZE;i++) T[i] = 0;           // zerowanie tablicy pomocniczej
	for(i=0;i<MAX_ARRAY_SIZE;i++) T[ A[i] ] += 1;    // zliczanie elementow
	int j,l = 0;
	for(i=0; i<MAX_DATA_SIZE; i++)                   // wstawienie elementow w ich
		for(j=0; j<T[i]; j++){                         // kolejnosci do tablicy wynikowej
			A[l] = i;
			l++;
		}
}

/* program glowny */
int main(){
	int TABLICA[MAX_ARRAY_SIZE];          // tablica moze miec same 0 lub smieci

	generuj_losowo_od_do(TABLICA,0,MAX_DATA_SIZE); // zapelniamy liczbami losowo

//	wypisz(TABLICA, PIONOWO);
	wypisz(TABLICA, POZIOMO);

	// uruchamiamy procedure sortowania dla calej tablicy
	countingsort(TABLICA);

//	wypisz(TABLICA, PIONOWO);
	wypisz(TABLICA, POZIOMO);

	return 0;
}