Initial Commit

2 files changed, 257 insertions, 0 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..9043b1c
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.6)
+project(qsort)
+
+set(CMAKE_CXX_STANDARD 11)
+
+set(SOURCE_FILES main.cpp)
+add_executable(qsort ${SOURCE_FILES})
\ No newline at end of file
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..2546a8e
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,250 @@
+#include <iostream>
+#include <cstdlib>
+#include <random>
+#include <cstring>
+#include <ctime>
+
+template<typename T>
+inline void swap(T &a, T &b) {
+  T t = a;
+  a = b;
+  b = t;
+}
+
+template<typename T>
+inline void insert(T *l, T *r, int (*compar)(const void*, const void*)) {
+  T* s = l;
+  while (s<r) {
+    T* k = s+1;
+    while (k > l && compar(k,k-1) < 0) {
+      swap(*k, *(k-1));
+      --k;
+    }
+    ++s;
+  }
+}
+
+#define INS 12
+
+template<typename T>
+void secret1(T *l, T *r, int (*compar)(const void*, const void*)) {
+  T *j = r;
+  T *i = l+1;
+  {
+    int a = compar(l, l+1), b= compar(l,l+2), c = compar(l+1,l+2);
+    if (a > 0) {
+      if (b > 0)
+      if (c<0) swap(*l,l[2]);
+        else swap(*l,l[1]);
+    } else if (a < 0) {
+      if (b < 0)
+        if (c<0) swap(*l,l[1]);
+        else swap(*l,l[2]);
+    }
+  }
+  while (i <= j) {
+    int a = compar(l,i);
+    if (a <= 0) {
+      int b = 0;
+      while (j > l && (b = compar(l,j)) < 0)
+        --j;
+      if (j > i) {
+        if (a != b) {
+          swap(*j, *i);
+          --j;
+        } else {
+          --i; --j;
+        }
+      } else break;
+    } else {
+      ++i;
+    }
+  }
+  swap(*l, *j);
+  --j;
+  //std::cout<< j-l <<" " << r-i << std::endl;
+  if (l+INS < j)
+    secret1(l,j, compar);
+  else
+    insert(l,j,compar);
+  if (i+INS < r)
+    secret1(i,r, compar);
+  else
+    insert(i,r,compar);
+}
+
+inline void swapsize(char *a,char *b, size_t size) {
+  for (int cnt = 0; cnt < size; ++cnt)
+    swap<char>(a[cnt],b[cnt]);
+}
+
+void secret(char *l, char *r, size_t size,int (*compar)(const void*, const void*)) {
+  char *j = r;
+  char *i = l+size;
+  while (i <= j) {
+    if (compar(l,i) < 0) {
+      swapsize(j, i, size);
+      j -= size;
+    } else {
+      i += size;
+    }
+  }
+  swapsize(l, j, size);
+  j -= size;
+  if (l < j)
+    secret1(l, j, compar);
+  if (i < r)
+    secret1(i, r, compar);
+
+}
+
+void mqsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*)) {
+  switch (size) {
+    case 1:
+      secret1((uint8_t*)base, (uint8_t*)base+(num-1), compar);
+      break;
+    case 2:
+      secret1((uint16_t *)base, (uint16_t *)base+(num-1), compar);
+      break;
+    case 4:
+      secret1((uint32_t *)base, (uint32_t*)base+(num-1), compar);
+      break;
+    case 8:
+      secret1((uint64_t *)base, (uint64_t *)base+(num-1), compar);
+      break;
+    default:
+      secret((char*)base, (char*)base+(num-1)*size, size, compar);
+  }
+}
+
+template<typename T>
+int compr(const void * a, const void * b){
+  T aa = *(T*)a;
+  T bb = *(T*)b;
+  if (aa > bb)
+    return 1;
+  if (aa < bb)
+    return -1;
+  return 0;
+}
+
+template<typename T>
+void* genInt(size_t num) {
+  std::random_device r;
+  std::mt19937_64 e(r());
+  std::uniform_int_distribution<T> unifrom_dist(0, 1 << (sizeof(T)*8 -2));
+  T * res = (T*)malloc(num * sizeof(T));
+  for (size_t i = 0; i<num; ++i)
+    res[i] = unifrom_dist(e);
+  return res;
+}
+
+template<typename T>
+void* genFloat(size_t num) {
+  std::random_device r;
+  std::mt19937_64 e(r());
+  std::uniform_real_distribution<T> unifrom_dist(0, 1);
+  T * res = (T*)malloc(num * sizeof(T));
+  for (size_t i = 0; i<num; ++i)
+    res[i] = unifrom_dist(e);
+  return res;
+}
+
+template<typename T>
+void* gen(size_t num) {
+  return genInt<T>(num);
+}
+
+template <>
+void* gen<float>(size_t num) {
+  return genFloat<float>(num);
+}
+
+template <>
+void* gen<double>(size_t num) {
+  return genFloat<double>(num);
+}
+
+int compeq(uint32_t *a,uint32_t *b, size_t size) {
+  for (size_t i = 0; i< size; ++i)
+    if (a[i] != b[i])
+      return 1;
+  return 0;
+}
+
+template<typename T>
+void print(void *v, size_t num) {
+  T * k = (T*) v;
+  for (int i = 0; i<num; ++i)
+    std::cout<< k[i] << " ";
+  std::cout<<std::endl;
+}
+
+template<typename T>
+void runAndTest(size_t num) {
+  clock_t tst;
+  clock_t tmd;
+  clock_t ted;
+  size_t size = sizeof(T);
+  void *base = gen<T>(num);
+  void *base2 = malloc(num*size);
+  memcpy(base2,base,num*size);
+  tst = clock();
+  mqsort(base,num,size,compr<T>);
+  tmd = clock();
+  qsort(base2,num,size,compr<T>);
+  ted = clock();
+  if (compeq((uint32_t*)base,(uint32_t*)base2,num*size/4)) {
+    std::cout << "Not equal" << std::endl;
+    print<T>(base, num);
+    print<T>(base2,num);
+  }
+  else
+    std::cout<<"Equal"<<std::endl;
+  std::cout<<"Time taken for me  : " << float(tmd - tst) / CLOCKS_PER_SEC<<std::endl;
+  std::cout<<"Time taken for std : " << float(ted - tmd) / CLOCKS_PER_SEC<<std::endl;
+}
+
+void usage() {
+  std::cout << "Usage: <this> [TYPE] [LENGTH]" <<std::endl;
+  std::cout << "    [TYPE]" <<std::endl;
+  std::cout << "          i : int" <<std::endl;
+  std::cout << "          l : long" <<std::endl;
+  std::cout << "          f : float" <<std::endl;
+  std::cout << "          d : double" <<std::endl;
+  std::cout << "    [LENGTH]" <<std::endl;
+  std::cout << "          An int specify the number of elements in the list to be sorted" <<std::endl;
+}
+
+int main(int argc,char** argv) {
+  if (argc < 3) {
+    usage();
+    return -1;
+  }
+  size_t num;
+  try {
+    num = (size_t)std::stoi(argv[2]);
+  } catch (std::exception &e) {
+    std::cout << e.what() << std::endl;
+    usage();
+    return -1;
+  }
+  switch(argv[1][0]) {
+    case 'i':
+      runAndTest<int>(num);
+      break;
+    case 'l':
+      runAndTest<long>(num);
+      break;
+    case 'f':
+      runAndTest<float>(num);
+      break;
+    case 'd':
+      runAndTest<double>(num);
+      break;
+    default:
+      usage();
+      return -1;
+  }
+  return 0;
+}
\ No newline at end of file