2
\$\begingroup\$

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));
  }
}
\$\endgroup\$
0
3
\$\begingroup\$
  1. Sort your includes. That way, you can keep track even if there are more of them.

  2. 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.

  3. 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.

  4. fill_vector() is a curious interface. I would expect get_random_data() which returns the vector.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – Deduplicator May 21 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.