Advertisement
AdrianMadajewski

Time Complexity quickSort vs bubbleSort

Nov 13th, 2019
214
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. #define true 1
  5. #define false 1
  6.  
  7. typedef int bool_t;
  8.  
  9. void swap(int* a, int* b)
  10. {
  11.     int t = *a;
  12.     *a = *b;
  13.     *b = t;
  14. }
  15.  
  16. int partition (int arr[], int low, int high)
  17. {
  18.     int pivot = arr[high];    
  19.     int i = (low - 1);  
  20.  
  21.     for (int j = low; j <= high- 1; j++)
  22.     {
  23.         if (arr[j] < pivot)
  24.         {
  25.             swap(&arr[++i], &arr[j]);
  26.         }
  27.     }
  28.     swap(&arr[i + 1], &arr[high]);
  29.     return (i + 1);
  30. }
  31.  
  32. void quickSort(int arr[], int low, int high)
  33. {
  34.     if (low < high)
  35.     {
  36.         /* pi is partitioning index, arr[p] is now
  37.            at right place */
  38.         int pi = partition(arr, low, high);
  39.  
  40.         // Separately sort elements before
  41.         // partition and after partition
  42.         quickSort(arr, low, pi - 1);
  43.         quickSort(arr, pi + 1, high);
  44.     }
  45. }
  46.  
  47. /* Function to print an array */
  48. void printArray(int arr[], int size)
  49. {
  50.     int i;
  51.     for (i=0; i < size; i++)
  52.         printf("%d ", arr[i]);
  53.     printf("\n");
  54. }
  55.  
  56. void bubbleSortFast(int arr[], int size) {
  57.     if(arr == NULL || size == 0) {
  58.         return;
  59.     }
  60.    
  61.     bool_t swapped = true;
  62.    
  63.     int i = 0;
  64.     while(i < size - 1 && swapped) {
  65.         swapped = false;
  66.         for(int j = 0; j < size - i - 1; ++j) {
  67.             if(arr[j] > arr[j + 1]) {
  68.                 swap(&arr[j], &arr[j + 1]);
  69.                 swapped = true;
  70.             }
  71.         }
  72.         ++i;
  73.     }
  74. }
  75.  
  76. void bubbleSort(int arr[], int size) {
  77.     for(int i = 0; i < size; ++i) {
  78.         for(int j = 0; j < size - 1; ++j) {
  79.             if(arr[j] > arr[j + 1]) {
  80.                 swap(&arr[j], &arr[j + 1]);
  81.             }
  82.         }
  83.     }
  84. }
  85.  
  86. // Driver program to test above functions
  87. int main(void)
  88. {
  89.     int arr[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
  90.     int n = sizeof(arr) / sizeof(arr[0]);
  91.    
  92.     // TIME #1
  93.     clock_t start;
  94.     clock_t end;
  95.     double time_taken;
  96.    
  97.     start = clock();
  98.     quickSort(arr, 0, n-1);
  99.     end = clock();
  100.     time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
  101.    
  102.     printf("Sorted array (quickSort): ");
  103.     printArray(arr, n);
  104.     printf("Time taken: %f\n", time_taken);
  105.    
  106.     int arr2[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
  107.     int n2 = sizeof(arr) / sizeof(arr[0]);
  108.    
  109.     // TIME #2
  110.     start = clock();
  111.    
  112.     bubbleSortFast(arr2, n2);
  113.    
  114.     end = clock();
  115.     time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
  116.    
  117.     printf("Sorted array (bubbleSortFast): ");
  118.     printArray(arr2, n2);
  119.     printf("Time taken: %f\n", time_taken);
  120.    
  121.     int arr3[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
  122.     int n3 = sizeof(arr) / sizeof(arr[0]);
  123.    
  124.     // TIME #3
  125.     start = clock();
  126.    
  127.     bubbleSort(arr3, n3);
  128.    
  129.     end = clock();
  130.     time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
  131.    
  132.     printf("Sorted array (bubbleSort): ");
  133.     printArray(arr3, n3);
  134.     printf("Time taken: %f\n", time_taken);
  135.    
  136.     return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement