uredi s prameni

/*
 *  PROSTOR ZA GLAVO
 * (ime in priimek avtorja, identifikacijska stevilka, besedilo naloge)
 --- --- --- --- --- --- ---
 * <ime_datoteke>.<koncnica>
 *
 *       Ustvarjeno: <datum>
 *            Avtor: <ime> <priimek>
 *  Identifikacijska stevilka: <IDUM>
 *  Besedilo naloge:
 *  <navodilo>
 */
 //privzete vkljucitve
#include "pch.h"
#include <iostream>
#include <ctime>
#include <string>


// definicija imenskega prostora(/podrocja)
namespace naloga1 {

    // uporabljeni imenski prostori
    using namespace std;

    void sort(int* arr1, int s1, int* arr2, int s2, int *merg, int m) {

        int i = 0, j = 0, k = 0;
        while (i < s1 && j < s2) {
            if (arr1[i] < arr2[j]) {
                merg[k] = arr1[i];
                i++;
                k++;
            }
            else {
                merg[k] = arr2[j];
                j++;
                k++;
            }
        }

        while (i < s1) {
            merg[k] = arr1[i];
            k++;
            i++;
        }
        while (j < s2) {
            merg[k] = arr2[j];
            k++;
            j++;
        }
    }

    // a predstavlja polje (celostevilskih) elementov, ki ga urejamo
    // n pa stevilo elementov polja
    int* urediSPrameni(int* a, int n)
    {
        // TUKAJ VSTAVI SVOJO KODO

        // vasa funkcija naj NE vraca NULL, pac pa
        // polje urejenih vrednosti
        int* pramen = new int[n];
        int* merge = new int[n];
        int pramenCounter = 0;
        int mergeCounter = 0;
        bool firstRun = true;
        int k = 0;
        int velikostPolja = n;
        int* tmpArr = new int[n];

        while (n > 0) {
            pramenCounter = 0;
            int primerjalni = a[0];
            for (int i = 0; i < n; i++) {
                if (primerjalni <= a[i]) {
                    primerjalni = a[i];
                    pramen[pramenCounter] = a[i];
                    pramenCounter++;

                    for (int j = i; j < n; j++) {
                        a[j] = a[j + 1];
                    }
                    i--;

                }
            }
            n -= pramenCounter;

            if (firstRun) {
                for (int i = 0; i < pramenCounter; i++) {
                    merge[mergeCounter] = pramen[i];
                    mergeCounter++;
                }
                firstRun = false;
            }
            else {

                int tmpV = mergeCounter + pramenCounter;
                int *tmp = new int[tmpV];
                sort(merge, mergeCounter, pramen, pramenCounter, tmp, tmpV);
                mergeCounter += pramenCounter;

                for (int i = 0, j = 0; i < mergeCounter && j <tmpV; i++, j++) {
                    merge[i] = tmp[j];
                }

            }

        }
        return merge;
    }



    //el predstavlja element, ki ga iscemo,
    //a predstavlja polje,
    //n pa stevilo elementov polja
    int poisci(int el, int* a, int n)
    {
        //TUKAJ VSTAVI SVOJO KODO
        int najdenIndeks = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] == el) {
                najdenIndeks = i;
            }
        }
        /*vasa funkcija naj NE vraca -2, pac pa
         indeks najdenega elementa (ce ga ne najde,
         naj vrne -1)*/

        if (najdenIndeks == -1) return -1;
        else return najdenIndeks;

    }

    //el predstavlja element, ki ga iscemo,
    //a predstavlja polje,
    //n pa stevilo elementov polja
    int poisciZBisekcijo(int el, int* a, int n)
    {
        //TUKAJ VSTAVI SVOJO KODO

        /*vasa funkcija naj NE vraca -2, pac pa
         index najdenega elementa (ce ga ne najde,
         naj vrne -1)*/

        int l = 0;
        int h = n;

        while (true) {
            int m = (l + h) / 2;

            if (el == a[m]) return m;
            else if (el > a[m]) {
                l = m + 1;
            }
            else {
                h = m - 1;
            }

        }

        return -1;
    }
}

using namespace naloga1;

int main(int argn, char** args)
{
    //zastavica uspesnosti testiranja
    bool uspesno = true;

    //priprava
    //int vhod[] = { 10, 8, 6, 4, 2, 0, -2, -4, -6, -8, -10 };
     int vhod[] = { 5, 3, 4, 7, 9, 8, 1, 10, 6 };
     const int velikost = 9; //sizeof(vhod) / sizeof(int);
     //const int velikost = 11; //sizeof(vhod) / sizeof(int);
    int pricakovan_izhod[] = { -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10 };

    //klic testirane metode
    int* dobljen_izhod = urediSPrameni(vhod, velikost);
    cout << endl;
    //preverjanje, če se kateri element iz dobljen_izhod ne sklada z elementom v pricakovan_izhod
    if (dobljen_izhod != NULL)
    {
        for (int i = 0; i < velikost; i++)
        {
            if (pricakovan_izhod[i] != dobljen_izhod[i])
            {
                cout << "Metoda urediSPrameni() ni vrnila pravilno urejenega polja." << endl;
                uspesno = false;
                break;
            }
        }
    }
    else //ko je dobljen_izhod == NULL
    {
        cout << "Metoda urediSPrameni() ni vrnila polja, pac pa NULL." << endl;
        uspesno = false;
    }

    //cout << poisci(-6, vhod, velikost) << endl;
    cout << poisciZBisekcijo(2, pricakovan_izhod, velikost) << endl;

    // TUKAJ VSTAVI SVOJE PRIMERE
    // npr. ce poisci() in poisciZBisekcijo() res vrneta indeks elementa,
    // ki je skrajno desno v polju (torej zadnje pojavljanje).
    // Če poisci() in poisciZBisekcijo() pri praznem polju res vrne -1.
    // Če urediSPrameni() res naraščajoče uredi polje in če so se pri tem vsi elementi ohranili.
    // Če poisci() in poisciZBisekcijo() vračata pravilni indeks iskanega elementa v polju.
    // Če se poisciZBisekcijo() pri večjem stevilu elementov res hitreje izvede kot poisci().
    // Če poisci() in poisciZBisekcijo() med iskanjem ne spreminja polja.
    // ...

    //po vseh testnih scenarijih
    cout << "Povzetek: Program ";
    if (uspesno)
        cout << "JE ";
    else
        cout << "ni ";
    cout << "uspesno prestal vaša testiranja." << endl;

    //ciscenje spomina
    if (dobljen_izhod != NULL)
        delete[] dobljen_izhod;

    return 0;
}