From b4728ed55ae16f04cf59f3a9f4c3e7fc7dcb5a39 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 7 Jan 2023 19:27:52 +0100 Subject: Heapsort? --- Year_2/Algorithms/heapsort.cc | 29 ++++++++++++++++------------- 1 file changed, 16 insertions(+), 13 deletions(-) (limited to 'Year_2/Algorithms') diff --git a/Year_2/Algorithms/heapsort.cc b/Year_2/Algorithms/heapsort.cc index 7f1ad24..2c69b9d 100644 --- a/Year_2/Algorithms/heapsort.cc +++ b/Year_2/Algorithms/heapsort.cc @@ -1,3 +1,4 @@ +// FIX: This file does not make the "right" number of heapify calls #include #include @@ -22,13 +23,13 @@ public: heap(HeapType type, T* arr, int size) : _type(type) - , _n { size + 1 } + , _n { size } { - _heapsize = size - 1; + _heapsize = size; a = new T[size + 1]; - for (int i = 1; i < _n; ++i) { + for (int i = 1; i <= _n; ++i) { a[i] = arr[i - 1]; } @@ -46,13 +47,13 @@ public: heap* insert(T key) { - if (_heapsize == _n - 1) + if (_heapsize == _n) return this; a[++_heapsize] = key; unsigned i = _heapsize; - while (i > 1 && compare(i >> 1, i)) { + while (i > 1 && compare(i >> 1, i) > 0) { swap(i, i >> 1); i >>= 1; } @@ -135,7 +136,7 @@ private: }; int -main() +main(int argc, char** argv) { ifstream fin("input.txt"); ofstream fout("output.txt"); @@ -143,22 +144,24 @@ main() string type; int n; - for (int i = 0; i < 3; ++i) { + for (int i = 0; i < atoi(argv[1]); ++i) { fin >> type >> n; if (type == "int") { int k; - heap* h = new heap(HeapType::MIN, n * 10); + int* keys = new int[n]; + for (int j = 0; j < n; ++j) { - fin >> k; - h->insert(k); + fin >> keys[j]; } + heap* h = new heap(HeapType::MIN, keys, n); h->heapsort(fout); delete h; + delete[] keys; } else if (type == "char") { char* keys = new char[n]; @@ -166,7 +169,7 @@ main() fin >> keys[j]; } - heap* h = new heap(HeapType::MIN, keys, n + 1); + heap* h = new heap(HeapType::MIN, keys, n); h->heapsort(fout); @@ -179,7 +182,7 @@ main() fin >> keys[j]; } - heap* h = new heap(HeapType::MIN, keys, n + 1); + heap* h = new heap(HeapType::MIN, keys, n); h->heapsort(fout); @@ -192,7 +195,7 @@ main() fin >> keys[j]; } - heap* h = new heap(HeapType::MIN, keys, n + 1); + heap* h = new heap(HeapType::MIN, keys, n); h->heapsort(fout); -- cgit v1.2.3-18-g5258