#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

#define POCETCISEL 20
#define MINCISLO 1
#define MAXCISLO 100
#define MISTNACISLO 3

int *VytvorPole(int pocetCisel) {
	int i;
	int *pole;
	pole=(int*) malloc(pocetCisel * sizeof(int));
	for (i=0; i<pocetCisel; i++) {
		pole[i]= rand() % (MAXCISLO - MINCISLO +1) + MINCISLO;
	}
	return pole;
}

void VypisPole(int *pole, int pocet) {
	int i;
	printf("\n");
	for (i=0; i<pocet; i++, pole++) {
		printf("%*d", MISTNACISLO, *pole);
	}
}

void BubbleSort(int *pole, int pocet) {
	int i;
	int pom;
	for (/*nic*/;pocet>1; pocet--) {
		for (i=1; i<pocet;i++) {
			if (pole[i]<pole[i-1]) {
				pom=pole[i];
				pole[i]=pole[i-1];
				pole[i-1]=pom;
			}
		}
	}
}

void QuickSort(int *pole, int pocet) {
	int pivot, pom;
	int ixPivot, ixL, ixP; // indexy
	if (pocet <=1) return;
	// vyberu pivot
	ixPivot=pocet/2;
	pivot=pole[ixPivot];
	// prohodim ho s prvkem na pozici 0
	pole[ixPivot]=pole[0];
	pole[0]=pivot;
	// rozhazim pole (na levou stranu <=pivot, na pravou > pivot)
	ixL=1; // na 0 mam pivota
	ixP=pocet-1; // index posledniho prvku
	while (ixL<ixP) { // dokud se indexy nepotkaji
		while (ixL<ixP && pole[ixL]<=pivot) ixL++; // najdu index prvku nepatriciho nalevo
		while (ixL<ixP && pole[ixP]>pivot) ixP--; // najdu index prvku nepatriciho napravo
		// prohodim prvky, ktere nepatri na prislusne strany
		pom=pole[ixL];
		pole[ixL]=pole[ixP];
		pole[ixP]=pom;
	}
	// ted se jen postaram, aby prvek, na kterem se indexy potkaly mohl jit k prave casti
	// ted plati, ze: ixL == ixP
	if (pole[ixL]<pivot) {
		pole[0]=pole[ixL];
		pole[ixL]=pivot;
	}
	QuickSort(pole, ixL);	// na levou cast
	QuickSort(pole+ixL, pocet-ixL);	// na pravou cast (je vcetne prvku, na kterem se potkaly indexy
}

// v pripade volani MergeSort s parametrem pocet <=1 se nealokuje nove pole, ale vraci se puvodni
// v pripade volani MergeSort s parametrem pocet >1 se vrati nove naalokovane setridene pole
int *MergeSort(int *pole, int pocet) {
	int *nove, *leve, *prave;
	int pocetL, pocetP, indexL, indexP, index;
	if (pocet <=1) return pole;
	pocetL=pocet/2;
	pocetP=pocet-pocetL;
	leve=MergeSort(pole, pocetL); // na levou polovinu
	prave=MergeSort(pole+pocetL, pocetP); // na pravou polovinu
	// sloucim dve setrizene posloupnosti leve a prave do jedne nove
	nove=(int*) malloc(pocet*sizeof(int));
	indexL=0; indexP=0; index=0;
	while (index < pocet) {
		while (indexL<pocetL && (leve[indexL]<=prave[indexP] || indexP>=pocetP)) {
			// vkladam prvky z leve, dokud jsou mensi ci rovny aktualnimu prvku z prave,
			// pripadne vlozim vsechny prvky z leve, pokud v prave uz nic neni
			nove[index++]=leve[indexL++];
		}
		while (indexP<pocetP && (prave[indexP]<=leve[indexL] || indexL>=pocetL)) {
			// vkladam prvky z prave, dokud jsou mensi ci rovny aktualnimu prvku z leve,
			// pripadne vlozim vsechny prvky z prave, pokud v leve uz nic neni
			nove[index++]=prave[indexP++];
		}
	}
	if (pocetL>1) free(leve); // leve jsem alokoval pouze tehdy, kdyz pocetL > 1
	if (pocetP>1) free(prave); // prave jsem alokoval pouze tehdy, kdyz pocetP > 1
	return nove;
}

int *VytvorKopii(int *pole, int pocet) {
	int *kopie;
	int i;
	kopie=(int*) malloc(pocet * sizeof(int));
	for (i=0; i<pocet; i++) {
		kopie[i]=pole[i];
	}
	return kopie;
}

int main() {
	int *original;
	int *kopie;
	int pocet;
	srand( (unsigned)time( NULL ) ); // randomize();
	pocet=POCETCISEL;
	original=VytvorPole(pocet);
	printf("\nOriginal:");
	VypisPole(original, pocet);
	// bubblesort
	kopie=VytvorKopii(original, pocet);
	BubbleSort(kopie, pocet);
	printf("\nBubbleSort:");
	VypisPole(kopie, pocet);
	free(kopie);
	// quicksort
	kopie=VytvorKopii(original, pocet);
	QuickSort(kopie, pocet);
	printf("\nQuickSort:");
	VypisPole(kopie, pocet);
	free(kopie);
	// mergesort
	kopie=MergeSort(original, pocet);
	printf("\nMergeSort:");
	VypisPole(kopie, pocet);
	if (pocet>1) free(kopie);
	free(original);
	printf("\n... stiskni klavesu ...");
	getche();
	return 0;
}