Skip to content

Instantly share code, notes, and snippets.

@heatblazer
Last active December 10, 2021 19:14
Show Gist options
  • Save heatblazer/113233b89554da08d8860a8adf43a123 to your computer and use it in GitHub Desktop.
Save heatblazer/113233b89554da08d8860a8adf43a123 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <array>
// this template would tell us the T is not an array like type
// ex. - does not have [n] operator overloaded
// for simplicity - or it's a poorman specialization below
template <typename T>
struct is_arraytype
{
static const bool value = false;
};
//poorman spec for vector<T>
template <typename T>
struct is_arraytype<std::vector<T>>
{
static const bool value = true;
};
//poorman spec for array<T>
template <typename T, size_t S>
struct is_arraytype<std::array<T, S>>
{
static const bool value = true;
};
//a cmp functor
template<typename T>
struct PredCmpT
{
enum CmpFn
{
Lt,
Gt
};
CmpFn m_fn;
explicit PredCmpT(PredCmpT::CmpFn fn) : m_fn{ fn } { }
bool operator()(const T& a, const T& b) {
switch (m_fn)
{
case Lt:
return a < b;
case Gt:
default:
return a > b;
}
}
};
//the actual user of the specialization
template<typename T, typename N>
void ssort(T& arr, PredCmpT<N> cmpfn)
{
//if T is not either std::array or std::vector - don't compile below it.
if (!is_arraytype<T>::value)
return;
int gap, sz;
sz = arr.size();
for (gap = sz / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < sz; i++)
{
for (int j= i - gap; j >=0 && cmpfn(arr[j], arr[j+gap]); j-=gap)
{
std::swap(arr[j], arr[j + gap]);
}
}
}
}
//driver tester program
int main()
{
std::array<int, 20> arr2 = {1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1};
std::vector<int> arr = {2,3,4,55,1,1,23,4,50,0,100,200,5,1000,2111,202020,1,0,0,0,
8,9,10,11,12,5,6,7,8,9,12345,6789,98765,1234,4321,7890,
1919, 2020, 6677, 9988, 1122, 1111, 1212};
ssort(arr2, PredCmpT<int>{PredCmpT<int>::CmpFn::Gt});
for(auto it : arr2) {
std::cout << it << "\r\n";
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment