#include "pch.h"
#include <iostream>
#include <cstdlib>
#include "time.h"

const int arrSize = 1000;
int arr[arrSize];
//int arr[arrSize] = { 5, 3, 7, 10, 8, 9 };

using namespace std;

int deli(int dno, int vrh);
void izpisi();
void hitroUredi(int dno, int vrh);
void generiranje();

int main()
{
	clock_t start, finish;
	double duration;

	srand(time(NULL));
	generiranje();

	//izpisi();

	start = clock();
	hitroUredi(0, arrSize - 1);
	finish = clock();

	duration = (double)(finish - start);
	cout << "Dolzina: " << duration << endl;
	//izpisi();
	cout << "Konec";

}

void generiranje() {
	for (int i = 0; i < arrSize; i++) {
		arr[i] = (rand() % 500);
	}
}

void hitroUredi(int dno, int vrh) {
	if (dno < vrh) {
		int j = deli(dno, vrh);
		hitroUredi(dno, j - 1);
		hitroUredi(j + 1, vrh);
	}
}

int deli(int dno, int vrh) {

	int m = (dno + vrh) / 2;

	int tmpB = arr[dno];
	arr[dno] = arr[m];
	arr[m] = tmpB;

	int pe = arr[dno];
	int levi = dno + 1;
	int desni = vrh;

	while (true) {

		while (arr[levi] < pe && levi <= vrh) { levi++; }
		while (arr[desni] > pe && desni >= dno) { desni--; };

		if (desni <= levi) break;
		else {
			int tmp = arr[levi];
			arr[levi] = arr[desni];
			arr[desni] = tmp;
		}
	}

	int tmpA = arr[dno];
	arr[dno] = arr[desni];
	arr[desni] = tmpA;

	return desni;
}

void izpisi() {
	for (int i = 0; i < arrSize; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}