/*Generic shell sort algorithm.*/
/*Works on all built-in data types(int, char, double, float).*/
/*Compilation: g++ shell_sort.cpp -std=c++11 -o shellsort --> ./shellsort */
#include <iostream>
#include <vector>
using namespace std;

/*Helper function to swap elements.*/
template<class T> void newswap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

/*Helper function to print arrays.*/
template<class T> void print(vector<T> &v) {
  int size = v.size();
  cout << "Array:";
  for(int i=0; i<size; i++)
    cout << " " << v[i];
  cout << endl;
}

/*Shell sort algorithm average case complexity: n^3/2.*/
template<class T> void shell_sort(vector<T> &v) {
  int size = v.size();
  int gap = 1;
  while(gap <= size / 2)
    gap = 3 * gap + 1;
  while(gap >= 1) {
    for(int i=gap; i<size; i++)
      for(int j=i; j>=0; j-=gap)
        if(v[j] < v[j-gap])
          newswap(v[j], v[j-gap]);
    gap /= 3;
  }
}

/*Main function to test the algorithm.*/
int main(int argc, char const *argv[]) {
    vector<char> v_char {'a','s','b','f', 'c'};
    vector<int> v_int {19,5,2,6,3,5};
    shell_sort(v_char);
    shell_sort(v_int);
    print(v_char);
    print(v_int);
    return 0;
}