AISP LV5

#pragma region library
#include<iostream>
#include<time.h>
#include<Windows.h>

using namespace std;
#pragma endregion

#pragma region prototipovi funkcija
void dodaj_brojeve_u_polje(int V[], int n);
void ispis_polja(int V[], int n);

void bubble_sort(int V[], int n);

void heap_sort(int V[], int n);
void podesi(int V[], int n);
void heapify(int V[], int n);

void merge_sort(int dg, int gg);
void merge(int dg, int gg);
#pragma endregion

const int MAXN = 100000000;
int polje[MAXN];

int main() {
    time_t t1, t2;
    int ponovno_pokretanje;
    int n;

    do {
        system("cls");

        cout << "Broj elemenata polja [max 100 000 000]: "; cin >> n;

        //Bubble sort
        dodaj_brojeve_u_polje(polje, n);
        cout << "Sortiranje u tijeku... ";
        t1 = clock();
        bubble_sort(polje, n);
        t2 = clock();
        cout << "Bubble sort vrijeme u [ms]: " << t2 - t1 << endl;
        //cout << "Polje sortirano pomocu Bubble sorta: "; ispis_polja(polje, n); cout << endl;

        //Heap sort
        dodaj_brojeve_u_polje(polje, n);
        cout << "Sortiranje u tijeku... ";
        t1 = clock();
        heap_sort(polje, n);
        t2 = clock();
        cout << "Heap sort vrijeme u [ms]: " << t2 - t1 << endl;
        //cout << "Polje sortirano pomocu Heap sorta: "; ispis_polja(polje, n); cout << endl;

        //Merge sort
        dodaj_brojeve_u_polje(polje, n);
        cout << "Sortiranje u tijeku... ";
        t1 = clock();
        merge_sort(0, n-1);
        t2 = clock();
        cout << "Merge sort vrijeme u [ms]: " << t2 - t1 << endl;
        //cout << "Polje sortirano pomocu Merge sorta: "; ispis_polja(polje, n); cout << endl;

        cout << endl;
        cout << "Za ponovno pokretanje programa unesite [1]: "; cin >> ponovno_pokretanje;
    } while (ponovno_pokretanje == 1);
    return 0;
}

#pragma region funkcije za rad sa poljem
void dodaj_brojeve_u_polje(int V[], int n) {
    for (int i = 0; i < n; i++)
        V[i] = n - i;
}
//kraj funkcije

void ispis_polja(int V[], int n) {
    for (int i = 0; i < n; i++)
        cout << V[i] << " ";
}
//kraj funkcije
#pragma endregion

#pragma region funkcija bubble_sort
void bubble_sort(int V[], int n) {
    bool zamjena;
    int temp;

    do {
        zamjena = false;

        for (int i = 1; i <= n - 1; i++) {
            if (V[i-1] > V[i]) {
                temp = V[i-1];
                V[i-1] = V[i];
                V[i] = temp;
                zamjena = true;
            }
        }
    } while (zamjena == true);
}
//kraj funkcije
#pragma endregion

#pragma region funkcija heap_sort
void heap_sort(int V[], int n) {
    int i, t;

    heapify(V, n);

    for (i = n - 1; i > 0; i--) {
        t = V[0];
        V[0] = V[i];
        V[i] = t;
        podesi(V, i);
    }
}
//kraj funkcije

void podesi(int V[], int n) {
    int i, j, broj;
    j = 0;
    broj = V[j];
    i = 2 * j + 1;

    while(i <= n - 1) {
        if (i + 1 <= n - 1) {
            if(V[i] < V[i+1])
                i++;
        }

        if (broj < V[i]) {
            V[j] = V[i];
            j = i;
            i = 2 * j + 1;
        }
        else
            break;
    }

    V[j] = broj;
}
//kraj funkcije

void heapify(int V[], int n) {
    int k, i, j, broj;

    for (k = 1; k < n; k++) {
        broj = V[k];
        i = k;
        j = (i - 1) / 2;

        while ((i > 0) && (broj > V[j])) {
            V[i] = V[j];
            i = j;
            j = (i - 1) / 2;
        }

        V[i] = broj;
    }
}
//kraj funkcije
#pragma endregion

#pragma region funkcija merge_sort
void merge_sort(int dg, int gg) {
    if (dg == gg) return;

    int s = (dg + gg) / 2;
    merge_sort(dg, s);
    merge_sort(s + 1, gg);
    merge(dg, gg);
}
//kraj funkcije

void merge(int dg, int gg) {
    int* T = new int [gg - dg + 1];
    int s = (dg + gg) / 2;
    int il = dg;
    int id = s + 1;

    for (int i = 0; i < gg - dg + 1; i++) {
        if ((il <= s) && (id <= gg)) {
            if (polje[il] < polje[id]) {
                T[i] = polje[il];
                il = il + 1;
            }
            else {
                T[i] = polje[id];
                id = id + 1;
            }
        }
        else {
            if (il > s) {
                T[i] = polje[id];
                id = id + 1;
            }
            else {
                T[i] = polje[il];
                il = il + 1;
            }
        }
    }

    for (int i = dg; i <= gg; i++)
        polje[i] = T[i - dg];

    delete [] T;
}
//kraj funkcije
#pragma endregion