Test 1 (cv 5.)

Zadanie piatok 11:00

1. Načítaj dodaný dataset s položkami. (1 bod)

2. Použi triediaci algoritmus, ktorý má v priemernom prípade zložitosť O(n log n) a v najhoršom prípade zložitosť O(n2) na roztriedenie datasetu z Úlohy 1. (3 body)

3. Vypíš počet potrebných porovnaní na štandardný výstup. (2 body)

4. Vypíš medián datasetu na štandardný výstup. (2 body, v prípade nesprávne vypočítaného mediánu bude za Úlohy 3 a 4 udelených 0 bodov)

5. Triediaci algoritmus z Úlohy 2 má priemernú zložitosť c n log n. Vypočítaj c a vypíš na štadardný výstup. (2 body)

Vysledky

Podla udania zlozitosti sa trebalo rozhodnut pre Quick sort. (alebo iny algoritmus, ktory ma preukazatelnu narocnost popisanu v zadani)

Pocet prvkov : 50001
Median : 10431965
Pocet vymen: 184546
Pocet porovnani: 15235709

    float vypocetKonstanty(int lenght, int cmp)
    {
        float log2n = log10((float)lenght) / log10(2.0f);
        float c = cmp / (lenght * log2n);

        return c;
    }

Riesenie

Ukazkove riesenie - Zapocet1-quicksort.cpp

Dataset- Dataset_5001a.dat

Zadanie piatok 7:00

1. Načítaj dodaný dataset s položkami. (1 bod)

2. Použi stabilný triediaci algoritmus so zložitosťou O(n log n) na roztriedenie datasetu z Úlohy 1. (3 body)

3. Vypíš počet potrebných porovnaní na štandardný výstup. (2 body)

4. Vypíš medián datasetu na štandardný výstup. (2 body, v prípade nesprávne vypočítaného mediánu bude za Úlohy 3 a 4 udelených 0 bodov)

5. Triediaci algoritmus z Úlohy 2 má zložitosť c n log n. Vypočítaj c a vypíš na štadardný výstup. (2 body)

Vysledky

Podla udania zlozitosti sa trebalo rozhodnut pre Merge sort. (alebo iny algoritmus, ktory ma preukazatelnu narocnost popisanu v zadani)

Pocet prvkov : 50001
Median : 10099011
Pocet porovnani: 2476362

    float vypocetKonstanty(int lenght, int cmp)
    {
        float log2n = log10((float)lenght) / log10(2.0f);
        float c = cmp / (lenght * log2n);

        return c;
    }

Riesenie

Ukazkove riesenie - Zapocet1-mergesort.cpp

Dataset - Dataset_5001b.dat