SHARE
TWEET

LAB 2&1

Mary_99 Jan 29th, 2019 101 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. //----------------------------------------------------sorts from lab 1------------------------------------------------
  8. void bubble_sort( int tab[], int n)
  9. {
  10.     int step;
  11.     int temp;
  12.     int i;
  13.     for( step = 0; step < n - 1; ++ step)
  14.     for(i = 0; i < n - step - 1;++i)
  15.     {
  16.         if(tab[i] > tab[i+1])
  17.         {
  18.             temp = tab[i];
  19.             tab[i] = tab[i+1];
  20.             tab[i+1] =  temp;
  21.  
  22.         }
  23.     }
  24. }
  25.  
  26. void insertion1_sort(int tab[], int n) //insertion srt starts at 2_nd element
  27. {
  28.    int i, key, j;
  29.    for (i = 1; i <= n - 1; i++)
  30.    {
  31.        key = i;
  32.  
  33.        while (key >= 0 && tab[key-1] > tab[key])
  34.        {
  35.            j= tab[key];
  36.            tab[key] = tab[key - 1];
  37.            tab[key - 1] = j;
  38.            key --;
  39.        }
  40.  
  41.    }
  42. }
  43.  
  44. void selection_sort (int tab[], int n)
  45. {
  46.     int k ,j , minimum_position, swap;
  47.     for (k = 0; k < (n - 1); k++)
  48.     {
  49.         minimum_position = k;
  50.         for(j = k + 1; j < n; j++)
  51.         {
  52.             if(tab[j]< tab[minimum_position])
  53.             minimum_position = j;
  54.         }
  55.         //swap(tab[k], tab[minimum_position]);
  56.         swap = tab[k];
  57.         tab[k]= tab[minimum_position];
  58.         tab[minimum_position]= swap;
  59.     }
  60. }
  61.  
  62.  
  63.  
  64. //-----------------------------------------------SORTS-------------------------------------------------------------
  65.  
  66. void insertion_sort(int tab[], int n) //insertion srt starts at 2_nd element
  67. {
  68.     int i, key, j;
  69.     for (i = 1; i <= n - 1; i++) {
  70.         key = i;
  71.  
  72.         while (key >= 0 && tab[key - 1] > tab[key]) {
  73.             j = tab[key];
  74.             tab[key] = tab[key - 1];
  75.             tab[key - 1] = j;
  76.             key--;
  77.         }
  78.  
  79.     }
  80. }
  81.  
  82. void merge(int tab[], int l, int m, int r)
  83. {
  84.     int i, j, k;
  85.     int n1 = m - l + 1;
  86.     int n2 = r - m;
  87.     //create temp arrays
  88.     int L[n1], R[n2];
  89.     //put copy data to arrays L & R
  90.     for (i = 0; i < n1; i++) {
  91.         L[i] = tab[l + i];
  92.     }
  93.     for (j = 0; j < n2; j++) {
  94.         R[j] = tab[m + 1 + j];
  95.     }
  96.     i = 0;
  97.     j = 0;
  98.     k = l;
  99.     while (i < n1 && j < n2) {
  100.         if (L[i] <= R[j]) {
  101.             tab[k] = L[i];
  102.             i++;
  103.         } else {
  104.             tab[k] = R[j];
  105.             j++;
  106.         }
  107.         k++;
  108.     }
  109.     //copy the remaining elements of L[]
  110.     while (i < n1) {
  111.         tab[k] = L[i];
  112.         i++;
  113.         k++;
  114.     }
  115.     //copy the remaining elements of R[]
  116.     while (j < n2) {
  117.         tab[k] = R[j];
  118.         j++;
  119.         k++;
  120.     }
  121. }
  122.  
  123. //bottom- up merge sort = iterative merge sort
  124. void merge_sort(int tab[], int l, int r)
  125. {
  126.     if (l < r) {
  127.         int m = (l + r) / 2;
  128.         merge_sort(tab, l, m);
  129.         merge_sort(tab, m + 1, r);
  130.         merge(tab, l, m, r);
  131.     }
  132. }
  133. //tiled bottom-up merge sort = merge + insertion
  134.  
  135. void tiled_bottom_up_merge_sort(int tab[], int l, int r, int threshold)
  136. {
  137.  
  138.  
  139.     if (l < r) {
  140.         if ((r - l) <= threshold) {
  141.             insertion_sort(tab, threshold);
  142.         } else {
  143.             int m = (l + r) / 2;
  144.             merge_sort(tab, l, m);
  145.             merge_sort(tab, m + 1, r);
  146.             merge(tab, l, m, r);
  147.         }
  148.     }
  149. }
  150.  
  151. int compare(const void *a, const void *b)
  152. {
  153.     return (*(int *) a - *(int *) b);
  154. }
  155.  
  156. //---------------------------------printing the array-------------------------------------------------------------
  157.  
  158. void print_tab(int tab[], int n) {
  159.     int i;
  160.     for (i = 0; i < n; i++)
  161.         printf("%d%s", tab[i], "; ");
  162.     printf("\n\n");
  163. }
  164.  
  165. //------------------------------------------------------------------------time---------------------------------------------------------------------------
  166.  
  167. void time_Check(float Start, float Stop) {
  168.     float Time;
  169.     Time = (Stop - Start) / CLOCKS_PER_SEC;
  170.     printf("Sorting time:\n %f  s ", Time);
  171.     printf("\n\n");
  172. }
  173. //----------------------------------------------------------------------generate numbers------------------------------------------------------------------
  174.  
  175. void numbers_generate(int tab[], int n) {
  176.     int i;
  177.     srand(time(NULL)); //randomize speed
  178.     for (i = 0; i < n; i++) {
  179.         tab[i] = rand() % n;
  180.     }
  181. }
  182.  
  183. //---------------------------------------------------------------------main function---------------------------------------------------------------------------
  184.  
  185. int main() {
  186.     int numbers[1000];
  187.     float start;
  188.     float stop;
  189.     int n;
  190.     n = (sizeof(numbers)) / (sizeof(int)); //find the size of array
  191.  
  192.     cout << "MERGE SORT" << endl << endl;
  193.     numbers_generate(numbers, n);
  194.     print_tab(numbers, n);
  195.     start = clock();
  196.     merge_sort(numbers, 0, n - 1);
  197.     stop = clock();
  198.     print_tab(numbers, n);
  199.     time_Check(start, stop);
  200.  
  201.  
  202.     cout << "TILED BOTTOM UP MARGE SORT" << endl << endl;
  203.     numbers_generate(numbers, n);
  204.     print_tab(numbers, n);
  205.     start = clock();
  206.     tiled_bottom_up_merge_sort(numbers, 0, n - 1, n / 10);
  207.     stop = clock();
  208.     print_tab(numbers, n);
  209.     time_Check(start, stop);
  210.  
  211.  
  212.     cout << "QUICK SORT" << endl << endl;
  213.     numbers_generate(numbers, n);
  214.     print_tab(numbers, n);
  215.     start = clock();
  216.     qsort(numbers, n, sizeof(int), compare);
  217.     stop = clock();
  218.     print_tab(numbers, n);
  219.     time_Check(start, stop);
  220.  
  221.     //--------------------------------------------------from lab 1------------------------------------------------------------------------
  222.     cout <<"--------------BUBBLE SORT------------"<< endl << endl;
  223.     numbers_generate(numbers, n);
  224.     start = clock(); //start measuring time
  225.     bubble_sort(numbers, n); //apply bubble sort
  226.     stop = clock();// stop measuring time
  227.    time_Check(start, stop); //display measured time
  228.  
  229. cout << endl <<"--------------INSERTION SORT------------"<< endl << endl;
  230.     numbers_generate(numbers, n);
  231.     start = clock();
  232.     insertion1_sort(numbers, n);
  233.     stop = clock();
  234.     time_Check(start, stop);
  235.  
  236. cout << endl<<"--------------SELECTION SORT------------"<< endl << endl;
  237.     numbers_generate(numbers, n);
  238.     start = clock();
  239.     selection_sort(numbers, n); //apply selection sort
  240.     stop = clock();
  241.     time_Check(start, stop);
  242. //----------------------------------------------------n=20^22 for tiled bottom-up merge sort-------------------------------------------------------------------
  243.     int numbers1[16384];
  244.     cout << "TILED BOTTOM UP MARGE SORT for n = 20^22 " << endl << endl;
  245.     numbers_generate(numbers1, n);
  246.     print_tab(numbers1, n);
  247.     start = clock();
  248.     tiled_bottom_up_merge_sort(numbers1, 0, n - 1, (20^22) / 10);
  249.     stop = clock();
  250.     print_tab(numbers1, n);
  251.     time_Check(start, stop);
  252.       return 0;
  253. }
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