SHARE
TWEET

proba 2

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