fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iterator>
  5. #include <iomanip>
  6. #include <locale>
  7. #include <stdlib.h>
  8. #include <time.h>
  9.  
  10. #ifdef WINDOWS
  11. #include <Windows.h>
  12. #endif
  13.  
  14. #ifdef _DEBUG
  15. #define DBG(x) (x)
  16. #else
  17. #define DBG(x) ((void *)0)
  18. #endif
  19.  
  20. // Since the math for a heap assumes 1-based indexing, 
  21. // this allows us to use 1-based indexing on an existing
  22. // vector.
  23. template <class T>
  24. class one_based {
  25.     std::vector<T> &data;
  26. public:
  27.     one_based(std::vector<T> &data) : data(data) {}
  28.     T &operator[](size_t index) {
  29.         return data[index-1];
  30.     }
  31.     T operator[](size_t index) const {
  32.         return data[index-1];
  33.     }
  34.     size_t size() { return data.size(); }
  35. };
  36.  
  37. template <class T, class Cmp>
  38. void heapify(std::vector<T> &d, Cmp cmp) {
  39.     one_based<T> data(d);
  40.     for (size_t i=2; i<=data.size(); i++) 
  41.         for (size_t j=i; j>1; j/=2)
  42.             if (cmp(data[j/2], data[j]))
  43.                 std::swap(data[j], data[j/2]);
  44.             else break;
  45. }
  46.  
  47. template <class T>
  48. void heapify(std::vector<T> &d) {
  49.     heapify(d, std::less<T>());
  50. }
  51.  
  52. template <class T, class Cmp>
  53. bool check_heap(std::vector<T> &d, int N, Cmp cmp) {
  54.     one_based<T> data(d);
  55.     for (int i=1; i<N/2; i++)
  56.         if (cmp(data[i], data[i*2]) || cmp(data[i], data[i*2+1])) {
  57.             std::cerr << "\nHeap corrupted\n";
  58.             return false;
  59.         }	
  60.     return true;
  61. }
  62.  
  63. template <class T>
  64. bool check_heap(std::vector<T> &d) {
  65.     return check_heap(d, std::less<T>());
  66. }
  67.  
  68. template <class T, class Cmp>
  69. void sift(std::vector<T> &d, size_t max, Cmp cmp = std::less<T>()) { 
  70.     one_based<T> data(d);
  71.     size_t pos2=2;
  72.  
  73.     for (size_t pos1=1; pos2<max; pos1=pos2, pos2*=2) {
  74.         if (cmp(data[pos2], data[pos2+1]))
  75.             ++pos2;
  76.  
  77.         if (cmp(data[pos1], data[pos2]))
  78.             std::swap(data[pos1], data[pos2]);
  79.         else break;
  80.     }
  81. }
  82.  
  83. template <class T>
  84. void sift(std::vector<T> &d, size_t max) {
  85.     sift(d, max, std::less<T>());
  86. }
  87.  
  88. template <class T, class Cmp>
  89. void heap_sort(std::vector<T> &data, Cmp cmp) { 
  90.     heapify(data, cmp);
  91.  
  92.     DBG((check_heap(data, data.size(), cmp)));
  93.  
  94.     for (size_t pos=data.size()-1; pos>1; pos--) {
  95.         std::swap(data[0], data[pos]);
  96.         sift(data, pos, cmp);
  97.  
  98.         DBG((check_heap(data, pos-1, cmp)));
  99.     }
  100.  
  101.     if (cmp(data[1], data[0]))
  102.         std::swap(data[0], data[1]);
  103. }
  104.  
  105. template <class T>
  106. void heap_sort(std::vector<T> &d) {
  107.     heap_sort(d, std::less<T>());
  108. }
  109.  
  110. //#ifdef TEST
  111. template <class T, class Cmp>
  112. bool check_sorted(std::vector<T> const &data, Cmp cmp) {
  113.     bool sorted = true;
  114.     for (size_t i=0; i<data.size()-1; i++)
  115.         if (cmp(data[i+1], data[i])) {
  116.             std::cerr << "Mis-sorted: " << data[i] << " and " << data[i+1] << "\n";
  117.             sorted = false;
  118.         }
  119.     return sorted;
  120. }
  121.  
  122. template <class T>
  123. bool check_sorted(std::vector<T> const &data) {
  124.     return check_sorted(data, std::less<T>());
  125. }
  126.  
  127. template <class T>
  128. void fill_rand(std::vector<T> &data, size_t size, time_t seed) {
  129.     srand(unsigned(seed));
  130.     data.clear();
  131.  
  132.     for (size_t i=0; i<size; i++)
  133.         data.push_back((T)rand());
  134. }
  135.  
  136. #ifdef WINDOWS
  137. class timer {
  138.     LARGE_INTEGER start;
  139. public:
  140.     timer() { QueryPerformanceCounter(&start); }
  141.  
  142.     double duration() {
  143.         LARGE_INTEGER stop;
  144.         LARGE_INTEGER freq;
  145.  
  146.         QueryPerformanceCounter(&stop); 
  147.         QueryPerformanceFrequency(&freq);
  148.  
  149.         return double(stop.QuadPart-start.QuadPart)/freq.QuadPart;
  150.     }
  151. };
  152. #else
  153. class timer {
  154.     clock_t start;
  155. public:
  156.      timer() : start(clock()) {}
  157.      double duration() {
  158.          return double(clock() - start)/CLOCKS_PER_SEC;
  159.      }
  160. };
  161. #endif
  162.  
  163. int main() { 
  164.     time_t seed = time(NULL);
  165.  
  166.     // std::cout.imbue(std::locale("")); fails on ideone.
  167.  
  168.     for (int i=2; i<12; i++) {
  169.         size_t size = (1 << i) * 1024;
  170.  
  171.         std::vector<long> data;
  172.         fill_rand(data, size, seed);
  173.  
  174.         timer t;
  175.  
  176.         heap_sort(data, std::less<long>());
  177.  
  178.         double d = t.duration();
  179.  
  180.         DBG((check_sorted(data)));
  181.  
  182.         std::cout << "size:" << std::setw(12) << size << " time: " << d << "\n";
  183.     }
  184.     return 0;
  185. }
  186.  
  187. // #endif
  188.  
Success #stdin #stdout 1.2s 3020KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size:        4096 time: 0
size:        8192 time: 0
size:       16384 time: 0
size:       32768 time: 0
size:       65536 time: 0.01
size:      131072 time: 0.02
size:      262144 time: 0.04
size:      524288 time: 0.1
size:     1048576 time: 0.23
size:     2097152 time: 0.64
https://ideone.com/pAowGb
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!