/*
 * Quick Sort Algorithm
 **************************************************************
 * podstawowa wersja rekurencyjna, liczby calkowite
 * [c] piotao, 20051107, c++/c
 *
 * Ten program jest przykladowa implementacja algorytmu quicksort
 * Zadaniem programu jest posortowanie tablicy liczb calkowitych.
 */

/* 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 20

/* 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

/* funkcja zamiany elementow - jej zadaniem jest zamiana miejscami elementow w
 * tablicy; mozna taka funkcje napisac np. tak, zeby pobierala tablice i dwa
 * indeksy jej elementow. Mozna zrobic funkcje, ktora wezmie tylko dwie zmienne
 * i zmodyfikuje je. Tutaj napiszemy ta pierwsza wersje.  Wywolanie:
 * zamien_elementy( TABLICA, indeks1, indeks2 );
 */

void zamien_1( int A[], int i, int j ){
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}

/* gdyby ktos sie uparl na zamiane elementow w formie dwoch przekazanych
 * wskaznikow, funkcja zamieniajaca elementy moglaby wygladac np. tak ja
 * ponizej. Wywolanie: zamien_wartosci( &zmienna1, &zmienna2 );
 * Dla elementow tablicy: zamien_wartosci( &A[i], &A[j] );
 * Wazne: musimy podac operator wyluskania, czy inaczej adresu: &
 */
void zamien_2( int *a, int *b ){
	int c = *a;
	*a = *b;
	*b = c;
}

/* najwazniejsza funkcja w algorytmie quicksort - partition. Jej zadaniem jest
 * przestawianie elementow i podzial sortowanego odcinka tablicy na dwie
 * czesci, wzgledem jakiegos wybranego elementu. Jedna czesc zawiera elementy
 * mniejsze od wybranego, druga czesc zawiera elementy wieksze.
 * Funkcja musi zwracac liczbe calkowita bedaca istniejacym indeksem tablicy.
 */
int partition( int A[], int p, int r){
	int x = A[p];
	int i = p;
	int j = r;
	while(1){
		while(A[j]>x){ j--; }
		while(A[i]<x){ i++; }
		if(i<j){
			zamien_1(A,i,j);                // wersja indeksowa
			//zamien_2(&A[i],&A[j]);        // wersja wskaznikowa
			i++; j--;
		}
		else{
			return j;
		}
	}
}

/* procedura quicksort - glowna procedura wykonujaca sortowanie, korzystajaca
 * oczywiscie z pomocy funkcji partition.  Jest to bardzo prosta funkcja
 * rekurencyjna.
 */
void quicksort( int A[], int p, int r,int l){
	int q;
	if(p < r){
		q = partition(A,p,r);
		printf("level: %i, partition: %i <= %i < %i\n",l,p,q,r);
		quicksort(A,p,q,l+1);
		quicksort(A,q+1,r,l+1);
	}
}

/* aby mozna bylo badac algorytm na rozne sposoby mozemy uzyc funkcji, ktore
 * generuja rozne dane - ponizej jest kilka przykladow
 */

/* funkcja generuje losowe liczby i zapelnia nimi tablice A */
void generuj_losowo( int A[] ){
	int i;
	for(i=0;i<MAX_ARRAY_SIZE;i++){ A[i] = rand(); }
}

/* 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));
	}
}

/* funkcja generuje liczby wstawiane do tablicy w kolejnosci rosnacej */
void generuj_rosnaco( int A[] ){
	int i = 0;
	while(i<MAX_ARRAY_SIZE){ A[i] = i; i = i+1; }
}

/* funkcja generuje liczby wstawiane do tablicy w kolejnosci malejacej */
void generuj_malejaco( int A[] ){
	int i = 0;
	while(i<MAX_ARRAY_SIZE){ A[i] = MAX_ARRAY_SIZE - i-1; i++; }
}

/* funkcja zapelnia tablice jedna, podana wartoscia */
void wypelnij_jednostajnie( int A[], int liczba ){
	int i;
	for(i=0;i<MAX_ARRAY_SIZE;i++){ A[i] = liczba; }
}

/* i jeszcze 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");
}



/* no i program glowny - to musialo tu byc :)    */
int main(){
	int TABLICA[MAX_ARRAY_SIZE];          // tablica moze miec same 0 lub smieci

//	generuj_losowo(TABLICA);              // generowanie losowych liczb w calej tablicy
	generuj_losowo_od_do(TABLICA,0,100);  // zapelniamy liczbami losowo od do
//	generuj_rosnaco( TABLICA );           // generujemy liczby ladnie posortowane juz
//	generuj_malejaco( TABLICA );          // generujemy liczby posortowane odwrotnie
//	wypelnij_jednostajnie( TABLICA, 210); // tablica zostanie zapelniona jedna wartoscia

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

	// uruchamiamy procedure sortowania dla calej tablicy
	// podajemy indeksy krancowych elementow, czyli 0 oraz max-1
	quicksort(TABLICA, 0, MAX_ARRAY_SIZE-1,0);

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

	return 0;
}