AISP - LV5

//LV 5

//1. zadatak

#include <iostream>
using namespace std;
const int N = 7;
int NH = 0;
int V[N] = { 12, 5, 4, 10, 7, 8, 11 };
int zamjena = 0;

int lijevi(int i)
{
    int lj = 2 * i + 1;
    if (lj > NH - 1 || i < 0)
        return -1;
    return lj;
}

int desni(int i)
{
    int ds = 2 * i + 2;
    if (ds > NH - 1 || i < 0)
        return -1;
    return ds;
}

void zamjeni(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
    zamjena++;
    cout << "Niz nakon " << zamjena << ". zamjene: ";
    for (int i = 0; i < N; i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}

void uhrpi(int i)
{
    int najveci = i;
    int lj = lijevi(i);
    int ds = desni(i);

    if (lj > -1)
    {
        if (V[lj] > V[i])
            najveci = lj;
    }

    if (ds > -1)
    {
        if (V[ds] > V[najveci])
            najveci = ds;
    }

    if (najveci != i)
    {
        zamjeni(V[i], V[najveci]);
        uhrpi(najveci);
    }
}

void napraviHrpu()
{
    cout << "Napravi hrpu" << endl;
    NH = N;
    for (int i = NH / 2; i >= 0; i--)
    {
        uhrpi(i);
    }
    cout << "Napravljena hrpu" << endl;
}

void heapsort()
{
    napraviHrpu();
    int zadnji = NH - 1;
    for (int i = zadnji; i >= 1; i--)
    {
        zamjeni(V[0], V[i]);
        NH = NH - 1;
        uhrpi(0);
    }
}

int main(void)
{
    heapsort();
    return 0;
}

//2. zadatak

/* #include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void max_heap(int *V, int i, int n)
{
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int najveci;
    if (l <= n - 1 && V[l] > V[i])
        najveci = l;
    else
        najveci = i;
    if (r <= n - 1 && V[r] > V[najveci])
        najveci = r;
    if (najveci != i)
    {
        int tmp = V[najveci];
        V[najveci] = V[i];
        V[i] = tmp;
        max_heap(V, najveci, n);
    }
}

void hrpa(int *V, int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; i--)
        max_heap(V, i, n);
}

void heap_sort(int *V, int n)
{
    int i;
    hrpa(V, n);
    for (i = n - 1; i > 0; i--)
    {
        int tmp = V[i];
        V[i] = V[0];
        V[0] = tmp;
        n--;
        max_heap(V, 0, n);
    }
}

void bubble_sort(int *V, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int flag = 0;
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (V[j] > V[j + 1])
            {
                int temp;
                temp = V[j];
                V[j] = V[j + 1];
                V[j + 1] = temp;
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}

void merge(int *V, 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 (V[il] < V[id])
            {
                T[i] = V[il];
                il = il + 1;
            }
            else
            {
                T[i] = V[id];
                id = id + 1;
            }
        }
        else
        {
            if (il > s)
            {
                T[i] = V[id];
                id = id + 1;
            }
            else
            {
                T[i] = V[il];
                il = il + 1;
            }
        }
    }
    for (int i = dg; i <= gg; i++)
    {
        V[i] = T[i - dg];
    }

    free(T);
}

void merge_sort(int *V, int dg, int gg)
{
    if (dg == gg)
        return;
    int s = (dg + gg) / 2;
    merge_sort(V, dg, s);
    merge_sort(V, s + 1, gg);
    merge(V, dg, gg);
}

int main(void)
{
    const int N = 10000;
    time_t t1, t2;
    int *V = new int [N];

    srand(time(NULL));

    cout << "N = " << N << endl;

    for (int i = 0; i < N; i++)
    {
        V[i] = rand() % 100;
    }

    t1 = clock();
    bubble_sort(V, N);
    t2 = clock();
    printf("Vrijeme bubblesort-a je %dms\n", t2 - t1);

    for (int i = 0; i < N; i++)
    {
        V[i] = rand() % 100;
    }

    t1 = clock();
    heap_sort(V, N);
    t2 = clock();
    printf("Vrijeme heapsort-a je %dms\n", t2 - t1);

    for (int i = 0; i < N; i++)
    {
        V[i] = rand() % 100;
    }

    t1 = clock();
    merge_sort(V, 0, N-1);
    t2 = clock();
    printf("Vrijeme mergesort-a je %dms\n", t2 - t1);

    free(V);

    return 0;
} */