BVB Source Codes

Algorithm-Implementations Show quick_sort.cpp Source code

Return Download Algorithm-Implementations: download quick_sort.cpp Source code - Download Algorithm-Implementations Source code - Type:.cpp
  1. /*
  2. Quicksort (partition-exchange sort)
  3. ----------
  4. Advantages:
  5.     - Fast for large data sets
  6. Disadvantages:
  7.     - Not stable
  8. Time complexity:
  9.     - worst:   O(n^2)
  10.     - average: O(n*log(n))
  11.     - best:    O(n*log(n))
  12. Space complexity:
  13.     - Ideally O(log n)
  14.     - This implementation O(n)
  15. */
  16.  
  17. #include <iostream>
  18. #include <vector>
  19. #include <stdlib.h>
  20. #include <time.h>
  21.  
  22. using std::cout;
  23. using std::vector;
  24. using std::endl;
  25.  
  26. template<typename T>
  27. void print(vector<T> l) {
  28.     for (int i=0; i < l.size(); i++) {
  29.         cout << l[i] << " ";
  30.     }
  31.     cout << endl;
  32. }
  33.  
  34. template<typename T>
  35. vector<T> extend(vector<T> v, vector<T> v_prime) {
  36.     v.reserve(v.size() + distance(v_prime.begin(), v_prime.end()));
  37.     v.insert(v.end(), v_prime.begin(), v_prime.end());
  38.     return v;
  39. }
  40.  
  41. template<typename T>
  42. vector<T> quicksort(vector<T> array) {
  43.     if (array.size() <= 1) {
  44.         return array;
  45.     }
  46.     int pivot_index = rand() % array.size();
  47.     T pivot = array[pivot_index];
  48.     array.erase(array.begin() + pivot_index);
  49.     vector<T> less;
  50.     vector<T> greater;
  51.     for (int i = 0; i < array.size(); i++) {
  52.         if (array[i] <= pivot) {
  53.             less.push_back(array[i]);
  54.         } else {
  55.             greater.push_back(array[i]);
  56.         }
  57.     }
  58.     less = quicksort(less);
  59.     less.push_back(pivot);
  60.     greater = quicksort(greater);
  61.     vector<T> result = extend(less, greater);
  62.     return result;
  63. }
  64.  
  65. //test cases
  66. int main() {
  67.     srand(time(0));
  68.     vector<int> l = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  69.     cout << "Unsorted list: ";
  70.     print(l);
  71.     l = quicksort(l);
  72.     cout << "Sorted list: ";
  73.     print(l);
  74. }
  75.  
  76.  
  77.  
downloadquick_sort.cpp Source code - Download Algorithm-Implementations Source code
Related Source Codes/Software:
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web ... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react ... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28

 Back to top