MMBC

Bubble sort vs Quicksort

Mar 16th, 2018
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <chrono>
  4. #include <ratio>
  5. #include <algorithm>
  6. #include <ctime>
  7. #include <cstdlib>
  8.  
  9. namespace sort
  10. {
  11.     void bubble_sort(int* t, size_t n)
  12.     {
  13.         for (unsigned int i = n-1; i >= 1; i--)
  14.             for (unsigned int j = 0; j < i; j++)
  15.                 if (t[j+1] < t[j])
  16.                     std::swap(t[j], t[j+1]);
  17.     }
  18.    
  19.     int partition(int* t, unsigned int s, unsigned int e)
  20.     {
  21.         int pivot = t[s];
  22.         int l = s+1;
  23.         int r = e;
  24.        
  25.         bool done = false;
  26.         while(!done)
  27.         {
  28.             while (l <= r && t[l] <= pivot)
  29.                 l++;
  30.            
  31.             while (t[r] >= pivot && r >= l)
  32.                 r--;
  33.            
  34.             if (r < l)
  35.                 done = true;
  36.             else
  37.                 std::swap(t[l], t[r]);
  38.         }
  39.         std::swap(t[s], t[r]);
  40.        
  41.         return r;
  42.     }
  43.    
  44.     void quicksort(int* t, unsigned int s, unsigned int e)
  45.     {
  46.         if (s < e)
  47.         {
  48.             int p = partition(t, s, e);
  49.             quicksort(t, s, p-1);
  50.             quicksort(t, p+1, e);
  51.         }
  52.     }
  53. }
  54.  
  55. int main(void)
  56. {
  57.     const unsigned int s = 1000;
  58.     int tab[s];
  59.     int stab[s];
  60.    
  61.     srand(time(0));
  62.     for (unsigned int i = 0; i < s; i++)
  63.     {
  64.         tab[i] = rand()%s;
  65.     }
  66.    
  67.     std::chrono::high_resolution_clock::time_point sp;
  68.     std::chrono::high_resolution_clock::time_point ep;
  69.     std::chrono::duration<double, std::milli> d;
  70.    
  71.     std::memcpy(stab, tab, s*sizeof(int));
  72.    
  73.     std::cout << "Bubble sort:" << std::endl;
  74.     sp = std::chrono::high_resolution_clock::now();
  75.     sort::bubble_sort(stab, s);
  76.     ep = std::chrono::high_resolution_clock::now();
  77.     d = ep-sp;
  78.     std::cout << "Time: " << d.count() << "ms" << std::endl << std::endl;
  79.    
  80.     std::memcpy(stab, tab, s*sizeof(int));
  81.    
  82.     std::cout << "Quick sort:" << std::endl;
  83.     sp = std::chrono::high_resolution_clock::now();
  84.     sort::quicksort(stab, 0, s-1);
  85.     ep = std::chrono::high_resolution_clock::now();
  86.     d = ep-sp;
  87.     std::cout << "Time: " << d.count() << "ms" << std::endl << std::endl;
  88.    
  89.     //for (const auto& i : stab) std::cout << i << std::endl;
  90.    
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment