API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
83
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 25.34 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include<cstdlib>
  3. #include<algorithm>
  4. #include<ctime>
  5. #include<cstdlib>
  6. #include<time.h>
  7. #include<fstream>
  8. #include<chrono>
  9. #define LEWY(w) ((2)*(w))
  10. #define PRAWY(w) ((w)*2 +1)
  11.  
  12. using namespace std;
  13.  
  14.  
  15. int licznik_operacji = 0 ;//porownanie i zamiana
  16.  
  17.  
  18. void losowe_liczby_increase(int n, int *tab, int k);
  19.  
  20. bool malejaco(int a, int b);
  21.  
  22. void losowe_liczby_decrease(int n, int *tab, int k);
  23.  
  24. void losowe_liczby_V(int n, int *tab, int k);
  25.  
  26. void losowe_liczby_A(int n, int *tab, int k);
  27.  
  28. void losowe_liczby_los(int n, int *tab, int k);
  29.  
  30.  
  31.  
  32. void Shell_Sort_sh(int *tab, int n)
  33. {
  34.     int buff, j;
  35.     for (int dys = n / 2; dys > 0; dys /= 2)
  36.     {
  37.         for (int i = dys; i < n; i++)
  38.         {
  39.             buff = tab[i];
  40.             licznik_operacji++;
  41.             for (j = i; j >= dys && tab[j - dys] > buff; j -= dys)
  42.                 tab[j] = tab[j - dys];
  43.                 licznik_operacji++;
  44.  
  45.             tab[j] = buff;
  46.             licznik_operacji++;
  47.         }
  48.     }
  49. }
  50.  
  51. void Shell_Sort_kn(int *tab, int n)
  52. {
  53.     int buff, j;
  54.     for (int dys = n / 3; dys > 0; dys /= 3)
  55.     {
  56.         for (int i = dys; i < n; i++)
  57.         {
  58.             buff = tab[i];
  59.             licznik_operacji++;
  60.             for (j = i; j >= dys && tab[j - dys] > buff; j -= dys)
  61.                 tab[j] = tab[j - dys];
  62.                 licznik_operacji++;
  63.  
  64.             tab[j] = buff;
  65.             licznik_operacji++;
  66.         }
  67.     }
  68. }
  69.  
  70. void insertion_sort_najprostszy(int n, int *tab)///////////przez wstawnianie
  71. {
  72.     int j;
  73.     int pom;
  74.     for (int i = 1; i < n; i++) {
  75.         pom = i;
  76.         j = i - 1;
  77.         while (tab[j] > tab[pom] && j >= 0) { swap(tab[j], tab[pom]); pom--; j--; }
  78.     }
  79. }
  80.  
  81. void scal(int dol, int srodek, int gora, int *tab, int * pom) {
  82.     int i = dol, j = srodek + 1;
  83.     for (int k = dol; k <= gora; k++) { pom[k] = tab[k]; }
  84.  
  85.     for (int k = dol; k <= gora; k++) {
  86.         if (i <= srodek) {
  87.             licznik_operacji++;
  88.             if (j <= gora) {
  89.                 licznik_operacji++;
  90.                 if (pom[j] < pom[i]) {
  91.                     tab[k] = pom[j++];
  92.                     licznik_operacji += 2;
  93.                 }
  94.                 else
  95.                     tab[k] = pom[i++];
  96.                 licznik_operacji++;
  97.             }
  98.             else
  99.                 tab[k] = pom[i++];
  100.             licznik_operacji++;
  101.         }
  102.         else
  103.             tab[k] = pom[j++];
  104.             licznik_operacji++;
  105.     }
  106. }
  107.  
  108. void Merge_sort(int dol, int gora, int *tab, int * pom) {
  109.     licznik_operacji++;
  110.     if (gora <= dol)  return;
  111.  
  112.     Merge_sort(dol, (dol + gora) / 2, tab, pom);
  113.     Merge_sort((dol + gora) / 2 + 1, gora, tab, pom);
  114.  
  115.     scal(dol, (gora + dol) / 2, gora, tab, pom);
  116. }
  117.  
  118.  
  119. void selection_sort(int tab[], const  int & n)//przez wybieranie
  120. {
  121.     int maxi = tab[1];
  122.     for (int j = 0; j < n - 1; j++) {
  123.         maxi = tab[j];
  124.         for (int i = j + 1; i < n; i++) {
  125.             if (tab[i] > maxi) {
  126.                 maxi = tab[i];
  127.                 tab[i] = tab[j];
  128.                 tab[j] = maxi;
  129.             }
  130.         }
  131.     }
  132. }
  133.  
  134. template<typename T, typename Assigment>
  135. void swap(T& a, T& b, Assigment&& as)
  136. {
  137.     T c;
  138.     as(c, a);
  139.     as(a, b);
  140.     as(b, c);
  141. }
  142.  
  143. template<typename Lesser, typename Greater, typename Assigment>
  144. void restore_heap(int n, int *tab, int  wezel, Lesser&& lesser, Greater&& greater, Assigment&& assigment) {//n to jest heap size
  145.     int largest;
  146.     int  l, p;
  147.     assigment(l, LEWY(wezel));
  148.     assigment(p, PRAWY(wezel));
  149.  
  150.     if (lesser(l, n) && greater(tab[l], tab[wezel])) //lewy
  151.     {
  152.         assigment(largest, l);
  153.     }
  154.     else
  155.     {
  156.         assigment(largest, wezel);
  157.     }
  158.     if (lesser(p,n) && greater(tab[p] , tab[largest]))
  159.     {
  160.         assigment(largest, p);
  161.     }
  162.     swap(tab[wezel], tab[largest], assigment);
  163.     if (largest != wezel)
  164.         restore_heap(n, tab, largest, lesser, greater, assigment);
  165. }
  166.  
  167. template<typename Lesser, typename Greater, typename Assigment>
  168. void zbuduj_heap(int n, int *tab, Lesser&& lesser, Greater&& greater, Assigment&& assigment) {
  169.  
  170.     int i;
  171.     assigment(i, n / 2);
  172.     for (; greater(i, 0); i--)
  173.     {
  174.         restore_heap(n, tab, i, lesser, greater, assigment);
  175.     }
  176.  
  177. }
  178.  
  179. template<typename Lesser, typename Greater, typename Assigment>
  180. void heap_sort(int *tab, int n, Lesser&& lesser, Greater&& greater, Assigment&& assigment) {//na potrzeby heap sort nalezy indeksowac od i =1 do n
  181.  
  182.     zbuduj_heap(n, tab, lesser, greater, assigment);
  183.     assigment(n, n - 1);
  184.     for (int i = n; i > 1; i--) {
  185.         swap(tab[1], tab[i], assigment);
  186.         assigment(n, n - 1);
  187.         restore_heap(n, tab, 1, lesser, greater, assigment);
  188.     }
  189.  
  190. }
  191.  
  192.  
  193.  
  194. void quick_sort(int tab[], int dol, int gora) {//pivotem pierwszy el tablicy
  195.     licznik_operacji++;
  196.     if (gora <= dol) { return; }
  197.     int pivot = tab[dol];
  198.     //cout << pivot << endl;///////////////////////wypisz wartosc pivota w kazdym wywolaniu
  199.     int j = gora + 1, i = dol - 1;
  200.     licznik_operacji+=3;////////////////////////////////////////////////////////////////////////////////// licznik
  201.  
  202.     while (1) {
  203.  
  204.         while (pivot > tab[++i]) { licznik_operacji += 2; };
  205.  
  206.  
  207.         while (pivot < tab[--j]) { licznik_operacji += 2; };
  208.         licznik_operacji += 3;
  209.         if (j >= i) { swap(tab[i], tab[j]); licznik_operacji ++;
  210.        
  211.         }
  212.         else { break; }
  213.     }
  214.     licznik_operacji+=2;
  215.     if (j > dol) { quick_sort(tab, dol, j); }
  216.     if (i < gora) { quick_sort(tab, i, gora); }
  217. }
  218.  
  219.  
  220. template<typename T>
  221. void sortowanie(T gen, fstream& plik, int* tab, int N = 4000000, int skok = 100000)
  222. {
  223.     plik << "n;czas;liczba operacji" << endl;
  224.     for (int n = 1; n < N; n += skok) {
  225.  
  226.         licznik_operacji = 0;
  227.         gen(n, tab, 500000);
  228.         auto start = chrono::steady_clock::now();
  229.         quick_sort(tab, 0, n - 1);
  230.         auto end = chrono::steady_clock::now();
  231.         // Store the time difference between start and end
  232.         auto diff = end - start;
  233.         plik << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  234.  
  235.     }
  236.     plik << ";;;" << endl;
  237. }
  238.  
  239. struct Assign
  240. {
  241.     template<typename A, typename B>
  242.     bool operator()(A&& a, B&& b) { return a = b; }
  243. };
  244.  
  245. template<typename Operator>
  246. struct OperatorCounter
  247. {
  248.     size_t counter{ 0 };
  249.     template<typename... Args>
  250.     bool operator()(Args&&... args)
  251.     {
  252.         bool rv = Operator()(std::forward<Args>(args)...);
  253.         counter++;
  254.         return rv;
  255.     }
  256. };
  257.  
  258.  
  259. int main()
  260. {
  261.     srand((int)time(NULL));
  262.  
  263.     auto start = chrono::steady_clock::now();
  264.     auto end = chrono::steady_clock::now();
  265.     auto diff = end - start;
  266.     int akcja;
  267.     /*cout << "wielkosc tablicy rand do posortowania";
  268.     int n;
  269.     cin >> n;
  270.     int* tab = new int[n];
  271.     srand((int) time(NULL));
  272.     losowe_liczby_A(n , tab, 50);///////////////po kazdym sortowaniu nalezy wyzerowac zmienna licznik operacji
  273.     cout << endl<<endl;*/
  274.     cout << "co chcesz robic : 1 wczytaj parametry sortowan do plikow;   2 wczytaj dane z klawiatury i zobacz posortowana tablice na konsoli ";
  275.     cin >> akcja;
  276.     switch (akcja) {
  277.                     case 1://aktualizowanie danych w plikach
  278.                     {     cout << "parametry ktorego sortowania chcesz zaktualizowac? 1 qs    2 hs  3  merge sort   4 shell srt shella 5 shell sort knutha";
  279.                         cin >> akcja;
  280.                         int* tab = new int[4000001];
  281.  
  282.  
  283.                             for (int i = 0; i < 4; i++)
  284.                             {//for na rzecz nie przeklikiwania wszystkiego
  285.                                         switch (akcja) {
  286.  
  287.                                         case 1: //quick sort
  288.                                         {//quick sort
  289.  
  290.                                             fstream quick_A, quick_V, quick_inc, quick_dec, quick_los;
  291.  
  292.                                             quick_A.open("quick_A.txt", ios::app | ios::out);
  293.                                             quick_V.open("quick_V.txt", ios::app | ios::out);
  294.                                             quick_inc.open("quick_increase.txt", ios::app | ios::out);
  295.                                             quick_dec.open("quick_decrease.txt", ios::app | ios::out);
  296.                                             quick_los.open("quick_los.txt", ios::app | ios::out);
  297.                                            
  298.                                            
  299.                                             sortowanie(losowe_liczby_A, quick_A, tab);
  300.                                            
  301.                                             break;
  302.                                         }
  303.  
  304.  
  305.                                         case 2://heap sort do zrobienie przetestowac heap sorta czy dziala
  306.                                         {
  307.  
  308.  
  309.  
  310.  
  311.  
  312.                                             fstream heap_A, heap_V, heap_inc, heap_dec, heap_los;
  313.                                             heap_A.open("heap_A.txt", ios::app | ios::out);
  314.                                             heap_V.open("heap_V.txt", ios::app | ios::out);
  315.                                             heap_inc.open("heap_increase.txt", ios::app | ios::out);
  316.                                             heap_dec.open("heap_decrease.txt", ios::app | ios::out);
  317.                                             heap_los.open("heap_los.txt", ios::app | ios::out);
  318.  
  319.                                            
  320.  
  321.                                             int* tab_heap = new int[4000001];//dla heap sorta gdzie tablica musi miec cindeksy 1 ...n
  322.                                             //losowe_liczby_los(n+1, tab_heap, 50);//zmieniam ta funkcje dla heap sorta gdzie tablica musi miec cindeksy 1 ...n pamietaj o n+1 dla heap sorta przy losowaniu
  323.                                             tab_heap[0] = NULL;
  324.                                             for (int n = 1; n < 4000000; n += 100000) {
  325.                                                 licznik_operacji = 0;
  326.                                                 OperatorCounter<Assign> assigment;
  327.                                                 OperatorCounter<less<int>> lesser;
  328.                                                 OperatorCounter<greater<int>> greater;
  329.  
  330.                                                 losowe_liczby_A(n + 1, tab_heap, 500000);
  331.                                                 start = chrono::steady_clock::now();
  332.                                                 heap_sort(tab_heap, n, lesser, greater, assigment);
  333.                                                 end = chrono::steady_clock::now();
  334.                                                 // Store the time difference between start and end
  335.                                                 diff = end - start;
  336.                                                 heap_A << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  337.                                                 cout << "Operations count:\nAssigment: " << assigment.counter << "\nLesser: " << lesser.counter << "\nGreater: " << greater.counter << '\n';
  338.                                             }
  339.                                             heap_A << ";;;" << endl;
  340.  
  341.                                             /////////////////////////////////////////////////////
  342.                                             /*
  343.                                             for (int n = 1; n < 4000000; n += 100000) {
  344.                                                 licznik_operacji = 0;
  345.                                                 losowe_liczby_V(n + 1, tab_heap, 500000);
  346.                                                 start = chrono::steady_clock::now();
  347.                                                 heap_sort(tab_heap, n);
  348.                                                 end = chrono::steady_clock::now();
  349.                                                 // Store the time difference between start and end
  350.                                                 diff = end - start;
  351.                                                 heap_V << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  352.                                             }
  353.                                             heap_V << ";;;" << endl;
  354.                                             ///////////////////////////////////////////////////
  355.                                             for (int n = 1; n < 4000000; n += 100000) {
  356.                                                 licznik_operacji = 0;
  357.                                                 losowe_liczby_los(n + 1, tab_heap, 500000);
  358.                                                 start = chrono::steady_clock::now();
  359.                                                 heap_sort(tab_heap, n);
  360.                                                 end = chrono::steady_clock::now();
  361.                                                 // Store the time difference between start and end
  362.                                                 diff = end - start;
  363.                                                 heap_los << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  364.                                             }
  365.                                             heap_los << ";;;" << endl;
  366.  
  367.                                             ////////////////////////////////////////////////////////////////////////////////////
  368.                                             for (int n = 1; n < 4000000; n += 100000) {
  369.                                                 licznik_operacji = 0;
  370.                                                 losowe_liczby_increase(n + 1, tab_heap, 500000);
  371.                                                 start = chrono::steady_clock::now();
  372.                                                 heap_sort(tab_heap, n);
  373.                                                 end = chrono::steady_clock::now();
  374.                                                 // Store the time difference between start and end
  375.                                                 diff = end - start;
  376.                                                 heap_inc << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  377.                                             }
  378.                                             heap_inc << ";;;" << endl;
  379.                                             ///////////////////////////////////////////////////
  380.  
  381.                                             for (int n = 1; n < 4000000; n += 100000) {
  382.                                                 licznik_operacji = 0;
  383.                                                 losowe_liczby_decrease(n + 1, tab_heap, 500000);
  384.                                                 start = chrono::steady_clock::now();
  385.                                                 heap_sort(tab_heap, n);
  386.                                                 end = chrono::steady_clock::now();
  387.                                                 // Store the time difference between start and end
  388.                                                 diff = end - start;
  389.                                                 heap_dec << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  390.                                             }
  391.                                             heap_dec << ";;;" << endl;
  392.                                             */
  393.                                             delete[] tab_heap;
  394.  
  395.                                             //break;
  396.                                         }
  397.  
  398.  
  399.                                         case 3://merge sort
  400.                                         {
  401.  
  402.  
  403.                                             fstream merge_A, merge_V, merge_inc, merge_dec, merge_los;
  404.                                             merge_A.open("merge_A.txt", ios::app | ios::out);
  405.                                             merge_V.open("merge_V.txt", ios::app | ios::out);
  406.                                             merge_inc.open("merge_increase.txt", ios::app | ios::out);
  407.                                             merge_dec.open("merge_decrease.txt", ios::app | ios::out);
  408.                                             merge_los.open("merge_los.txt", ios::app | ios::out);
  409.  
  410.  
  411.  
  412.                                             int* tab = new int[4000000];
  413.                                             int *pom = new int[4000000];
  414.  
  415.                                             for (int n = 1; n < 4000000; n += 100000) {
  416.                                                 licznik_operacji = 0;
  417.                                                 losowe_liczby_A(n, tab, 500000);
  418.                                                 start = chrono::steady_clock::now();
  419.                                                 Merge_sort(0, n, tab, pom);
  420.                                                 end = chrono::steady_clock::now();
  421.                                                 // Store the time difference between start and end
  422.                                                 diff = end - start;
  423.                                                 merge_A << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  424.                                             }
  425.                                             merge_A << ";;;" << endl;
  426.                                             //////////////////////////////////////////////////////////////
  427.  
  428.                                             for (int n = 1; n < 4000000; n += 100000) {
  429.                                                 licznik_operacji = 0;
  430.                                                 losowe_liczby_V(n, tab, 500000);
  431.                                                 start = chrono::steady_clock::now();
  432.                                                 Merge_sort(0, n, tab, pom);
  433.                                                 end = chrono::steady_clock::now();
  434.                                                 // Store the time difference between start and end
  435.                                                 diff = end - start;
  436.                                                 merge_V << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  437.                                             }
  438.                                             merge_V << ";;;" << endl;
  439.                                             ///////////////////////////////////////////////////
  440.                                             for (int n = 1; n < 4000000; n += 100000) {
  441.                                                 licznik_operacji = 0;
  442.                                                 losowe_liczby_los(n, tab, 500000);
  443.                                                 start = chrono::steady_clock::now();
  444.                                                 Merge_sort(0, n, tab, pom);
  445.                                                 end = chrono::steady_clock::now();
  446.                                                 // Store the time difference between start and end
  447.                                                 diff = end - start;
  448.                                                 merge_los << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  449.                                             }
  450.                                             merge_los << ";;;" << endl;
  451.                                             ////////////////////////////////////////////////////////////////////////////////////
  452.                                             for (int n = 1; n < 4000000; n += 100000) {
  453.                                                 licznik_operacji = 0;
  454.                                                 losowe_liczby_increase(n, tab, 500000);
  455.                                                 start = chrono::steady_clock::now();
  456.                                                 Merge_sort(0, n, tab, pom);
  457.                                                 end = chrono::steady_clock::now();
  458.                                                 // Store the time difference between start and end
  459.                                                 diff = end - start;
  460.                                                 merge_inc << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  461.                                             }
  462.                                             merge_inc << ";;;" << endl;
  463.                                             ///////////////////////////////////////////////////
  464.  
  465.                                             for (int n = 1; n < 4000000; n += 100000) {
  466.                                                 licznik_operacji = 0;
  467.                                                 losowe_liczby_decrease(n, tab, 500000);
  468.                                                 start = chrono::steady_clock::now();
  469.                                                 Merge_sort(0, n, tab, pom);
  470.                                                 end = chrono::steady_clock::now();
  471.                                                 // Store the time difference between start and end
  472.                                                 diff = end - start;
  473.                                                 merge_dec << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  474.  
  475.  
  476.                                             }
  477.                                             merge_dec << ";;;" << endl;
  478.  
  479.                                             delete[] pom;
  480.                                             //break;
  481.                                         }
  482.  
  483.  
  484.                                         case 4: //shell_sh z przyrostami shella
  485.                                         {
  486.  
  487.                                             fstream shell_sh_A, shell_sh_V, shell_sh_inc, shell_sh_dec, shell_sh_los, shell_sh;
  488.  
  489.                                             shell_sh_A.open("shell_sh_A.txt", ios::app | ios::out);
  490.                                             shell_sh_V.open("shell_sh_V.txt", ios::app | ios::out);
  491.                                             shell_sh_inc.open("shell_sh_increase.txt", ios::app | ios::out);
  492.                                             shell_sh_dec.open("shell_sh_decrease.txt", ios::app | ios::out);
  493.                                             shell_sh_los.open("shell_sh_los.txt", ios::app | ios::out);
  494.  
  495.  
  496.  
  497.  
  498.                                             for (int n = 1; n < 4000000; n += 100000) {
  499.  
  500.                                                 licznik_operacji = 0;
  501.                                                 losowe_liczby_A(n, tab, 500000);
  502.                                                 start = chrono::steady_clock::now();
  503.                                                 Shell_Sort_sh(tab, n);
  504.                                                 end = chrono::steady_clock::now();
  505.                                                 // Store the time difference between start and end
  506.                                                 diff = end - start;
  507.                                                 shell_sh_A << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  508.                                             }
  509.                                             shell_sh_A << ";;;" << endl;;
  510.                                             /////////////////////////////////////////////////////
  511.  
  512.                                             for (int n = 1; n < 4000000; n += 100000) {
  513.                                                 licznik_operacji = 0;
  514.                                                 losowe_liczby_V(n, tab, 500000);
  515.                                                 start = chrono::steady_clock::now();
  516.                                                 Shell_Sort_sh(tab, n);
  517.                                                 end = chrono::steady_clock::now();
  518.                                                 // Store the time difference between start and end
  519.                                                 diff = end - start;
  520.                                                 shell_sh_V << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  521.                                             }
  522.                                             shell_sh_V << ";;;" << endl;;;
  523.                                             ///////////////////////////////////////////////////
  524.                                             for (int n = 1; n < 4000000; n += 100000) {
  525.                                                 licznik_operacji = 0;
  526.                                                 losowe_liczby_increase(n, tab, 500000);
  527.                                                 start = chrono::steady_clock::now();
  528.                                                 Shell_Sort_sh(tab, n);
  529.                                                 end = chrono::steady_clock::now();
  530.                                                 // Store the time difference between start and end
  531.                                                 diff = end - start;
  532.                                                 shell_sh_inc << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  533.                                             }
  534.                                             shell_sh_inc << ";;;" << endl;;;
  535.                                             ///////////////////////////////////////////////////
  536.  
  537.                                             for (int n = 1; n < 4000000; n += 100000) {
  538.                                                 licznik_operacji = 0;
  539.                                                 losowe_liczby_decrease(n, tab, 500000);
  540.                                                 start = chrono::steady_clock::now();
  541.                                                 Shell_Sort_sh(tab, n);
  542.                                                 end = chrono::steady_clock::now();
  543.                                                 // Store the time difference between start and end
  544.                                                 diff = end - start;
  545.                                                 shell_sh_dec << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  546.                                             }
  547.                                             shell_sh_dec << ";;;" << endl;;
  548.                                             ///////////////////////////////////////////////////
  549.                                             for (int n = 1; n < 4000000; n += 100000) {
  550.                                                 licznik_operacji = 0;
  551.                                                 losowe_liczby_los(n, tab, 500000);
  552.                                                 start = chrono::steady_clock::now();
  553.                                                 Shell_Sort_sh(tab, n);
  554.                                                 end = chrono::steady_clock::now();
  555.                                                 // Store the time difference between start and end
  556.                                                 diff = end - start;
  557.                                                 shell_sh_los << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  558.                                             }
  559.                                             shell_sh_los << ";;;" << endl;;
  560.  
  561.  
  562.  
  563.  
  564.                                             //break;
  565.                                         }
  566.  
  567.  
  568.                                         case 5://z przyrostami knutha
  569.                                         {
  570.  
  571.                                             fstream shell_kn_A, shell_kn_V, shell_kn_inc, shell_kn_dec, shell_kn_los;
  572.  
  573.                                             shell_kn_A.open("shell_kn_A.txt", ios::app | ios::out);
  574.                                             shell_kn_V.open("shell_kn_V.txt", ios::app | ios::out);
  575.                                             shell_kn_inc.open("shell_kn_increase.txt", ios::app | ios::out);
  576.                                             shell_kn_dec.open("shell_kn_decrease.txt", ios::app | ios::out);
  577.                                             shell_kn_los.open("shell_kn_los.txt", ios::app | ios::out);
  578.  
  579.  
  580.  
  581.  
  582.                                             for (int n = 1; n < 4000000; n += 100000) {
  583.  
  584.                                                 licznik_operacji = 0;
  585.                                                 losowe_liczby_A(n, tab, 500000);
  586.                                                 start = chrono::steady_clock::now();
  587.                                                 Shell_Sort_kn(tab, n);
  588.                                                 end = chrono::steady_clock::now();
  589.                                                 // Store the time difference between start and end
  590.                                                 diff = end - start;
  591.                                                 shell_kn_A << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  592.                                             }
  593.                                             shell_kn_A << ";;;" << endl;
  594.                                             /////////////////////////////////////////////////////
  595.  
  596.                                             for (int n = 1; n < 4000000; n += 100000) {
  597.                                                 licznik_operacji = 0;
  598.                                                 losowe_liczby_V(n, tab, 500000);
  599.                                                 start = chrono::steady_clock::now();
  600.                                                 Shell_Sort_kn(tab, n);
  601.                                                 end = chrono::steady_clock::now();
  602.                                                 // Store the time difference between start and end
  603.                                                 diff = end - start;
  604.                                                 shell_kn_V << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  605.                                             }
  606.                                             shell_kn_V << ";;;" << endl;
  607.                                             ///////////////////////////////////////////////////
  608.                                             for (int n = 1; n < 4000000; n += 100000) {
  609.                                                 licznik_operacji = 0;
  610.                                                 losowe_liczby_increase(n, tab, 500000);
  611.                                                 start = chrono::steady_clock::now();
  612.                                                 Shell_Sort_kn(tab, n);
  613.                                                 end = chrono::steady_clock::now();
  614.                                                 // Store the time difference between start and end
  615.                                                 diff = end - start;
  616.                                                 shell_kn_inc << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  617.                                             }
  618.                                             shell_kn_inc << ";;;" << endl;
  619.                                             ///////////////////////////////////////////////////
  620.  
  621.                                             for (int n = 1; n < 4000000; n += 100000) {
  622.                                                 licznik_operacji = 0;
  623.                                                 losowe_liczby_decrease(n, tab, 500000);
  624.                                                 start = chrono::steady_clock::now();
  625.                                                 Shell_Sort_kn(tab, n);
  626.                                                 end = chrono::steady_clock::now();
  627.                                                 // Store the time difference between start and end
  628.                                                 diff = end - start;
  629.                                                 shell_kn_dec << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  630.                                             }
  631.                                             shell_kn_dec << ";;;" << endl;
  632.                                             ///////////////////////////////////////////////////
  633.                                             for (int n = 1; n < 4000000; n += 100000) {
  634.                                                 licznik_operacji = 0;
  635.                                                 losowe_liczby_los(n, tab, 500000);
  636.                                                 start = chrono::steady_clock::now();
  637.                                                 Shell_Sort_kn(tab, n);
  638.                                                 end = chrono::steady_clock::now();
  639.                                                 // Store the time difference between start and end
  640.                                                 diff = end - start;
  641.                                                 shell_kn_los << n << ";" << chrono::duration <double, milli>(diff).count() << "" << ";" << licznik_operacji << endl;
  642.                                             }
  643.                                             shell_kn_los << ";;;" << endl;
  644.  
  645.  
  646.  
  647.  
  648.                                             break;
  649.                                         }
  650.  
  651.  
  652.                                         default: {system("pause");
  653.                                             delete[] tab;
  654.                                             return 0; }
  655.                                         }
  656.  
  657.                                        
  658.                                    
  659.                             }
  660.                         delete[] tab;
  661.                         return 0;
  662.                     }      
  663.  
  664.                        
  665.     case 2://pisanie z klawiatury
  666.     {
  667.         cout << "najpierw podaj dlugosc tablicy do posortowania";
  668.         int n;
  669.         cin >> n;
  670.         int* tab = new int[n];
  671.         for (int i = 0; i < n; i++) {
  672.             cout << "podawaj liczby dopoki petla sie nie skonczy";
  673.             cin >> tab[i];
  674.  
  675.         }
  676.  
  677.  
  678.         cout << "ktorego sortowania dane chcesz podac z klawiatury?: 1 qs    2 hs  3  merge sort   4 shell srt shella 5 shell sort knutha cokolwiek innego zeby przerwac";
  679.         cin >> akcja;
  680.         switch (akcja) {
  681.  
  682.         case 1: {
  683.             quick_sort(tab,0,n-1);
  684.  
  685.             for (int i = 0; i < n;i++) {
  686.                 cout << tab[i] << ", ";
  687.             }
  688.  
  689.             break;
  690.         }
  691.         case 2: {
  692.             int* tab2 = new int[n + 1];
  693.             tab2[0] = NULL;
  694.             for (int i = 1; i < n + 1;i++) {
  695.                 tab2[i] = tab[i - 1];
  696.             }
  697.  
  698.             //heap_sort(tab2,n+1);
  699.             for (int i = 0; i < n; i++) {
  700.                 cout << tab2[i] << ", ";
  701.             }
  702.  
  703.             delete[] tab2 ;
  704.             break;
  705.         }
  706.         case 3: {
  707.             int * pom = new int[n];
  708.             Merge_sort(0,n-1,tab,pom);
  709.             for (int i = 0; i < n; i++) {
  710.                 cout << tab[i] << ", ";
  711.             }
  712.  
  713.             delete [] pom;
  714.             break;
  715.         }
  716.         case 4: {
  717.             Shell_Sort_sh(tab,n);
  718.             for (int i = 0; i < n; i++) {
  719.                 cout << tab[i] << ", ";
  720.             }
  721.  
  722.  
  723.             break;
  724.         }
  725.         case 5: {
  726.             Shell_Sort_kn(tab,n);
  727.             for (int i = 0; i < n; i++) {
  728.                 cout << tab[i] << ", ";
  729.             }
  730.  
  731.  
  732.             break;
  733.         }
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.         }
  741.  
  742.         delete[] tab;
  743.  
  744.  
  745.  
  746.  
  747.  
  748.  
  749.  
  750.  
  751.  
  752.  
  753.  
  754.         break;
  755.     }
  756.  
  757.  
  758.     default: {return 0; }
  759.  
  760.  
  761.              break;
  762.     }
  763.  
  764.     //shell_sort_sh(n,tab);
  765.     //insertion_sort_najprostszy(n,tab);
  766.     //quick_sort(tab, 0, n - 1);
  767.     //selection_sort(tab ,n);
  768.     //shell_sort_kn(n,tab);
  769.  
  770.     ///////////////////////merge sort
  771.     /*int *pom = new int[n];//na potrzeby merge sorta pomocnicza struktura danych
  772.     Merge_sort(0,n-1,tab,pom);
  773.     delete[] pom;*/
  774.  
  775.     system("pause");
  776.  
  777.  
  778.     cout << "koniec";
  779.  
  780.     return 0;
  781. }
  782.  
  783.  
  784.  
  785. void losowe_liczby_decrease(int n, int *tab, int k) {
  786.  
  787.     losowe_liczby_los(n, tab, k);
  788.     sort(tab, tab + n - 1, malejaco);
  789.  
  790.     /*for (int i = 0; i < n; i++)
  791.     {
  792.         printf("%d, ", tab[i]);
  793.     }
  794.     cout << endl;
  795.     */
  796. }
  797.  
  798.  
  799. bool malejaco(int a, int b) {
  800.  
  801.     return (a > b);
  802.  
  803. }
  804.  
  805.  
  806. void losowe_liczby_increase(int n, int *tab, int k) {
  807.     losowe_liczby_los(n, tab, k);
  808.     sort(tab, tab + n - 1);
  809.  
  810.     /*for (int i = 0; i < n; i++)
  811.     {
  812.         printf("%d, ", tab[i]);
  813.     }
  814.     cout << endl;
  815.     */
  816. }
  817.  
  818.  
  819.  
  820. void losowe_liczby_V(int n, int *tab, int k) {
  821.  
  822.     losowe_liczby_los(n, tab, k);
  823.     sort(tab + n / 2, tab + n);
  824.     sort(tab, tab + n / 2, malejaco);
  825.     /*for (int i = 0; i < n; i++)
  826.     {
  827.         printf("%d, ", tab[i]);
  828.     }
  829.     cout << endl;
  830.     */
  831. }
  832.  
  833. void losowe_liczby_A(int n, int *tab, int k) {
  834.     losowe_liczby_los(n, tab, k);
  835.  
  836.     sort(tab + n / 2, tab + n, malejaco);
  837.     sort(tab, tab + n / 2);
  838.  
  839.     /*for (int i = 0; i < n; i++)
  840.     {
  841.         printf("%d, ", tab[i]);
  842.     }
  843.     cout << endl;
  844.     */
  845.  
  846. }
  847.  
  848. void losowe_liczby_los(int n, int *tab, int k) {
  849.     for (int i = 0; i <n; i++)
  850.     {
  851.         tab[i] = ((int)rand() % (k - 10)) + 10;
  852.     }
  853.     /*for (int i = 0; i < n; i++)
  854.         {
  855.             printf("%d, ", tab[i]);
  856.         }
  857.         cout << endl;
  858.         */
  859.  
  860. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!