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