// Hitro_Uredi.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include <cstdlib>
#include <ctime>
#include <time.h>
using namespace std;

int a[1000000], dolzinaZaporedja;

void generirajNakljucno();
void generirajNarascajoce();
void generirajPadajoce();
void izpisZaporedja();
int DELI(int dno, int vrh);
void HITRO_UREDI(int dno, int vrh);
void PREVERI(int dno, int vrh);
int _tmain(int argc, _TCHAR* argv[])
{
	int meni = 0;
        clock_t start, finish;
    double duration;


        while(meni != 6){
        cout << endl << "Hitro uredi - izbira:" << endl << endl;
        cout << "1 Generiraj naključno zaporedje" << endl;
        cout << "2 Generiraj urejeno naraščajoče zaporedje" << endl;
        cout << "3 Generiraj urejeno padajoče zaporedje" << endl;
        cout << "4 Izpis zaporedja" << endl;
        cout << "5 Uredi" << endl;
        cout << "6 Konec" << endl << endl;
        cout << "Vaša izbira: ";

        cin >> meni;

        if(meni > 0 && meni < 4){
                cout << endl << "Vpisi dolzino zaporedja: ";
                cin >> dolzinaZaporedja;
        }

        if(meni == 1)
        generirajNakljucno();

        else if(meni == 2)
        generirajNarascajoce();

        else if(meni == 3)
        generirajPadajoce();

        else if(meni == 4)
        izpisZaporedja();

        else if(meni == 5){
                int dno = 0, vrh = dolzinaZaporedja - 1;
                start = clock();
                HITRO_UREDI(dno, vrh);
                finish = clock();
                PREVERI( dno,  vrh);
                duration = (double)(finish - start);
                cout << endl << "Cas urejanja: "<< duration << " sec" << endl;
        }

        }
	return 0;
}

int DELI(int dno, int vrh){
int l = dno, d = vrh,  m = (dno+vrh)/2, temp;
temp = a [dno];
a[dno] = a[m];
a[m] = temp;
while(l < d)
{
	while(a[l] <= a[dno] && l < vrh)
	{
		l++;
    }
	while(a[d] >= a[dno] && d > dno)
	{
		d--;
	}
	if(l < d)
	{
		temp = a[l];
		a[l] = a[d];
        a[d] = temp;
	}
}
temp = a[dno];
a[dno] = a[d];
a[d] = temp;
return d;
}
void PREVERI(int dno, int vrh)
{
	for(int i=dno;i<vrh-1;i++)
	{
		if(a[i+1] < a[i])
		{
			cout<<"Napacno zaporedje: "<<a[i+1]<<" "<<a[i];
		}
	}
}
void HITRO_UREDI(int dno, int vrh)
{
	int j;
	if(dno<vrh)
	{
		j=DELI(dno,vrh);
		HITRO_UREDI(dno,j-1);
		HITRO_UREDI(j+1,vrh);
	}
}
void izpisZaporedja()
{
	cout<<endl<<"Zaporedje: ";
	for(int i=0;i<dolzinaZaporedja;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
void generirajNakljucno()
{
	srand((unsigned)time(0));
	int random_integer;
	for(int i = 0; i <= dolzinaZaporedja; i++)
	{
		random_integer = rand() % 10;
		a[i] = random_integer;
	}
}
void generirajNarascajoce()
{
	for(int i = 0; i < dolzinaZaporedja; i++)
	{
		a[i] = i;
	}
}
void generirajPadajoce()
{
	int x = dolzinaZaporedja - 1;
	for(int i = 0; i < dolzinaZaporedja; i++)
	{
		a[i] = x;
        x--;
	}
}