Facebook
From Matyo, 2 Weeks ago, written in C++.
Embed
Download Paste or View Raw
Hits: 204
  1. #include <iostream>
  2. #include <chrono>
  3. using namespace std;
  4. using namespace std::chrono;
  5.  
  6.  
  7. void swap(int* a, int* b)
  8. {
  9.     int t = *a;
  10.     *a = *b;
  11.     *b = t;
  12. }
  13.  
  14. void Bubblesort(int a[], int n)
  15. {
  16.     int r, i, j;
  17.     for (i = 0; i < n - 1; i++)
  18.     {
  19.        // bool flag = false;
  20.         for (j = 0; j < n - i - 1; j++)
  21.             if (a[j] > a[j + 1])
  22.             {
  23.          //       flag = true;
  24.                 r = a[j];
  25.                 a[j] = a[j + 1];
  26.                 a[j + 1] = r;
  27.             }
  28.         //if (!flag)
  29.          //   break;
  30.     }//36, 41, 35, 43, 58
  31.        
  32. }
  33.  
  34. void Selection_Sort(int arr[], int n)
  35. {
  36.     int i, j, min, rab;
  37.     for (i = 0; i < n - 1; i++)
  38.     {  
  39.         min = i;
  40.         for (j = i + 1; j < n; j++)
  41.         {
  42.             if (arr[j] < arr[min])
  43.                 min = j;
  44.         }
  45.         if (min != i)
  46.         {
  47.            // swap(&arr;[min], &arr;[i]);
  48.             rab = arr[i];  arr[i] = arr[min];  arr[min] = rab;
  49.         }
  50.     }
  51. }
  52.  
  53. void Insertion_Sort(int arr[], int n)  // без рекурсия
  54. {
  55.     int i, key, j;
  56.     for (i = 1; i < n; i++)
  57.     {
  58.         key = arr[i];
  59.         j = i - 1;
  60.  
  61.         while (j >= 0 && arr[j] > key)
  62.         {
  63.             arr[j + 1] = arr[j];
  64.             j = j - 1;
  65.         }
  66.         arr[j + 1] = key;
  67.     }
  68. }
  69.  
  70. void ins_r(int a[], int i, int num)   // с рекурсия
  71. {
  72.     int rab, j;  j = i - 1;
  73.     while ((j >= 0) && (a[j] > a[j + 1]))
  74.     {
  75.         //swap(&a[j], &a[j + 1]);
  76.         rab = a[j];  a[j] = a[j + 1];  a[j + 1] = rab;
  77.         j--;
  78.     }
  79.     if (i < num - 1)  ins_r(a, i + 1, num);
  80. }
  81.  
  82. int partition(int a[], int low, int high)
  83. {
  84.     int pivot = a[high]; // pivot
  85.     int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
  86.  
  87.     for (int j = low; j <= high - 1; j++)
  88.     {
  89.         // If current element is smaller than the pivot
  90.         if (a[j] < pivot)
  91.         {
  92.             i++; // increment index of smaller element
  93.             swap(&a[i], &a[j]);
  94.         }
  95.     }
  96.     swap(&a[i + 1], &a[high]);
  97.     return (i + 1);
  98. }
  99.  
  100. void quicksort(int a[], int L, int R)
  101. {
  102.     int q;
  103.     if (L < R)
  104.     {
  105.         q = partition(a, L, R);
  106.         quicksort(a, L, q - 1);
  107.         quicksort(a, q + 1, R);
  108.     }
  109. }
  110.  
  111. void merge(int arr[], int l, int m, int r)
  112. {
  113.     int i, j, k;
  114.     int n1 = m - l + 1;
  115.     int n2 = r - m;
  116.    // cout << "\n n1=" << n1;
  117.    // cout << "\n n2=" << n2;
  118.     // Sazdavame podmasivite
  119.     int L[1000], R[1000];
  120.     //Popalvame podmasivite
  121.     for (i = 0; i < n1; i++)
  122.         L[i] = arr[l + i];
  123.     for (j = 0; j < n2; j++)
  124.         R[j] = arr[m + 1 + j];
  125.  
  126.     //Сливаме подмасивите обратно в един
  127.     i = 0; // Инициализираме индекс за първия подмасив
  128.     j = 0; // Инициализираме индекс за втория подмасив
  129.     k = l; // Инициализираме индекс за общия масив
  130.     while (i < n1 && j < n2) {
  131.         if (L[i] <= R[j]) {
  132.             arr[k] = L[i];
  133.             i++;
  134.         }
  135.         else {
  136.             arr[k] = R[j];
  137.             j++;
  138.         }
  139.         k++;
  140.     }
  141.  
  142.     /* Копираме оставащите елементи от L[], ако условието е изпълнено */
  143.     while (i < n1) {
  144.         arr[k] = L[i];
  145.         i++;
  146.         k++;
  147.     }
  148.  
  149.     //Копираме оставащите елементи от R[], ако условието е изпълнено
  150.     while (j < n2) {
  151.         arr[k] = R[j];
  152.         j++;
  153.         k++;
  154.     }
  155. }
  156.  
  157. void MergeSort(int arr[], int l, int r)
  158. {
  159.     int m;
  160.     if (l < r)
  161.     {
  162.         m = l + (r - l) / 2;
  163.         MergeSort(arr, l, m);
  164.         MergeSort(arr, m + 1, r);
  165.         merge(arr, l, m, r);
  166.     }
  167. }
  168.  
  169. void heapify(int arr[], int n, int i)
  170. {
  171.     int largest = i;
  172.     int l = 2 * i + 1; // namirane na leviq naslednik = 2*i + 1
  173.     int r = 2 * i + 2; // namirane na desniq naslednik = 2*i + 2
  174.  
  175.     // Ako leviq naslednik e po golqm ot korena
  176.     if (l < n && arr[l] > arr[largest])
  177.         largest = l;
  178.  
  179.     // Ako desniq e po golqm
  180.     if (r < n && arr[r] > arr[largest])
  181.         largest = r;
  182.  
  183.     // Ako nai golemiq element ne e korena e neobhodimo razmqna
  184.     if (largest != i) {
  185.         swap(&arr;[i], &arr;[largest]);
  186.  
  187.         // Recursively heapify the affected sub-tree
  188.         heapify(arr, n, largest);
  189.     }
  190. }
  191.  
  192. void heapSort(int arr[], int n)
  193. {
  194.     // Postroqvame piramida
  195.     for (int i = n / 2 - 1; i >= 0; i--)
  196.         heapify(arr, n, i);
  197.  
  198.     // Edin po Edin prashtame nai golemiq element nai otzad
  199.     for (int i = n - 1; i > 0; i--) {
  200.        
  201.         swap(arr[0], arr[i]);
  202.  
  203.        //Izvikvame funkciqta da proveri dali darvoto e otnovo piramida
  204.         heapify(arr, i, 0);
  205.     }
  206. }
  207.  
  208. void Print(int a[], int n)
  209. {
  210.     cout << "Elementite na masiva sa: {";
  211.     for (int i = 0; i < n; i++)
  212.     {
  213.         cout << " " << a[i];
  214.     }
  215.     cout << " }";
  216. }
  217.  
  218. int main()
  219. {
  220.     int arr[1000];// = { 38,27,43,3,9,82,10 };
  221.     int n = sizeof(arr) / sizeof(arr[0]);
  222.     //srand(time(0));
  223.     for (int i = 0; i < n; i++)
  224.         arr[i] = rand() % 5001;
  225.     cout << "\n-------------Nesortiran masiv-------------" << endl;;
  226.     Print(arr, n);
  227.    // Bubblesort(arr, n);
  228.     auto start = high_resolution_clock::now();
  229.    // Bubblesort(arr, n);
  230.     //Selection_Sort(arr, n);
  231.     //Insertion_Sort(arr, n);    // InsertionSort без рекурсия
  232.     //ins_r(arr, 1, n);  // InsertionSort с рекурсия
  233.     quicksort(arr, 0, n - 1);
  234.     //MergeSort(arr, 0, n - 1);
  235.    // heapSort(arr, n);
  236.     auto stop = high_resolution_clock::now();
  237.      auto durati>(stop - start);
  238.     cout << "\n\n-------------sortiran masiv-------------" << endl;;
  239.     Print(arr, n);
  240.     cout << "\nVremeto za sortirane na masiva e: " << duration.count() << " microseconds" << endl;
  241. }
  242.