SHARE
TWEET

LAB 1

Mary_99 Jan 25th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5.  
  6. //-----------------------------------------------------------------------------------sorts functions------------------------------------------------------------------------------------
  7. void bubble_sort( int tab[], int n)
  8. {
  9.     int step;
  10.     int temp;
  11.     int i;
  12.     for( step = 0; step < n - 1; ++ step)
  13.     for(i = 0; i < n - step - 1;++i)
  14.     {
  15.         if(tab[i] > tab[i+1])
  16.         {
  17.             temp = tab[i];
  18.             tab[i] = tab[i+1];
  19.             tab[i+1] =  temp;
  20.  
  21.         }
  22.     }
  23. }
  24. void re_bubble_sort( int tab[], int n)
  25. {
  26.     int step;
  27.     int temp;
  28.     int i;
  29.     for( step = 0; step < n - 1; ++step)
  30.     for(i = 0; i < n - step - 1; ++i)
  31.     {
  32.         if(tab[i]<tab[i+1])
  33.         {
  34.             temp = tab[i];
  35.             tab[i]=tab[i+1];
  36.             tab[i+1]= temp;
  37.  
  38.         }
  39.     }
  40. }
  41.  
  42.  
  43. void insertion_sort(int tab[], int n) //insertion srt starts at 2_nd element
  44. {
  45.    int i, key, j;
  46.    for (i = 1; i <= n - 1; i++)
  47.    {
  48.        key = i;
  49.  
  50.        while (key >= 0 && tab[key-1] > tab[key])
  51.        {
  52.            j= tab[key];
  53.            tab[key] = tab[key - 1];
  54.            tab[key - 1] = j;
  55.            key --;
  56.        }
  57.  
  58.    }
  59. }
  60.  
  61.  
  62. void re_insertion_sort( int tab[], int n)
  63. {
  64.     int i, key, j;
  65.    for (i = 1; i <= n - 1; i++)
  66.    {
  67.        key = i;
  68.  
  69.        while (key >= 0 && tab[key-1] < tab[key])
  70.        {
  71.            j= tab[key];
  72.            tab[key] = tab[key - 1];
  73.            tab[key - 1] = j;
  74.            key --;
  75.        }
  76.  
  77.    }
  78.  
  79.  
  80. }
  81.  
  82. void selection_sort (int tab[], int n)
  83. {
  84.     int k ,j , minimum_position, swap;
  85.     for (k = 0; k < (n - 1); k++)
  86.     {
  87.         minimum_position = k;
  88.         for(j = k + 1; j < n; j++)
  89.         {
  90.             if(tab[j]< tab[minimum_position])
  91.             minimum_position = j;
  92.         }
  93.         //swap(tab[k], tab[minimum_position]);
  94.         swap = tab[k];
  95.         tab[k]= tab[minimum_position];
  96.         tab[minimum_position]= swap;
  97.     }
  98. }
  99.  
  100. void re_selection_sort (int tab[], int n)
  101. {
  102.     int k ,j , minimum_position, swap;
  103.     for (k = 0; k < n; k++)
  104.     {
  105.         minimum_position = k;
  106.         for(j = k + 1; j < n; j++)
  107.         {
  108.             if(tab[j]> tab[minimum_position])
  109.             minimum_position = j;
  110.         }
  111.         //swap(tab[k], tab[minimum_position]);
  112.         swap = tab[k];
  113.         tab[k]= tab[minimum_position];
  114.         tab[minimum_position]= swap;
  115.     }
  116. }
  117.  
  118. //-----------------------------------------------------------------------printing the array-------------------------------------------------------------
  119.  
  120. void print_tab(int tab[], int n)
  121. {
  122.    int i;
  123.    for (i = 0; i < n; i++)
  124.        printf("%d", tab[i]);
  125.    printf("\n");
  126. }
  127.  
  128. //------------------------------------------------------------------------time---------------------------------------------------------------------------
  129.  
  130.  void time_Check(float Start, float Stop )
  131. {
  132.     float Time;
  133.     Time = (Stop-Start) /  CLOCKS_PER_SEC;
  134.     printf("Sorting time:\n %f  s ", Time);
  135. }
  136.  //----------------------------------------------------------------------generate numbers------------------------------------------------------------------
  137.  
  138. void numbers_generate(int tab[], int n)
  139. {
  140.     int i ;
  141.     srand(time(NULL)); //randomize speed
  142.     for(i = 0; i < n; i++)
  143.     {
  144.         tab[i] = rand()%n;
  145.     }
  146. }
  147.  
  148. //------------------------------------------------------------------------swap function--------------------------------------------------------------------
  149.  
  150. void swap(int *xp, int *yp)
  151. {
  152.     int temp = *xp;
  153.     *xp = *yp;
  154.     *yp = temp;
  155. }
  156.  
  157.  
  158.  
  159. //----------------------------------------------------------------------main function------------------------------------------------------------------------
  160.  
  161.  int main ()
  162. {
  163.     int numbers[1024];
  164.     float start;
  165.     float stop;
  166.     int n;
  167.     n = (sizeof(numbers))/(sizeof(int)); //find the size of array
  168.  
  169.     printf("BUBBLE SORT\n");
  170.     numbers_generate(numbers, n);
  171.     start = clock();
  172.     bubble_sort(numbers, n);
  173.     stop = clock();
  174.     time_Check(start, stop);
  175.     printf("\n\n");
  176.  
  177.     printf("INSERTION SORT\n");
  178.     numbers_generate(numbers, n);
  179.     start = clock();
  180.     insertion_sort(numbers, n);
  181.     stop = clock();
  182.     time_Check(start, stop);
  183.     printf("\n\n");
  184.  
  185.     printf("SELECTION SORT\n");
  186.     numbers_generate(numbers, n);
  187.     start = clock();
  188.     selection_sort(numbers, n);
  189.     stop = clock();
  190.     time_Check(start, stop);
  191.     printf("\n\n");
  192.  
  193.     printf("RE-BUBBLE SORT\n");
  194.     numbers_generate(numbers, n);
  195.     start = clock();
  196.     re_bubble_sort(numbers, n);
  197.     stop = clock();
  198.     time_Check(start, stop);
  199.     printf("\n\n");
  200.  
  201.     printf("RE-INSERTION SORT\n");
  202.     numbers_generate(numbers, n);
  203.     start = clock();
  204.     re_insertion_sort(numbers, n);
  205.     stop = clock();
  206.     time_Check(start, stop);
  207.     printf("\n\n");
  208.  
  209.     printf("RE-SELECTION SORT\n");
  210.     numbers_generate(numbers, n);
  211.     start = clock();
  212.     re_selection_sort(numbers, n);
  213.     stop = clock();
  214.     time_Check(start, stop);
  215.     printf("\n\n");
  216.  
  217.  
  218.     //---------------------------------------------------------Count the number of swaps  for bubble sort, n = 2^16--------------------------------
  219.  
  220.     int Numbers[65536];//2^16
  221.     int k;
  222.     int i ;
  223.     int j;
  224.     k = (sizeof(Numbers) / sizeof(int));
  225.     numbers_generate(Numbers, k);
  226.     bool swapped = false;
  227.     int count_swap = 0;
  228.     int no_swap = 0;
  229.  
  230.     do
  231.     {
  232.             for( i = 0; i < k-1; i++)
  233.         {
  234.             for( j = 0; j < k-i-1; j++)
  235.             {
  236.                 if(Numbers[j] > Numbers[j+1])
  237.                 {
  238.                     swap(&Numbers[j], &Numbers[j+1]);
  239.                     swapped = true;
  240.                     count_swap++;
  241.                 }
  242.                 else
  243.                 {
  244.                     swapped = false;
  245.                     no_swap++;
  246.                 }
  247.             }
  248.         }
  249.     }while(swapped == true);
  250.     printf("Bubble sort \n");
  251.     printf("\n\n");
  252.     printf( "Number of swaps: %d" , count_swap );
  253.     printf("\n\n");
  254.     printf("Number of no swaps: %d" , no_swap );
  255.     printf("\n\n");
  256.       return 0;
  257. }
  258. //the best case scenario is when all array is already sorted
  259. //the worst case scenario is then the array is reverse sorted
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