I have implemented a heap data structure, and use it to sort. My understanding is that it is O(nlogn) complexity. However, when compared to bubble sort, it is order of magnitude slower -- and yeah, I tried running it for larger arrays. I checked some answers at SO (in particular this and this), but still lost. Could anyone point out what am I doing wrong here, please?
The results are:
HEAP SORT: 12415690ns
QUICK SORT: 71ns
BUBBLE SORT: 541659ns
Here are the codes:
main.cpp:
#include <chrono>
#include <iostream>
#include <stdexcept>
#include <vector>
// #include "heap.cpp"
// #include "pqueue.cpp"
#include "sort.cpp"
using namespace std;
using namespace std::chrono;
template <class T>
void printVector (vector<T> A) {
for (std::vector<int>::iterator it = A.begin(); it != A.end(); ++it) {
std::cout << *it << ' ';
}
cout << endl;
}
template <class T>
vector<T> constructVector(int A[], std::size_t len, std::size_t num) {
vector<T> res (A, A+len);
for (std::size_t idx = 0; idx < num-1; ++idx) {
res.push_back(A[idx%len]);
}
return res;
}
int main() {
high_resolution_clock::time_point t1;
high_resolution_clock::time_point t2;
int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
std::size_t len = sizeof(a) / sizeof(int);
vector<int> HEAP = constructVector<int>(a, len, 32000); // (a, a + sizeof(a) / sizeof(int));
vector<int> QUICK = constructVector<int>(a, len, 32000); // (a, a + sizeof(a) / sizeof(int));
vector<int> BUBBLE = constructVector<int>(a, len, 32000);
// cout << "Original Array: "; printVector(HEAP);
cout << "HEAP SORT: ";
t1 = high_resolution_clock::now();
heapsort(HEAP);
t2 = high_resolution_clock::now();
cout << duration_cast<nanoseconds>( t2 - t1 ).count() << "ns\n";
// cout << "New Array: "; printVector(HEAP);
// cout << "Original Array: "; printVector(QUICK);
cout << "QUICK SORT: ";
t1 = high_resolution_clock::now();
quicksort(QUICK, 0, QUICK.size());
t2 = high_resolution_clock::now();
cout << duration_cast<nanoseconds>( t2 - t1 ).count() << "ns\n";
// cout << "New Array: "; printVector(HEAP);
// cout << "Original Array: "; printVector(QUICK);
cout << "BUBBLE SORT: ";
t1 = high_resolution_clock::now();
bublesort(BUBBLE);
t2 = high_resolution_clock::now();
cout << duration_cast<nanoseconds>( t2 - t1 ).count() << "ns\n";
// cout << "New Array: "; printVector(HEAP);
}
sort.cpp:
#ifndef __SORT_CPP_INCLUDED_
#define __SORT_CPP_INCLUDED_
#include <vector>
#include "heap.cpp"
template <class T>
void heapsort(std::vector<T> &A, bool increasing = true) {
Heap<T> H(A, increasing);
H.sort();
A = H.get();
}
template <class T>
std::size_t partition(std::vector<T> &A, std::size_t p, std::size_t r) {
T x = A[r-1];
std::size_t i = p - 1;
for (std::size_t j = p; j < r; ++j) {
if (A[j] <= x) {
++i;
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
}
}
A[i+1] ^= A[r-1];
A[r-1] ^= A[i+1];
A[i+1] ^= A[r-1];
return i + 1;
}
template <class T>
void quicksort(std::vector<T> &A, std::size_t p, std::size_t r) {
if (p-1 < r) {
std::size_t q = partition(A, p, r);
quicksort(A, p, q);
quicksort(A, q+1, r);
}
}
template <class T>
void bublesort(std::vector<T> &A) {
bool swapped = false;
do {
swapped = false;
for (std::size_t idx = 1; idx < A.size(); ++idx) {
if (A[idx-1] > A[idx]) {
// swap them
A[idx] = A[idx-1];
A[idx-1] = A[idx];
A[idx] = A[idx-1];
swapped = true;
}
}
} while (swapped);
}
#endif
heap.cpp:
#ifndef __HEAP_CPP_INCLUDED__
#define __HEAP_CPP_INCLUDED__
#include <vector>
template <class T>
class Heap {
public:
Heap(bool maxHeap = true) : heap_size(0), max_heap(maxHeap) {}
Heap(const std::vector<T> &a, bool maxHeap = true) : A(a), max_heap(maxHeap) {
if (maxHeap) this->build_max_heap(); else this->build_min_heap(); }
~Heap() {}
protected:
std::vector<T> A;
std::size_t heap_size;
bool max_heap;
public:
std::size_t parent(std::size_t idx) { return (idx - 1) >> 1; }
std::size_t left(std::size_t idx) { return (idx << 1) + 1; }
std::size_t right (std::size_t idx) { return (idx + 1) << 1; }
public:
std::vector<T> get() { return A; }
std::size_t size() { return heap_size; }
void sort();
void build_max_heap();
void build_min_heap();
void max_heapify(std::size_t idx);
void min_heapify(std::size_t idx);
};
template <class T>
void Heap<T>::sort() {
if (this->heap_size <= 0) return; // Already sorted or empty
if (this->heap_size != this->A.size()){ // Not sorted and not heapified
max_heap ? build_max_heap() : build_min_heap();
}
for (std::size_t idx = this->A.size()-1; idx > 0; --idx) {
A[0] ^= A[idx];
A[idx] ^= A[0];
A[0] ^= A[idx];
--this->heap_size;
max_heap ? max_heapify(0) : min_heapify(0);
}
}
template<class T>
void Heap<T>::build_max_heap() {
this->heap_size = this->A.size();
for (std::size_t idx = (this->A.size() - 1) >> 1; idx > 0; --idx)
this->max_heapify(idx);
this->max_heapify(0);
}
template<class T>
void Heap<T>::build_min_heap() {
this->heap_size = this->A.size();
for (std::size_t idx = (this->A.size()-1) >> 1; idx > 0; --idx)
this->min_heapify(idx);
this->min_heapify(0);
}
template <class T>
void Heap<T>::max_heapify(std::size_t idx) {
std::size_t l = this->left(idx);
std::size_t r = this->right(idx);
std::size_t largest;
if (l < this->heap_size && A[l] > A[idx]) largest = l;
else largest = idx;
if (r < this->heap_size && A[r] > A[largest]) largest = r;
if (largest != idx) {
this->A[idx] ^= this->A[largest];
this->A[largest] ^= this->A[idx];
this->A[idx] ^= this->A[largest];
this->max_heapify(largest);
}
}
template <class T>
void Heap<T>::min_heapify(std::size_t idx) {
std::size_t l = this->left(idx);
std::size_t r = this->right(idx);
std::size_t smallest;
// std::cout << "DEBUG: " << idx << std::endl;
if (l < this->heap_size && A[l] < A[idx]) smallest = l;
else smallest = idx;
if (r < this->heap_size && A[r] < A[smallest]) smallest = r;
if (smallest != idx) {
this->A[idx] ^= this->A[smallest];
this->A[smallest] ^= this->A[idx];
this->A[idx] ^= this->A[smallest];
this->min_heapify(smallest);
}
}
#endif
