SHARE
TWEET

LAB 2

Mary_99 Jan 29th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <time.h>
  3. #include <algorithm>
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. //-----------------------------------------------SORTS-------------------------------------------------------------
  9.  
  10. void insertion_sort(int tab[], int n) //insertion srt starts at 2_nd element
  11. {
  12.     int i, key, j;
  13.     for (i = 1; i <= n - 1; i++) {
  14.         key = i;
  15.  
  16.         while (key >= 0 && tab[key - 1] > tab[key]) {
  17.             j = tab[key];
  18.             tab[key] = tab[key - 1];
  19.             tab[key - 1] = j;
  20.             key--;
  21.         }
  22.  
  23.     }
  24. }
  25.  
  26. void merge(int tab[], int l, int m, int r)
  27. {
  28.     int i, j, k;
  29.     int n1 = m - l + 1;
  30.     int n2 = r - m;
  31.     //create temp arrays
  32.     int L[n1], R[n2];
  33.     //put copy data to arrays L & R
  34.     for (i = 0; i < n1; i++) {
  35.         L[i] = tab[l + i];
  36.     }
  37.     for (j = 0; j < n2; j++) {
  38.         R[j] = tab[m + 1 + j];
  39.     }
  40.     i = 0;
  41.     j = 0;
  42.     k = l;
  43.     while (i < n1 && j < n2) {
  44.         if (L[i] <= R[j]) {
  45.             tab[k] = L[i];
  46.             i++;
  47.         } else {
  48.             tab[k] = R[j];
  49.             j++;
  50.         }
  51.         k++;
  52.     }
  53.     //copy the remaining elements of L[]
  54.     while (i < n1) {
  55.         tab[k] = L[i];
  56.         i++;
  57.         k++;
  58.     }
  59.     //copy the remaining elements of R[]
  60.     while (j < n2) {
  61.         tab[k] = R[j];
  62.         j++;
  63.         k++;
  64.     }
  65. }
  66.  
  67. //bottom- up merge sort = iterative merge sort
  68. void merge_sort(int tab[], int l, int r)
  69. {
  70.     if (l < r) {
  71.         int m = (l + r) / 2;
  72.         merge_sort(tab, l, m);
  73.         merge_sort(tab, m + 1, r);
  74.         merge(tab, l, m, r);
  75.     }
  76. }
  77. //tiled bottom-up merge sort = merge + insertion
  78.  
  79. void tiled_bottom_up_merge_sort(int tab[], int l, int r, int threshold)
  80. {
  81.  
  82.  
  83.     if (l < r) {
  84.         if ((r - l) <= threshold) {
  85.             insertion_sort(tab, threshold);
  86.         } else {
  87.             int m = (l + r) / 2;
  88.             merge_sort(tab, l, m);
  89.             merge_sort(tab, m + 1, r);
  90.             merge(tab, l, m, r);
  91.         }
  92.     }
  93. }
  94.  
  95. int compare(const void *a, const void *b)
  96. {
  97.     return (*(int *) a - *(int *) b);
  98. }
  99.  
  100. //---------------------------------printing the array-------------------------------------------------------------
  101.  
  102. void print_tab(int tab[], int n) {
  103.     int i;
  104.     for (i = 0; i < n; i++)
  105.         printf("%d%s", tab[i], "; ");
  106.     printf("\n\n");
  107. }
  108.  
  109. //------------------------------------------------------------------------time---------------------------------------------------------------------------
  110.  
  111. void time_Check(float Start, float Stop) {
  112.     float Time;
  113.     Time = (Stop - Start) / CLOCKS_PER_SEC;
  114.     printf("Sorting time:\n %f  s ", Time);
  115.     printf("\n\n");
  116. }
  117. //----------------------------------------------------------------------generate numbers------------------------------------------------------------------
  118.  
  119. void numbers_generate(int tab[], int n) {
  120.     int i;
  121.     srand(time(NULL)); //randomize speed
  122.     for (i = 0; i < n; i++) {
  123.         tab[i] = rand() % n;
  124.     }
  125. }
  126.  
  127. //---------------------------------------------------------------------main function---------------------------------------------------------------------------
  128.  
  129. int main() {
  130.     int numbers[1000];
  131.     float start;
  132.     float stop;
  133.     int n;
  134.     n = (sizeof(numbers)) / (sizeof(int)); //find the size of array
  135.  
  136.     cout << "MERGE SORT" << endl << endl;
  137.     numbers_generate(numbers, n);
  138.     print_tab(numbers, n);
  139.     start = clock();
  140.     merge_sort(numbers, 0, n - 1);
  141.     stop = clock();
  142.     print_tab(numbers, n);
  143.     time_Check(start, stop);
  144.  
  145.  
  146.     cout << "TILED BOTTOM UP MARGE SORT" << endl << endl;
  147.     numbers_generate(numbers, n);
  148.     print_tab(numbers, n);
  149.     start = clock();
  150.     tiled_bottom_up_merge_sort(numbers, 0, n - 1, n / 10);
  151.     stop = clock();
  152.     print_tab(numbers, n);
  153.     time_Check(start, stop);
  154.  
  155.  
  156.     cout << "QUICK SORT" << endl << endl;
  157.     numbers_generate(numbers, n);
  158.     print_tab(numbers, n);
  159.     start = clock();
  160.     qsort(numbers, n, sizeof(int), compare);
  161.     stop = clock();
  162.     print_tab(numbers, n);
  163.     time_Check(start, stop);
  164. //----------------------------------------------------n=20^22 for tiled bottom-up merge sort-------------------------------------------------------------------
  165.     int numbers1[16384];
  166.     cout << "TILED BOTTOM UP MARGE SORT for n = 20^22 " << endl << endl;
  167.     numbers_generate(numbers1, n);
  168.     print_tab(numbers1, n);
  169.     start = clock();
  170.     tiled_bottom_up_merge_sort(numbers1, 0, n - 1, (20^22) / 10);
  171.     stop = clock();
  172.     print_tab(numbers1, n);
  173.     time_Check(start, stop);
  174.       return 0;
  175. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top