Trying for an efficient and readable heap-sort implementation

Question

I'm looking for any sort of optimization and/or conventional practice tips, such as using the appropriate data types and naming my variables appropriately.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

constexpr short MIN_ELEMS = 3;
constexpr short MAX_ELEMS = 15;
constexpr short LARGEST_ELEM_INT = 99;

void fill_vector(std::vector<int> &v, short MAX_ELEMS, short LARGEST_ELEM_INT);

void print_vector(const std::vector<int>::iterator start, const std::vector<int>::iterator end);

void max_heap(const std::vector<int>::iterator elem, const std::vector<int>::iterator start, std::vector<int>::iterator end);

void heap_sort(const std::vector<int>::iterator start, const std::vector<int>::iterator end);

int main() {
  srand(time(NULL));
  short random_range = rand() % MAX_ELEMS + 1;
  short num_of_elems = random_range < MIN_ELEMS ? MIN_ELEMS : random_range; // prevents num_of_elems from being less than MIN_ELEMS

  std::vector<int> v;
  fill_vector(v, num_of_elems, LARGEST_ELEM_INT);

  print_vector(v.begin(), v.end());

  heap_sort(v.begin(), v.end());

  print_vector(v.begin(), v.end());
}

void fill_vector(std::vector<int> &v, short num_of_elems, short LARGEST_ELEM_INT) {
  short i = 0;
  while (++i, i <= num_of_elems) {
    v.push_back(rand() % LARGEST_ELEM_INT);
  }
}

void print_vector(const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
  for (auto elem = start; elem != end; ++elem) {
    std::cout << *elem << ' ';
  }
  std::cout << '\n';
}

void max_heap(const std::vector<int>::iterator elem, const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
  auto biggest = elem;

  auto left_child = start+((elem-start)*2+1);
  auto right_child = start+((elem-start)*2+2);

  if (left_child < end && *left_child > *biggest) {
    biggest = left_child;
  }

  if (right_child < end && *right_child > *biggest) {
    biggest = right_child;
  }

  if (elem != biggest) {
    auto val = *biggest;
    *biggest = *elem;
    *elem = val;
    max_heap(biggest, start, end);
  }
}

void heap_sort(const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
  // sort vector to max heap
  for (auto i = start+((end-start)/2)-1; i >= start; --i) {
    max_heap(i, start, end);
  }

  // sort vector in ascending order
  for (auto i = start; i != end-1; ++i) {
    auto val = *start;
    *start = *(start+(end-i-1));
    *(start+(end-i-1)) = val;

    max_heap(start, start, start+(end-i-1));
  }
}

Deduplicator · Accepted Answer · 2021-05-21 00:17:03Z

Sort your includes. That way, you can keep track even if there are more of them.
Writing a test-program is a good idea. Though print the seed-value, and allow overriding from the command-line for reproducibility.

In line with that, add a method to test whether a range is ordered, print that result and use it for the exit-code too.
I would expect a function named print_vector() to, you know, print a vector. Not an iterator-range from a vector. Also, encoding the type of an argument in the function-name hurts usability, especially in generic code.
fill_vector() is a curious interface. I would expect get_random_data() which returns the vector.
Know your operators. ++i, i <= num_of_elems is equivalent to ++i <= num_elements.

Anyway, that should be a for-loop, or you could omit i and just count the argument down to zero.
Kudos for using constexpr to avoid preprocessor-cnstants where not needed. Still, ALL_CAPS_AND_UNDERSCORES identifiers are generally reserved for preprocessor-macros. They warn/assure everyone that preprocessor-rules apply. Fix the naming too.
The C++ headers <cxxx> modelled on the C headers <xxx.h> only guarantee to put their symbols into ::std. Don't assume they are also in the global namespace.
max_heap() will often try to create pointers far beyond the passed range. Creating such a pointer invokes undefined behavior.
For simple and correct code, better use indices.

JDługosz · Accepted Answer · 2021-05-21 15:29:32Z

Unless you really need to save memory, don't use short. Your number-of-elements should be size_t. I've benchmarked x86-64 systems that 16-bit values are much slower than 8, 32, or 64.

Don't use the C NULL macro. C++ has a keyword nullptr.

It would be more readable if you made an alias for std::vector<int>::iterator that you use many times. Really, this ought to be a template, but I understand that writing fixed code is the first step to getting it to work and then you transform it into a template. But you should think about that later step when writing the code.

It's good that you are using iterators. Most beginners seem to use arrays and index numbers instead.

I think your implementation follows the algorithm's textbook description well and is easy enough to follow, but would benefit from some comments. For example, explain that max_heap expects a certain range of elements to already be in a heap structure and draws in a new element (assuming I got that right; I'm not following that in the code but from my memory of the algorithm).

Most are good additional points, but at least inside max_heap(), indices have the advantage that even if they are grossly out-of-range, they don't cause UB. — Deduplicator
– Deduplicator, Commented May 21, 2021 at 15:51

Stack Exchange Network

Trying for an efficient and readable heap-sort implementation

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Trying for an efficient and readable heap-sort implementation

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions