daily pastebin goal
39%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Generic shell sort algorithm.*/
  2. /*Works on all built-in data types(int, char, double, float).*/
  3. /*Compilation: g++ shell_sort.cpp -std=c++11 -o shellsort --> ./shellsort */
  4. #include <iostream>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. /*Helper function to swap elements.*/
  9. template<class T> void newswap(T &a, T &b) {
  10.   T temp = a;
  11.   a = b;
  12.   b = temp;
  13. }
  14.  
  15. /*Helper function to print arrays.*/
  16. template<class T> void print(vector<T> &v) {
  17.   int size = v.size();
  18.   cout << "Array:";
  19.   for(int i=0; i<size; i++)
  20.     cout << " " << v[i];
  21.   cout << endl;
  22. }
  23.  
  24. /*Shell sort algorithm average case complexity: n^3/2.*/
  25. template<class T> void shell_sort(vector<T> &v) {
  26.   int size = v.size();
  27.   int gap = 1;
  28.   while(gap <= size / 2)
  29.     gap = 3 * gap + 1;
  30.   while(gap >= 1) {
  31.     for(int i=gap; i<size; i++)
  32.       for(int j=i; j>=0; j-=gap)
  33.         if(v[j] < v[j-gap])
  34.           newswap(v[j], v[j-gap]);
  35.     gap /= 3;
  36.   }
  37. }
  38.  
  39. /*Main function to test the algorithm.*/
  40. int main(int argc, char const *argv[]) {
  41.     vector<char> v_char {'a','s','b','f', 'c'};
  42.     vector<int> v_int {19,5,2,6,3,5};
  43.     shell_sort(v_char);
  44.     shell_sort(v_int);
  45.     print(v_char);
  46.     print(v_int);
  47.     return 0;
  48. }
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