daily pastebin goal
68%
SHARE
TWEET

sort

a guest Feb 22nd, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include "time.h"
  4.  
  5.  
  6. using namespace std;
  7.  
  8. //медиана из 3х элементов
  9. int pivot(int a, int b, int c)
  10. {
  11.     return min(max(a, b), max(b, c));
  12. }
  13.  
  14. int part(int *arr, int lef, int rig)
  15. {
  16.     int l = lef;
  17.     int r = rig;
  18.     int piv = pivot(arr[l],arr[(l + r) / 2], arr[r]);
  19.    
  20.     while (l <= r)
  21.     {
  22.         while (arr[l] < piv)
  23.             l++;
  24.         while (arr[r] > piv)
  25.             r--;
  26.  
  27.         if (l <= r)
  28.             swap(arr[l++], arr[r--]);
  29.     }
  30.     return l;
  31. }
  32.  
  33. void quick_sort(int *arr, int l, int r)
  34. {
  35.     if (l < r)
  36.     {
  37.         int p = part(arr, l, r);
  38.         quick_sort(arr, l, p - 1);
  39.         quick_sort(arr, p, r);
  40.     }
  41.     return ;
  42. }
  43.  
  44.  
  45. //Просеивание элемента через кучу
  46. void sift_down(int *arr, int i, int end)
  47. {
  48.     int root = i;
  49.    
  50.     // Пока у корня хотя бы один потомок
  51.     while (root * 2 + 1 <= end)
  52.     {
  53.         // левый потомок
  54.         int child = root * 2 + 1;
  55.         //если есть правый потомок и он больше левого, берём его
  56.         if ((child + 1 <=
  57.             end) && (arr[child] < arr[child + 1]))
  58.             child++;
  59.         //если корень меньше выбранного потомка, меняем их местами
  60.         if (arr[root] < arr[child])
  61.         {
  62.             swap(arr[root], arr[child]);
  63.             //назначаем корнем выбранного потомка
  64.             root = child;
  65.         }
  66.         else return ;
  67.     }
  68. }
  69.  
  70. void heapify(int *arr, int n)
  71. {
  72.     //индекс последнего родительского узла
  73.     int count = n;
  74.     //Выбирается последний из родительских узлов
  75.     int start = (count - 2) / 2;
  76.     while (start >= 0)
  77.     {
  78.         // и из каждого узла (n - 1) уровня запускается просеивание
  79.         sift_down(arr, start, count - 1);
  80.         //переход к предыдущему узлу (n - 1) и выше узлов
  81.         start--;
  82.     }
  83. }
  84.  
  85. void heap_sort(int *arr, int n)
  86. {
  87.     //создаём кучу на основе массива
  88.     heapify(arr, n);
  89.     int end = n - 1;
  90.  
  91.     while (end > 0)
  92.     {
  93.         //Меняем местами корень дерева и последний элемент
  94.         swap(arr[end], arr[0]);
  95.         //сдвигаем индекс последнего элемента
  96.         end--;
  97.         //просеиваем новый корень через кучу
  98.         //каждый раз не затрагивая на 1 элемент из конца меньше
  99.         sift_down(arr, 0, end);
  100.     }
  101. }
  102.  
  103.  
  104. //Буффер, для того, чтобы не выделять каждый раз память
  105. int *buff;
  106.  
  107. void merge(int *arr, int left, int mid, int right)
  108. {
  109.     int itR = 0;
  110.     int itL = 0;
  111.  
  112.     //массив делится на 2 части, обе сливаются в буффер
  113.     while ((left + itL < mid) && (mid + itR < right))
  114.     {
  115.         if (arr[left + itL] < arr[mid + itR])
  116.         {
  117.             buff[itR + itL] = arr[left + itL];
  118.             itL++;
  119.         }
  120.         else
  121.         {
  122.             buff[itR + itL] = arr[mid + itR];
  123.             itR++;
  124.         }
  125.     }
  126.  
  127.     //в левой было больше элементов
  128.     while (left + itL < mid)
  129.     {
  130.         buff[itR + itL] = arr[left + itL];
  131.         itL++;
  132.     }
  133.     //в правой болы больше элементов
  134.     while (mid + itR < right)
  135.     {
  136.         buff[itR + itL] = arr[mid + itR];
  137.         itR++;
  138.     }
  139.  
  140.     for (int i = 0; i < itR + itL; i++)
  141.     {
  142.         arr[left + i] = buff[i];
  143.     }
  144. }
  145.  
  146. void merge_sort(int *arr, int left, int right)
  147. {
  148.     if (left + 1 >= right)
  149.         return ;
  150.     // разделение массива на 2 части
  151.     int mid = (right + left) / 2;
  152.  
  153.     merge_sort(arr, left, mid);
  154.     merge_sort(arr, mid, right);
  155.     merge(arr, left, mid, right);
  156. }
  157.  
  158. void print(int *arr, int n)
  159. {
  160.     for (int i = 0; i < n; i++)
  161.         cout << arr[i] << " ";
  162.     cout << endl;
  163. }
  164.  
  165. int main()
  166. {
  167.     int n;
  168.     cin >> n;
  169.     buff = new int[n];
  170.  
  171.     int *inf1 = new int[n];
  172.     int *inf2 = new int[n];
  173.     int *inf3 = new int[n];
  174.  
  175.     srand(time(NULL));
  176.  
  177.     for (int i = 0; i < n; i++)
  178.     {
  179.         inf1[i] = rand();
  180.         inf2[i] = inf1[i];
  181.         inf3[i] = inf1[i];
  182.         //cout << inf1[i] << " ";
  183.     }
  184.  
  185.     //vector <int> inf_2(inf);
  186.     //vector <int> inf_3(inf);
  187.  
  188.     cout << endl;
  189.  
  190.     cout << "quick sort" << endl;
  191.     double time1 = clock();
  192.     quick_sort(inf1, 0, n - 1);
  193.     time1 = clock() - time1;
  194.     //print(inf1, n);
  195.  
  196.  
  197.     cout << "heap sort" << endl;
  198.     double time2 = clock();
  199.     heap_sort(inf2, n);
  200.     time2 = clock() - time2;
  201.     //print(inf_2);
  202.  
  203.     cout << "merge sort" << endl;
  204.     double time3 = clock();
  205.     merge_sort(inf3, 0, n);
  206.     time3 = clock() - time3;
  207.     //print(inf_3);
  208.    
  209.     cout << "Quick sort time == " << time1 << endl;
  210.     cout << "Heap sort time == " << time2 << endl;
  211.     cout << "Merge sort time == " << time3 << endl;
  212.  
  213.     system("pause");
  214. }
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