QS

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

const int arrSize = 30;
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();

}

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];

	//cout << "pe: " << pe << endl;
	int levi = dno + 1;
	int desni = vrh;

	while (true) {

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

		// sort asc/desc
		/*while (arr[levi] > pe) levi++;
		while (arr[desni] < pe) desni--;
*/
/*for (; levi < vrh; levi++) {
	if (arr[levi] > pe) {
		leviNajden = levi;
		break;
	}
}
for (; desni >= dno; desni--) {
	if (arr[desni] < pe) {
		desniNajden = desni;
		break;
	}
}
*/
// cout << "LEVI: " << levi  << " DESNI: " << desni << endl;

		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;
}