SHARE
TWEET

Untitled

a guest Mar 24th, 2019 63 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