daily pastebin goal
30%
SHARE
TWEET

Untitled

a guest Mar 24th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #include <iostream>
  3. #include <cmath>
  4. #include <ctime>
  5. #include <cstdlib>
  6. #include <chrono>
  7. #include <vector>
  8. #include <algorithm>
  9.  
  10. double ln2 = log2(2);
  11. using namespace std;
  12.  
  13. template < class typ >
  14. void quicksort(typ *tab, int left, int right)
  15. {
  16.     typ pivot = tab[(left + right) / 2];
  17.     int i, j;
  18.     typ x;
  19.     i = left;
  20.     j = right;
  21.  
  22.     do
  23.     {
  24.         while (tab[i] < pivot) i++;
  25.         while (tab[j] > pivot) j--;
  26.         if (i <= j)
  27.         {
  28.             x = tab[i];
  29.             tab[i] = tab[j];
  30.             tab[j] = x;
  31.             i++;
  32.             j--;
  33.         }
  34.     } while (i <= j);
  35.     if (j > left) quicksort(tab, left, j);
  36.     if (i < right) quicksort(tab, i, right);
  37. }
  38. template < class typ >
  39. void merge(typ *arr, int l, int m, int r)
  40. {
  41.     int i, j, k;
  42.     int n1 = m - l + 1;
  43.     int n2 = r - m;
  44.  
  45.     /* create temp arrays */
  46.     typ *L=new typ[n1], *R=new typ[n2];
  47.  
  48.     /* Copy data to temp arrays L[] and R[] */
  49.     for (i = 0; i < n1; i++)
  50.         L[i] = arr[l + i];
  51.     for (j = 0; j < n2; j++)
  52.         R[j] = arr[m + 1 + j];
  53.  
  54.     /* Merge the temp arrays back into arr[l..r]*/
  55.     i = 0; // Initial index of first subarray
  56.     j = 0; // Initial index of second subarray
  57.     k = l; // Initial index of merged subarray
  58.     while (i < n1 && j < n2)
  59.     {
  60.         if (L[i] <= R[j])
  61.         {
  62.             arr[k] = L[i];
  63.             i++;
  64.         }
  65.         else
  66.         {
  67.             arr[k] = R[j];
  68.             j++;
  69.         }
  70.         k++;
  71.     }
  72.  
  73.     /* Copy the remaining elements of L[], if there
  74.        are any */
  75.     while (i < n1)
  76.     {
  77.         arr[k] = L[i];
  78.         i++;
  79.         k++;
  80.     }
  81.  
  82.     /* Copy the remaining elements of R[], if there
  83.        are any */
  84.     while (j < n2)
  85.     {
  86.         arr[k] = R[j];
  87.         j++;
  88.         k++;
  89.     }
  90.     delete[] L;
  91.     delete[] R;
  92. }
  93.  
  94. /* l is for left index and r is right index of the
  95.    sub-array of arr to be sorted */
  96. template < class typ >
  97. void mergeSort(typ *arr, int l, int r)
  98. {
  99.     if (l < r)
  100.     {
  101.         // Same as (l+r)/2, but avoids overflow for
  102.         // large l and h
  103.         int m = l + (r - l) / 2;
  104.  
  105.         // Sort first and second halves
  106.         mergeSort(arr, l, m);
  107.         mergeSort(arr, m + 1, r);
  108.  
  109.         merge(arr, l, m, r);
  110.     }
  111. }
  112.  
  113. template <class Item>
  114. void Exchange(Item *Array, long i, long j)
  115. {
  116.     Item temp;
  117.     temp = Array[i];
  118.     Array[i] = Array[j];
  119.     Array[j] = temp;
  120. }
  121. template <class Item>
  122. void MedianOfThree(Item *Array, long &L, long &R)
  123. {
  124.     if (Array[++L - 1] > Array[--R])
  125.         Exchange(Array, L - 1, R);
  126.     if (Array[L - 1] > Array[R / 2])
  127.         Exchange(Array, L - 1, R / 2);
  128.     if (Array[R / 2] > Array[R])
  129.         Exchange(Array, R / 2, R);
  130.     Exchange(Array, R / 2, R - 1);
  131. }
  132. template <class Item>
  133. long Partition(Item *Array, long L, long R)
  134. {
  135.     long i, j;
  136.     if (R >= 3)
  137.         MedianOfThree(Array, L, R);
  138.     for (i = L, j = R - 2; ; )
  139.     {
  140.         for (; Array[i] < Array[R - 1]; ++i);
  141.         for (; j >= L && Array[j] > Array[R - 1]; --j);
  142.         if (i < j)
  143.             Exchange(Array, i++, j--);
  144.         else break;
  145.     }
  146.     Exchange(Array, i, R - 1);
  147.     return i;
  148. }
  149.  
  150.  
  151. template <class Item>
  152. void Heapify(Item *Array, long i, long N)
  153. {
  154.     long j;
  155.     while (i <= N / 2)
  156.     {
  157.         j = 2 * i;
  158.         if (j + 1 <= N && Array[j + 1] > Array[j])
  159.             j = j + 1;
  160.         if (Array[i] < Array[j])
  161.             Exchange(Array, i, j);
  162.         else break;
  163.         i = j;
  164.     }
  165. }
  166. template <class Item>
  167. void Heap_Sort(Item *Array, long N)
  168. {
  169.     long i;
  170.     for (i = N / 2; i > 0; --i)
  171.         Heapify(Array - 1, i, N);
  172.     for (i = N - 1; i > 0; --i)
  173.     {
  174.         Exchange(Array, 0, i);
  175.         Heapify(Array - 1, 1, i);
  176.     }
  177. }
  178. template <class Item>
  179. void Insertion_Sort(Item *Array, long N)
  180. {
  181.     long i, j;
  182.     Item temp;
  183.     for (i = 1; i < N; ++i)
  184.     {
  185.         temp = Array[i];
  186.         for (j = i; j > 0 && temp < Array[j - 1]; --j)
  187.             Array[j] = Array[j - 1];
  188.         Array[j] = temp;
  189.     }
  190. }
  191. template <class Item>
  192. void IntroSort(Item *Array, long N, int M)
  193. {
  194.     long i;
  195.     if (M <= 0)
  196.     {
  197.         Heap_Sort(Array, N);
  198.         return;
  199.     }
  200.     i = Partition(Array, 0, N);
  201.     if (i > 9)
  202.         IntroSort(Array, i, M - 1);
  203.     if (N - 1 - i > 9)
  204.         IntroSort(Array + i + 1, N - 1 - i, M - 1);
  205. }
  206.  
  207. template <class Item>
  208. void Hybrid_Introspective_Sort(Item *Array, long N)
  209. {
  210.     IntroSort(Array, N, (int)floor(2 * log(N) / ln2));
  211.     Insertion_Sort(Array, N);
  212. }
  213.  
  214. template<typename T>
  215. bool checkIfCorrect(std::vector<T> table, const std::vector<T>& result)
  216. {
  217.     std::sort(table.begin(), table.end());
  218.     return (table == result);
  219. }
  220.  
  221. template<typename T, size_t N>
  222. bool checkIfCorrect(const T(&table)[N], const  T(&result)[N])
  223. {
  224.     T sorted[N];
  225.     std::copy(table, table + N, sorted);
  226.     std::sort(std::begin(sorted), std::end(sorted));
  227.  
  228.     return std::equal(std::begin(sorted), std::end(sorted),
  229.         std::begin(result), std::end(result));
  230. }
  231. int main()
  232. {
  233.     srand(time(NULL));
  234.  
  235.     std::vector<int> nVector{ 10000, 50000, 100000,500000, 1000000 };
  236.     const int nbOfExperiments = 10;
  237.     int liczba;
  238.     int *pom;
  239.     int *pom2;
  240.     int *pom3;
  241.     int *tablica;
  242.     int *tablica2;
  243.     int *tablica3;
  244.     int *tablica4;
  245.     int *tablica5;
  246.     int *tablica6;
  247.     int *tablica7;
  248.     int *tablica8;
  249.    
  250.  
  251.     /*Badanie dla każdego rozmiaru tablicy n*/
  252.     for (const auto& n : nVector)
  253.     {
  254.         pom = new int[n];
  255.         pom2 = new int[n];
  256.         pom3 = new int[n];
  257.         tablica = new int[n];
  258.         tablica2 = new int[n];
  259.         tablica3 = new int[n];
  260.         tablica4 = new int[n];
  261.         tablica5 = new int[n];
  262.         tablica6 = new int[n];
  263.         tablica7 = new int[n];
  264.         tablica8 = new int[n];
  265.         cout << "wielkosc:" << n<<endl;
  266.         /*Wykonanie eksperymentu nbOfExperiments razy dla tablic o rozmiarze n*/
  267.         for (int i = 0; i < nbOfExperiments; ++i)
  268.         {
  269.             for (int i = 0; i < n; i++)
  270.             {
  271.                 liczba = rand() % n;
  272.                 tablica[i] = liczba;
  273.             }
  274.            
  275.             for (int i = 0; i < n; i++)
  276.             {
  277.                 if (i > n / 4)
  278.                 {
  279.                     liczba = rand() % n;
  280.                     tablica2[i] = liczba;
  281.                 }
  282.                 else
  283.                     tablica2[i] = i;
  284.             }
  285.            
  286.             for (int i = 0; i < n; i++)
  287.             {
  288.                 if (i > n / 2)
  289.                 {
  290.                     liczba = rand() % n;
  291.                     tablica3[i] = liczba;
  292.                 }
  293.                 else
  294.                     tablica3[i] = i;
  295.             }
  296.            
  297.             for (int i = 0; i < n; i++)
  298.             {
  299.                 if (i > 0.75*n)
  300.                 {
  301.                     liczba = rand() % n;
  302.                     tablica4[i] = liczba;
  303.                 }
  304.                 else
  305.                     tablica4[i] = i;
  306.             }
  307.            
  308.             for (int i = 0; i < n; i++)
  309.             {
  310.                 if (i > 0.95*n)
  311.                 {
  312.                     liczba = rand() % n;
  313.                     tablica5[i] = liczba;
  314.                 }
  315.                 else
  316.                     tablica5[i] = i;
  317.             }
  318.            
  319.             for (int i = 0; i < n; i++)
  320.             {
  321.                 if (i > 0.99*n)
  322.                 {
  323.                     liczba = rand() % n;
  324.                     tablica6[i] = liczba;
  325.                 }
  326.                 else
  327.                     tablica6[i] = i;
  328.             }
  329.            
  330.             for (int i = 0; i < n; i++)
  331.             {
  332.                 if (i > 0.997*n)
  333.                 {
  334.                     liczba = rand() % n;
  335.                     tablica7[i] = liczba;
  336.                 }
  337.                 else
  338.                     tablica7[i] = i;
  339.             }
  340.            
  341.             for (int i = n; i>0; i--)
  342.             {
  343.                 tablica8[i-1] = i;
  344.             }
  345.            
  346.  
  347.  
  348.            
  349.  
  350.             /*
  351.             Przygotowanie tablic o rozmiarze n:
  352.             •wszystkie elementy tablicy losowe,
  353.             • 25%, 50%, 75%, 95%, 99%, 99,7% początkowych elementów tablicy jest już posortowanych,
  354.             • wszystkie elementy tablicy już posortowane ale w odwrotnej kolejności.
  355.             */
  356.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  357.             {
  358.                 pom[i] = tablica[i];
  359.                 pom2[i] = tablica[i];
  360.                 pom3[i] = tablica[i];
  361.             }
  362.  
  363.             /* Mierzenie czasu trwania jednego eksperymentu
  364.             Poniższy fragment wykonywany jest wielokrotnie
  365.             osobno dla każdej kombinacji algorytmu i tablicy wejściowej
  366.             //pojedyncze wykonanie jednego algorytmu sortowania dla jednej tablicy
  367.             //sortowanie na kopii tablic wejściowych
  368.             */
  369.             // **TABLICA 1**
  370.             cout << "tab1" << endl;
  371.             //quick
  372.             auto start = std::chrono::system_clock::now();
  373.             quicksort<int>(pom, 0, n);
  374.             auto end = std::chrono::system_clock::now();
  375.             std::chrono::duration<double> diff = end - start; // w sekundach https://en.cppreference.com/w/cpp/chrono/duration
  376.             double durationTime = diff.count(); // zmierzony czas zapisać do pliku lub zagregować, zapisać liczbę badanych elementów
  377.             cout << "q:" << durationTime << endl;
  378.             //merge
  379.             start = std::chrono::system_clock::now();
  380.             mergeSort<int>(pom2, 0, n);
  381.             end = std::chrono::system_clock::now();
  382.             diff = end - start;
  383.             durationTime = diff.count();
  384.             cout << "m:" << durationTime << endl;
  385.             //intro
  386.             start = std::chrono::system_clock::now();
  387.             Hybrid_Introspective_Sort<int>(pom3, n);
  388.             end = std::chrono::system_clock::now();
  389.             diff = end - start;
  390.             durationTime = diff.count();
  391.             cout << "i:" << durationTime << endl;
  392.             cout << "tab2" << endl;
  393.             // **TABLICA 2**
  394.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  395.             {
  396.                 pom[i] = tablica2[i];
  397.                 pom2[i] = tablica2[i];
  398.                 pom3[i] = tablica2[i];
  399.             }
  400.             //quick
  401.             start = std::chrono::system_clock::now();
  402.             quicksort<int>(pom, 0, n);
  403.             end = std::chrono::system_clock::now();
  404.             diff = end - start;
  405.             durationTime = diff.count();
  406.             cout << "q:" << durationTime << endl;
  407.             //merge
  408.             start = std::chrono::system_clock::now();
  409.             mergeSort<int>(pom2, 0, n);
  410.             end = std::chrono::system_clock::now();
  411.             diff = end - start;
  412.             durationTime = diff.count();
  413.             cout << "m:" << durationTime << endl;
  414.             //intro
  415.             start = std::chrono::system_clock::now();
  416.             Hybrid_Introspective_Sort<int>(pom3, n);
  417.             end = std::chrono::system_clock::now();
  418.             diff = end - start;
  419.             durationTime = diff.count();
  420.             cout << "i:" << durationTime << endl;
  421.             cout << "tab3" << endl;
  422.             // **TABLICA 3**
  423.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  424.             {
  425.                 pom[i] = tablica3[i];
  426.                 pom2[i] = tablica3[i];
  427.                 pom3[i] = tablica3[i];
  428.             }
  429.             //quick
  430.             start = std::chrono::system_clock::now();
  431.             quicksort<int>(pom, 0, n);
  432.             end = std::chrono::system_clock::now();
  433.             diff = end - start;
  434.             durationTime = diff.count();
  435.             cout << "q:" << durationTime << endl;
  436.             //merge
  437.             start = std::chrono::system_clock::now();
  438.             mergeSort<int>(pom2, 0, n);
  439.             end = std::chrono::system_clock::now();
  440.             diff = end - start;
  441.             durationTime = diff.count();
  442.             cout << "m:" << durationTime << endl;
  443.             //intro
  444.             start = std::chrono::system_clock::now();
  445.             Hybrid_Introspective_Sort<int>(pom3, n);
  446.             end = std::chrono::system_clock::now();
  447.             diff = end - start;
  448.             durationTime = diff.count();
  449.             cout << "i:" << durationTime << endl;
  450.             cout << "tab4" << endl;
  451.             // **TABLICA 4**
  452.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  453.             {
  454.                 pom[i] = tablica3[i];
  455.                 pom2[i] = tablica3[i];
  456.                 pom3[i] = tablica3[i];
  457.             }
  458.             //quick
  459.             start = std::chrono::system_clock::now();
  460.             quicksort<int>(pom, 0, n);
  461.             end = std::chrono::system_clock::now();
  462.             diff = end - start;
  463.             durationTime = diff.count();
  464.             cout << "q:" << durationTime << endl;
  465.             //merge
  466.             start = std::chrono::system_clock::now();
  467.             mergeSort<int>(pom2, 0, n);
  468.             end = std::chrono::system_clock::now();
  469.             diff = end - start;
  470.             durationTime = diff.count();
  471.             cout << "m:" << durationTime << endl;
  472.             //intro
  473.             start = std::chrono::system_clock::now();
  474.             Hybrid_Introspective_Sort<int>(pom3, n);
  475.             end = std::chrono::system_clock::now();
  476.             diff = end - start;
  477.             durationTime = diff.count();
  478.             cout << "i:" << durationTime << endl;
  479.             cout << "tab5" << endl;
  480.             // **TABLICA 5**
  481.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  482.             {
  483.                 pom[i] = tablica5[i];
  484.                 pom2[i] = tablica5[i];
  485.                 pom3[i] = tablica5[i];
  486.             }
  487.             //quick
  488.             start = std::chrono::system_clock::now();
  489.             quicksort<int>(pom, 0, n);
  490.             end = std::chrono::system_clock::now();
  491.             diff = end - start;
  492.             durationTime = diff.count();
  493.             cout << "q:" << durationTime << endl;
  494.             //merge
  495.             start = std::chrono::system_clock::now();
  496.             mergeSort<int>(pom2, 0, n);
  497.             end = std::chrono::system_clock::now();
  498.             diff = end - start;
  499.             durationTime = diff.count();
  500.             cout << "m:" << durationTime << endl;
  501.             //intro
  502.             start = std::chrono::system_clock::now();
  503.             Hybrid_Introspective_Sort<int>(pom3, n);
  504.             end = std::chrono::system_clock::now();
  505.             diff = end - start;
  506.             durationTime = diff.count();
  507.             cout << "i:" << durationTime << endl;
  508.             cout << "tab6" << endl;
  509.             // **TABLICA 6**
  510.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  511.             {
  512.                 pom[i] = tablica6[i];
  513.                 pom2[i] = tablica6[i];
  514.                 pom3[i] = tablica6[i];
  515.             }
  516.             //quick
  517.             start = std::chrono::system_clock::now();
  518.             quicksort<int>(pom, 0, n);
  519.             end = std::chrono::system_clock::now();
  520.             diff = end - start;
  521.             durationTime = diff.count();
  522.             cout << "q:" << durationTime << endl;
  523.             //merge
  524.             start = std::chrono::system_clock::now();
  525.             mergeSort<int>(pom2, 0, n);
  526.             end = std::chrono::system_clock::now();
  527.             diff = end - start;
  528.             durationTime = diff.count();
  529.             cout << "m:" << durationTime << endl;
  530.             //intro
  531.             start = std::chrono::system_clock::now();
  532.             Hybrid_Introspective_Sort<int>(pom3, n);
  533.             end = std::chrono::system_clock::now();
  534.             diff = end - start;
  535.             durationTime = diff.count();
  536.             cout << "i:" << durationTime << endl;
  537.             cout << "tab7" << endl;
  538.             // **TABLICA 7**
  539.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  540.             {
  541.                 pom[i] = tablica7[i];
  542.                 pom2[i] = tablica7[i];
  543.                 pom3[i] = tablica7[i];
  544.             }
  545.             //quick
  546.             start = std::chrono::system_clock::now();
  547.             quicksort<int>(pom, 0, n);
  548.             end = std::chrono::system_clock::now();
  549.             diff = end - start;
  550.             durationTime = diff.count();
  551.             cout << "q:" << durationTime << endl;
  552.             //merge
  553.             start = std::chrono::system_clock::now();
  554.             mergeSort<int>(pom2, 0, n);
  555.             end = std::chrono::system_clock::now();
  556.             diff = end - start;
  557.             durationTime = diff.count();
  558.             cout << "m:" << durationTime << endl;
  559.             //intro
  560.             start = std::chrono::system_clock::now();
  561.             Hybrid_Introspective_Sort<int>(pom3, n);
  562.             end = std::chrono::system_clock::now();
  563.             diff = end - start;
  564.             durationTime = diff.count();
  565.             cout << "i:" << durationTime << endl;
  566.             cout << "tab8" << endl;
  567.             // **TABLICA 8**
  568.             for (int i = 0; i < n; i++) //kopiowanie tablicy
  569.             {
  570.                 pom[i] = tablica8[i];
  571.                 pom2[i] = tablica8[i];
  572.                 pom3[i] = tablica8[i];
  573.             }
  574.             //quick
  575.             start = std::chrono::system_clock::now();
  576.             quicksort<int>(pom, 0, n);
  577.             end = std::chrono::system_clock::now();
  578.             diff = end - start;
  579.             durationTime = diff.count();
  580.             cout << "q:" << durationTime << endl;
  581.             //merge
  582.             start = std::chrono::system_clock::now();
  583.             mergeSort<int>(pom2, 0, n);
  584.             end = std::chrono::system_clock::now();
  585.             diff = end - start;
  586.             durationTime = diff.count();
  587.             cout << "m:" << durationTime << endl;
  588.             //intro
  589.             start = std::chrono::system_clock::now();
  590.             Hybrid_Introspective_Sort<int>(pom3, n);
  591.             end = std::chrono::system_clock::now();
  592.             diff = end - start;
  593.             durationTime = diff.count();
  594.             cout << "i:" << durationTime << endl;
  595.             //Sprawdzenie poprawności działania algorytmu
  596.            
  597.         }
  598.         /*
  599.         delete[] pom;
  600.         delete[] pom2;
  601.         delete[] pom3;
  602.         delete[] tablica;
  603.         delete[] tablica2;
  604.         delete[] tablica3;
  605.         delete[] tablica4;
  606.         delete[] tablica5;
  607.         delete[] tablica6;
  608.         delete[] tablica7;
  609.         delete[] tablica8;
  610.     */
  611.        
  612.     }
  613.     /*
  614.     delete[] pom;
  615.     delete[] pom2;
  616.     delete[] pom3;
  617.     delete[] tablica;
  618.     delete[] tablica2;
  619.     delete[] tablica3;
  620.     delete[] tablica4;
  621.     delete[] tablica5;
  622.     delete[] tablica6;
  623.     delete[] tablica7;
  624.     delete[] tablica8;
  625.     pom = nullptr;
  626.     pom2 = nullptr;
  627.     pom3 = nullptr;
  628.     tablica = nullptr;
  629.     tablica2 = nullptr;
  630.     tablica3 = nullptr;
  631.     tablica4 = nullptr;
  632.     tablica5 = nullptr;
  633.     tablica6 = nullptr;
  634.     tablica7 = nullptr;
  635.     tablica8 = nullptr;
  636.     */
  637.     return 0;
  638.    
  639. }
  640.  
  641.  
  642.  
  643. // Uruchomienie programu: Ctrl + F5 lub menu Debugowanie > Uruchom bez debugowania
  644. // Debugowanie programu: F5 lub menu Debugowanie > Rozpocznij debugowanie
  645.  
  646. // Porady dotyczące rozpoczynania pracy:
  647. //   1. Użyj okna Eksploratora rozwiązań, aby dodać pliki i zarządzać nimi
  648. //   2. Użyj okna programu Team Explorer, aby nawiązać połączenie z kontrolą źródła
  649. //   3. Użyj okna Dane wyjściowe, aby sprawdzić dane wyjściowe kompilacji i inne komunikaty
  650. //   4. Użyj okna Lista błędów, aby zobaczyć błędy
  651. //   5. Wybierz pozycję Projekt > Dodaj nowy element, aby utworzyć nowe pliki kodu, lub wybierz pozycję Projekt > Dodaj istniejący element, aby dodać istniejące pliku kodu do projektu
  652. //   6. Aby w przyszłości ponownie otworzyć ten projekt, przejdź do pozycji Plik > Otwórz > Projekt i wybierz plik sln
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top