NonrecursiveHEADmaster

6 files changed, 345 insertions, 181 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..8274df8
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+/cmake-*
+/build
+/.idea
+*.swp
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 9043b1c..a9e1c98 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,7 +1,19 @@
 cmake_minimum_required(VERSION 3.6)
 project(qsort)
 
+if(NOT CMAKE_BUILD_TYPE)
+    set(CMAKE_BUILD_TYPE "Release" CACHE STRING
+            "Choose the type of build, options are: Debug Release RelWithDebInfo MinSizeRel." FORCE)
+endif(NOT CMAKE_BUILD_TYPE)
+
 set(CMAKE_CXX_STANDARD 11)
 
-set(SOURCE_FILES main.cpp)
-add_executable(qsort ${SOURCE_FILES})
\ No newline at end of file
+set(SOURCE_FILES main.cpp mqsort.cpp)
+add_executable(qsort ${SOURCE_FILES})
+
+add_custom_target(test-all
+        COMMAND ${CMAKE_BINARY_DIR}/qsort i 100000 100
+        COMMAND ${CMAKE_BINARY_DIR}/qsort l 100000 100
+        COMMAND ${CMAKE_BINARY_DIR}/qsort f 100000 100
+        COMMAND ${CMAKE_BINARY_DIR}/qsort d 100000 100
+        DEPENDS qsort)
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..75bc509
--- /dev/null
+++ b/README.md
@@ -0,0 +1,68 @@
+# QUICK_SORT
+
+## HowTos
+
+***The build system is using CMake***
+
+### Setup CMake
+
+1. `cd <SOURCE_DIR>`
+2. `mkdir build`
+3. `cd build`
+4. `cmake ..`
+
+### Build
+
+After CMake is setup, type:
+
+* `make`
+
+### Test all
+
+* `make test-all`
+
+Example output: i5-7200U, Archlinux, linux 4.9.2, gcc 6.3.1
+~~~
+100000 Int for 100 Iterations
+Average time taken for me  (s): 0.00987307
+Average time taken for std (s): 0.0111078
+Speedup over std : 1.12506
+Median time taken for me  (s): 0.0098605
+Median time taken for std (s): 0.0110835
+Speedup over std : 1.12403
+100000 Long for 100 Iterations
+Average time taken for me  (s): 0.0100124
+Average time taken for std (s): 0.0111518
+Speedup over std : 1.1138
+Median time taken for me  (s): 0.009971
+Median time taken for std (s): 0.011114
+Speedup over std : 1.11463
+100000 Float for 100 Iterations
+Average time taken for me  (s): 0.0107144
+Average time taken for std (s): 0.0111841
+Speedup over std : 1.04384
+Median time taken for me  (s): 0.0106765
+Median time taken for std (s): 0.011099
+Speedup over std : 1.03957
+100000 Double for 100 Iterations
+Average time taken for me  (s): 0.0108789
+Average time taken for std (s): 0.0115306
+Speedup over std : 1.05991
+Median time taken for me  (s): 0.010835
+Median time taken for std (s): 0.0114525
+Speedup over std : 1.05699
+~~~
+
+### Individual tests
+
+See `./qsort` and follow the instructions, for examples:
+
+* Sort *10000* **int** items for *10000* iterations:
+~~~
+./qsort i 10000 10000
+~~~
+* Sort *10000* **float** items for *10000* iterations:
+~~~
+./qsort f 10000 10000
+~~~
+
diff --git a/main.cpp b/main.cpp
index 2546a8e..08a4368 100644
--- a/main.cpp
+++ b/main.cpp
@@ -1,126 +1,14 @@
 #include <iostream>
-#include <cstdlib>
 #include <random>
 #include <cstring>
 #include <ctime>
+#include <algorithm>
+#include "mqsort.h"
 
 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;
+int compr(const void *a, const void *b) {
+  T aa = *(T *) a;
+  T bb = *(T *) b;
   if (aa > bb)
     return 1;
   if (aa < bb)
@@ -129,118 +17,157 @@ int compr(const void * a, const void * b){
 }
 
 template<typename T>
-void* genInt(size_t num) {
+void genInt(void *base, 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)
+  std::uniform_int_distribution<T> unifrom_dist(0, (T) 1 << (sizeof(T) * 8 - 2));
+  T *res = (T *) base;
+  for (size_t i = 0; i < num; ++i)
     res[i] = unifrom_dist(e);
-  return res;
 }
 
 template<typename T>
-void* genFloat(size_t num) {
+void genFloat(void *base, 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)
+  T *res = (T *) base;
+  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);
+void gen(void *base, size_t num) {
+  genInt<T>(base, num);
 }
 
-template <>
-void* gen<float>(size_t num) {
-  return genFloat<float>(num);
+template<>
+void gen<float>(void *base, size_t num) {
+  genFloat<float>(base, num);
 }
 
-template <>
-void* gen<double>(size_t num) {
-  return genFloat<double>(num);
+template<>
+void gen<double>(void *base, size_t num) {
+  genFloat<double>(base, num);
 }
 
-int compeq(uint32_t *a,uint32_t *b, size_t size) {
-  for (size_t i = 0; i< size; ++i)
+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) {
+void runAndTest(size_t num, size_t it) {
   clock_t tst;
   clock_t tmd;
   clock_t ted;
+  std::vector<clock_t> mine, stnd;
   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);
+  void *base = malloc(num * size);
+  void *base2 = malloc(num * size);
+  for (size_t t = 0; t < it; ++t) {
+    gen<T>(base, num);
+    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;
+      return;
+    }
+    mine.push_back(tmd - tst);
+    stnd.push_back(ted - tmd);
   }
-  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;
+  free(base);
+  free(base2);
+  std::sort(mine.begin(), mine.end());
+  std::sort(stnd.begin(), stnd.end());
+  double m = 0, s = 0;
+  for (auto itt = mine.begin(); itt < mine.end(); ++itt)
+    m += *itt;
+  for (auto itt = stnd.begin(); itt < stnd.end(); ++itt)
+    s += *itt;
+  std::cout << "Average time taken for me  (s): " << m / CLOCKS_PER_SEC / it << std::endl;
+  std::cout << "Average time taken for std (s): " << s / CLOCKS_PER_SEC / it << std::endl;
+  std::cout << "Speedup over std : " << s / m << std::endl;
+  if (it & 1) {
+    m = mine[it >> 1];
+    s = stnd[it >> 1];
+  } else {
+    m = mine[it >> 1];
+    m += mine[(it >> 1) - 1];
+    m /= 2;
+    s = stnd[it >> 1];
+    s += stnd[(it >> 1) - 1];
+    s /= 2;
+  }
+  std::cout << "Median time taken for me  (s): " << m / CLOCKS_PER_SEC << std::endl;
+  std::cout << "Median time taken for std (s): " << s / CLOCKS_PER_SEC << std::endl;
+  std::cout << "Speedup over std : " << s / m << 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) {
+  std::cout << "Usage: <this> [TYPE] [LENGTH]" << std::endl;
+  std::cout << "    [TYPE]" << std::endl;
+  std::cout << "          c : char(int8)" << std::endl;
+  std::cout << "          s : short(int16)" << 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;
+  std::cout << "    [ITERATIONS]" << std::endl;
+  std::cout << "          An int specify the number of iterations of test" << std::endl;
+}
+
+int main(int argc, char **argv) {
+  if (argc < 4) {
     usage();
     return -1;
   }
   size_t num;
+  size_t it;
   try {
-    num = (size_t)std::stoi(argv[2]);
+    num = (size_t) std::stoi(argv[2]);
+    if (num > 10000000)
+      std::cout << "The [LENGTH] seems to be too large" << std::endl;
+    it = (size_t) std::stoi(argv[3]);
+    if (it > 10000000)
+      std::cout << "The [ITERATIONS] seems to be too large" << std::endl;
   } catch (std::exception &e) {
     std::cout << e.what() << std::endl;
     usage();
     return -1;
   }
-  switch(argv[1][0]) {
+  switch (argv[1][0]) {
+    case 'c':
+      std::cout<<num<<" Char for "<<it<<" Iterations"<<std::endl;
+      runAndTest<int8_t>(num, it);
+      break;
+    case 's':
+      std::cout<<num<<" Short for "<<it<<" Iterations"<<std::endl;
+      runAndTest<int16_t>(num, it);
+      break;
     case 'i':
-      runAndTest<int>(num);
+      std::cout<<num<<" Int for "<<it<<" Iterations"<<std::endl;
+      runAndTest<int>(num, it);
       break;
     case 'l':
-      runAndTest<long>(num);
+      std::cout<<num<<" Long for "<<it<<" Iterations"<<std::endl;
+      runAndTest<long>(num, it);
       break;
     case 'f':
-      runAndTest<float>(num);
+      std::cout<<num<<" Float for "<<it<<" Iterations"<<std::endl;
+      runAndTest<float>(num, it);
       break;
     case 'd':
-      runAndTest<double>(num);
+      std::cout<<num<<" Double for "<<it<<" Iterations"<<std::endl;
+      runAndTest<double>(num, it);
       break;
     default:
       usage();
diff --git a/mqsort.cpp b/mqsort.cpp
new file mode 100644
index 0000000..5d54892
--- /dev/null
+++ b/mqsort.cpp
@@ -0,0 +1,140 @@
+//
+// Created by joe on 1/14/17.
+//
+
+#include "mqsort.h"
+
+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
+#define MAXS 100
+#define PUSH(x, y) {stack[top][0] = x; stack[top][1] = y; ++top; }
+#define POP(x, y) {--top; x = stack[top][0]; y = stack[top][1];}
+#define EMPTY (top == 0)
+
+template<typename T>
+void secret1(T *l, T *r, int (*compar)(const void *, const void *)) {
+  int top = 0;
+  T *stack[MAXS][2];
+  while (true) {
+    if (l + INS > r) {
+      insert(l, r, compar);
+      if (EMPTY)
+        break;
+      POP(l, r);
+      continue;
+    }
+    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;
+    if (j > l) {
+      if (r > i) {
+        if (j - l > r - i) {
+          PUSH(l, j);
+          l = i;
+        } else {
+          PUSH(i, r);
+          r = j;
+        }
+      } else r = j;
+    } else if (r > i) {
+      l = i;
+    } else if (EMPTY)
+      break;
+    else POP(l, r);
+  }
+}
+
+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);
+  }
+}
diff --git a/mqsort.h b/mqsort.h
new file mode 100644
index 0000000..ef9d3be
--- /dev/null
+++ b/mqsort.h
@@ -0,0 +1,13 @@
+//
+// Created by joe on 1/14/17.
+//
+
+#ifndef QSORT_MQSORT_H
+#define QSORT_MQSORT_H
+
+#include <cstdint>
+#include <cstdlib>
+
+void mqsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));
+
+#endif //QSORT_QSORT_H