2
\$\begingroup\$

Hey Guys,
I'm in the process of building a console program in C ++ that allows users to:

  • sort a sequence of numbers loaded from a TXT file
  • save sorted sequence in a new TXT file
  • measure the sorting time for individual algorithm

I decided to write such a program because I want to learn algorithms, how different sorting algorithms work and I was curious how efficient/fast each individual algorithm is.

At the moment I have implemented

  • Bubble Sort
  • Insertion Sort
  • IntroSort (from C++ STD)
  • Selection Sort
  • Merge Sort
  • Quicksort

This is a sample output of the program

   [Bubble Sort]  Took:  77817989 µs   (77817.989 ms) (77s) to sort 100000 numbers
[Insertion Sort]  Took:  24974911 µs   (24974.911 ms) (24s) to sort 100000 numbers
      [STD Sort]  Took:     33990 µs      (33.990 ms)  (0s) to sort 100000 numbers
[Selection Sort]  Took:  20961005 µs   (20961.005 ms) (20s) to sort 100000 numbers
    [Merge Sort]  Took:    364995 µs     (364.995 ms)  (0s) to sort 100000 numbers
     [Quicksort]  Took:     25993 µs      (25.993 ms)  (0s) to sort 100000 numbers

Okay, end of story about the project, I have a few questions for experienced programmers

  1. Could anyone do some little code review please?
    I wonder if I have built the project structure correctly. What could be changed in the code. What is coded incorrectly. What bad practices have I committed. e.t.c
  2. I wonder if the measurement results are reliable in any way. How the system speed or the order in which the sorting function is called affects the results
  3. I plan to implement even more sorting algorithms. In your opinion, what other features could I add to make the project more interesting and to impress the future employer?
  4. And one last thing. What is your honest opinion about this project?

Thank you very much in advance for any help


main.cpp

#include <iostream>
#include "sorter.h"

int main() {
  Sorter s;
  s.load_numbers("nums.txt");

  s.run_bubble_sort();
  s.run_insertion_sort();
  s.run_std_sort();
  s.run_selection_sort();
  s.run_merge_sort();
  s.run_quicksort();

  return 0;
}

timer.h

#include <chrono>
#include <string>

class Timer {
public:
  Timer(std::string sorting_alg, int num_quantity);
  ~Timer();

private:
  std::chrono::time_point<std::chrono::high_resolution_clock> _startTimepoint;
  std::string _algorythm;
  int _quantity;
  void _stop_timer();
};

timer.cpp

#include <iostream>
#include <string>
#include "timer.h"

Timer::Timer(std::string sorting_alg, int num_quantity) {
  _startTimepoint = std::chrono::high_resolution_clock::now();
  _algorythm = sorting_alg;
  _quantity = num_quantity;
}

void Timer::_stop_timer() {
    auto endTimepoint = std::chrono::high_resolution_clock::now();
    auto start = std::chrono::time_point_cast<std::chrono::microseconds>(_startTimepoint).time_since_epoch().count();
    auto end = std::chrono::time_point_cast<std::chrono::microseconds>(endTimepoint).time_since_epoch().count();

    auto duration = end - start;
    double miliseconds = duration * 0.001;
    int seconds = miliseconds * 0.001;
    
    // Just remove three 0's from ms number
    std::string in_miliseconds = " (" + std::to_string(miliseconds).substr(0,(std::to_string(miliseconds).length() - 3)) + " ms)";

    std::cout.width(16);
    std::cout << "[" + _algorythm + "]";

    std::cout.width(7);
    std::cout << " Took:";

    std::cout.width(10);
    std::cout << duration;

    std::cout.width(2);
    std::cout << " \xE6s";

    std::cout.width(17);
    std::cout << in_miliseconds;

    std::cout.width(6);
    std::cout << " (" + std::to_string(seconds) + "s)";

    std::cout.width(20);
    std::cout << " to sort " + std::to_string(_quantity) + " numbers\n";
}

Timer::~Timer() {
  _stop_timer();
}

sorter.h

#pragma once

#include <vector>

class Sorter {
  public:
  void load_numbers(std::string filename);
  void run_bubble_sort(std::string output_filename = "sorted_bubble_sort.txt");
  void run_insertion_sort(std::string output_filename = "sorted_insertion_sort.txt");
  void run_std_sort(std::string output_filename = "sorted_std_sort.txt");
  void run_selection_sort(std::string output_filename = "sorted_selection_sort.txt");
  void run_merge_sort(std::string output_filename = "sorted_merge_sort.txt");
  void run_quicksort(std::string output_filename = "sorted_quicksort_sort.txt");
  

  private:
  std::vector<int> _unsorted;
  std::vector<int> _sorted;

  // For Merge Sort
  std::vector<int> _merge(std::vector<int> L, std::vector<int> R);
  std::vector<int> _mergeSort(std::vector<int> to_sort);

  // For Quicksort
  int _partition(std::vector<int> &arr, int from, int to);
  void _quicksort(std::vector<int> &arr, int from, int to);

  void _save_numbers_to_file(std::string output_filename);
  void _swap(int *left, int *right);
  void _die(const std::string& err_msg);
};

sorter.cpp

#include <fstream>
#include <iostream>
#include <algorithm>

#include "sorter.h"
#include "timer.h"

void Sorter::load_numbers(std::string filename) {
  /* 
   * Reads numbers from file and saves them to _unsorted vector
   * 
   * :param filename: filename to read numbers from
  */
  std::ifstream nums_file (filename);
  int curr_num;
  _unsorted.clear();

  while (nums_file >> curr_num) {
    // Add numbers from file to an array
    //std::cout << curr_num << ", ";
    _unsorted.push_back(curr_num);
  }

  nums_file.close();
}

void Sorter::run_bubble_sort(std::string output_filename) {
  /* 
   * Sorts an array with Bubble Sort algorithm
   * 
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    // Start timer
    Timer t("Bubble Sort", numbers_count);
  
    bool swapped = false;

    for (int i = 0; i < numbers_count - 1; i++) {
      swapped = false;
      for (int j = 0; j < numbers_count - i - 1; j++) {
        if (_sorted[j] > _sorted[j+1]) {
          // Swap places
          _swap(&_sorted[j], &_sorted[j+1]);
          swapped = true;
        }
      }
      if (swapped == false) {
          // Array sorted
          break;
      }
    }
  }
  
  _save_numbers_to_file(output_filename);
}

void Sorter::run_insertion_sort(std::string output_filename) {
  /* 
   * Sorts an array with Insertion Sort algorithm
   * 
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    // Start timer
    Timer t("Insertion Sort", numbers_count);
    for (int i = 1; i < numbers_count; i++) {
      int curr = _sorted[i];

      int j = i - 1;
      // Shift each element to the right
      while(j >= 0 && _sorted[j] > curr) {
        _sorted[j+1] = _sorted[j];
        j--;
      }
      _sorted[j+1] = curr;
    }
  }

  _save_numbers_to_file(output_filename);
}

void Sorter::run_std_sort(std::string output_filename) {
   /* 
   * Sorts an array with sort() function from
   * C++ Standard Library - from <algorithm> header
   *
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    Timer t("STD Sort", numbers_count);

    std::sort(_sorted.begin(), _sorted.end());
  }

  _save_numbers_to_file(output_filename);
}

void Sorter::run_selection_sort(std::string output_filename) {
  /* 
   * Sorts an array with Selection Sort algorithm
   * 
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  int min;
  int min_index;

  {
    Timer t("Selection Sort", numbers_count);

    for (int i = 0; i < numbers_count; i++) {
      min = _sorted[i];
      min_index = i;
      for(int j = i; j < numbers_count; j++) {
        if (_sorted[j] < min) {
          // we have new min
          min = _sorted[j];
          min_index = j;
        }
      }
      _swap(&_sorted[i], &_sorted[min_index]);
    }
  }
  
  _save_numbers_to_file(output_filename);
}

void Sorter::run_merge_sort(std::string output_filename) {
  /* 
   * Runs Merge Sort algorithm
   * 
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    Timer t("Merge Sort", numbers_count);
    
    _sorted = _mergeSort(_sorted);
  }
  
  _save_numbers_to_file(output_filename);
}

std::vector<int> Sorter::_merge(std::vector<int> L, std::vector<int> R) {
  /* 
   * [Helper function for _mergeSort]
   * Merges two sorted arrays into one sorted array
   * 
   * :param L: first (half) array
   * :param R: second (half) array
   * :return: merged array as vector
  */
  std::vector<int> merged;
  
  int L_i = 0; // Index of smallest unpicked num in L
  int R_i = 0; // Index of smallest unpicked num in R

  // Fill merged array with elements from L and R
  while(L_i < L.size() && R_i < R.size()) {
      if (L[L_i] <= R[R_i]) {
          // Get val from Left arr and insert into merged
          merged.push_back(L[L_i]);
          L_i++;
      } else {
          // Get val from right arr and insert into merged
          merged.push_back(R[R_i]);
          R_i++;
      }
  }
  
  // If all values from right arr were inserted (into merged),
  // Take left arr and insert it's values to merged
  while(L_i < L.size()) {
      merged.push_back(L[L_i]);
      L_i++;
  }
  
  // If all values from left arr were inserted (into merged),
  // Take right arr and insert it's values to merged
  while(R_i < R.size()) {
      merged.push_back(R[R_i]);
      R_i++;
  }
  return merged;
}

std::vector<int> Sorter::_mergeSort(std::vector<int> to_sort) {
  /* 
  * Sorts an array with Merge Sort algorithm 
  * 
  * :param to_sort: array to be sorted
  * :return: sorted array as vector
  */
  if (to_sort.size() <= 1) {
      return to_sort;
  }
  
  std::vector<int> left;
  std::vector<int> right;
  
  // Divide to_sort into 2 halfs
  // Fill left array with first half and
  // right array with second half
  for (int i = 0; i < to_sort.size(); i++) {
      if (i < to_sort.size() / 2) {
          left.push_back(to_sort[i]);
      } else {
          right.push_back(to_sort[i]);
      }
  }
  
  // Recursion
  left = _mergeSort(left);
  right = _mergeSort(right);
  
  // Return final, sorted array
  return _merge(left, right);
}

void Sorter::run_quicksort(std::string output_filename) {
  /* 
   * Runs Quicksort algorithm
   * 
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    Timer t("Quicksort", numbers_count);
    
    _quicksort(_sorted, 0, _sorted.size() - 1);
  }
  
  _save_numbers_to_file(output_filename);
}

int Sorter::_partition(std::vector<int> &arr, int from, int to) {
  /* 
   * Helper function for quicksort algorithm
   * Sets pivot to last element of array
   * Places pivot at its correct position so that
   * all smaller values are on the left side
   * and greater values are on the right side 
   * (of the pivot)
   *
   * :param arr: array to be sorted
   * :param from: lowest index of array
   * :param to: highest index of array
  */
  int pivot = arr[to]; // Set the last element as pivot
  int i = from - 1;

  for (int j = from; j <= to - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      _swap(&arr[i], &arr[j]);
    }
  }

  // The final postition of pivot as (i + 1)
  _swap(&arr[i + 1], &arr[to]);
  
  // Return position of pivot
  return (i + 1);
}

void Sorter::_quicksort(std::vector<int> &arr, int from, int to) {
  /* 
   * Sorts an array with Quicksort algorithm 
   * 
   * :param arr: array to be sorted
   * :param from: lowest index of array
   * :param to: highest index of array
  */
  if (from < to) {
    int p_i = _partition(arr, from , to); // Partitioning index
    
    _quicksort(arr, from, p_i - 1); // Left side
    _quicksort(arr, p_i + 1, to); // Right side
  }
}

void Sorter::_swap(int *left, int *right) {
  /* 
   * Swaps two number in an array
   * 
   * :param *left: pointer to first number location
   * :param *right: pointer to second number location
  */
  int temp = *left;
  *left = *right;
  *right = temp;
}

void Sorter::_save_numbers_to_file(std::string output_filename) {
  /* 
   * Saves sorted array into a file
   * 
   * :param output_filename: file name with sorted numbers
  */
  std::ofstream output_file (output_filename);
  for (int i = 0; i < _sorted.size(); i++) {
    output_file << _sorted[i];
    if (i != _sorted.size() - 1) {
      output_file << ", ";
    }
  }
  output_file.close();
}

void Sorter::_die(const std::string& err_msg)
{
   /* 
   * Outputs error message on standard error output stream
   * and exits program
   * 
   * :param err_msg: error message to be displayed
  */
    std::cerr << err_msg << std::endl;
    exit(1);
}
```
\$\endgroup\$
4
  • \$\begingroup\$ What is "Incredibly Precise" about this? \$\endgroup\$
    – G. Sliepen
    May 2, 2021 at 22:08
  • 2
    \$\begingroup\$ I’d say anyone timing a 78 s operation and reporting the time down to the microsecond is being incredibly precise. \$\endgroup\$
    – indi
    May 2, 2021 at 23:45
  • \$\begingroup\$ Hi @Giovacho - How do you know that your sorts actually work - did you compare the results?? And are you perhaps just lucky? i.e. if you added 3 more rows would they still work properly? Why - well if they don't work properly - then any "performance" comparison is not really a fair comparison. \$\endgroup\$
    – Mr R
    May 3, 2021 at 4:29
  • \$\begingroup\$ @Mr R I agree that this could be a potential problem. But in the future I am going to add unit tests to the project \$\endgroup\$
    – Giovacho
    May 3, 2021 at 8:53

1 Answer 1

8
\$\begingroup\$

Questions (+ design review)

Could anyone do some little code review please?

The biggest issue I see with your current design is that you are using the “god object” anti-pattern. Your Sorter class:

  1. Loads the data from a file.
  2. Implements over a half-dozen sort algorithms.
  3. Tests over a half-dozen sort algorithms.
  4. Writes sorted data to a file (over a half-dozen different ways).

The general rule of good software design is “one ‘thing’, one job”, where “thing” could be a class, a function, or whatever else. In this case, loading the data is one “thing”, each sort algorithm is its own “thing”. The test mechanism is (should be) one “thing”. And so on.

In addition, there’s the question of whether the “thing” should be a class or a function. C++ is not Java; it is not necessary to shoehorn every operation into a class. If a “thing” is only doing something—and doesn’t need to maintain state or data—then it doesn’t need to be a class. It can be a function. In particular, every one of those sort functions should be (as implied right in the name “sort function”)… a function.

Sometimes it’s better to start designing from a high-level interface perspective. By that I mean, forget about the low-level details at first, and focus on what you want the code to look like. I don’t think if someone gave you the problem statement, that you first instinct would be to write main() the way it is written. The idea of a “sorter” object doesn’t really make a lot of sense. I think a more natural look for main() would be something like:

// load the data
auto const data = load_data("nums.txt");

// for each sort function, run a test
//
// the test needs the name of the sort, the actual function to test, and the
// data to test with
test_sort_function("Bubble sort",    &bubble_sort,    data);
test_sort_function("Insertion Sort", &insertion_sort, data);
test_sort_function("STD Sort",       &std_sort,       data);
// ...

Or perhaps;

// load the data
auto const data = load_data("nums.txt");

// each sort function has a name, and the actual function
auto const tests = std::vector<std::tuple<std::string_view, sort_function_t>>{
    {"Bubble sort",    &bubble_sort},
    {"Insertion Sort", &insertion_sort},
    {"STD Sort",       &std_sort},
    // ...
};

for (auto&& [name, func] : tests)
{
    // test logic here
}

Personally, I prefer the latter design, because it allows me to repeat and reorder tests much more easily.

Either way makes it pretty trivial to add a new sort algorithm to test: simply write the actual sort algorithm, then add a new line—either a new test_sort_function() line, or a new line in that tests lists. That’s just two tasks: create the algorithm, register the test. Done.

And that’s another reason why god objects are so bad. If I want to add a new sort algorithm to test with your current design, I have to:

  1. Write actual algorithm (and, of course, test it… which is something your current design doesn’t seem to take into account).
  2. Write the run_???_sort() function, which has to:
    1. Verify the input data.
    2. Create the actual working data.
    3. Create a timer.
    4. Run the algorithm.
    5. (Output the test data. Luckily this is automatic due to being in the destructor of Timer.)
    6. Write the sorted data to an output file.
  3. Add a new line in main() to actually run the test.

That’s a hell of a lot of work just to add one more tests. And it’s really inflexible: what if I wanted to try running, say, bubble sort three different ways—with the data randomized, with the data reverse sorted, and with the data already sorted—to see how much difference it makes when the data is already sorted. There are two ways to consider solving that problem: one would be to write 3 different test lines to test a single sort algorithm, the other would be to modify the test logic to run those tests for every sort algorithm. Either option is difficult with your current design, but trivial with the two designs I suggested. That’s what happens when you take the time to think of the high-level interface you want, before diving into low-level code details.

I can’t speak for most employers, but that’s what I would be looking for if I were hiring a programmer. If I toss out a spec, and a coder immediately starts banging out code on the keyboard… they’re already done; I won’t be hiring them. The coder who stopsthinks… and works their way through a high-level overview of the problem first… that’s who I want.

So as a summary of the problems with your design:

  • It has a massive code smell due to using a god object. Even without digging into the class, it’s obvious that Sorter is a god object just from glancing at main().
  • If I want to add a new sort algorithm, it takes an infuriating amount of boilerplate to do what should be a simple job.
  • If I want to change the nature of the testing—for example, by running tests with differently-pre-sorted data, or by doing a bunch of iterations and averaging the times—I have to do so independently for every algorithm.
  • Most of the sort algorithms are buried in the test code. How do you even know they actually work? How could you test them? They could be buggy as all hell and you’d never know.

I wonder if the measurement results are reliable in any way.

They are not.

Benchmarking is a very hard problem. Your test results could be affected by:

  • which test is run first (because it may need to allocate memory, which ends up in a call to the kernel to get new pages allocated, but once you have those pages the following tests will just reuse them)
  • the order of the tests (because one test may leave the cache in a state that is beneficial or detrimental to the next test)
  • what else happens to be running on the system
  • the state of your storage media (you’re doing output after every test, after all)
  • randomness (the OS may decide to do some kind of sweep while your tests are running, or DRAM refresh may cause issues at an even lower level);
  • and so on.

There is simply no way to prevent any of the above confounding factors.

And that’s not to mention that compiler optimizations might ruin your day, too. Benchmarking is a very, very, VERY hard problem.

What you could do to minimize the influence of (some of) these confounding factors is to treat your benchmarking like an actual scientific experiment, and follow the best practices for that. For example, rather than taking a simple data point, take hundreds or thousands—run each test many, many times—perhaps in random order. Then average those results, possibly after throwing out the highest and lowest 10% or something, or maybe finding the standard deviation and throwing out any data points that are more than 1 or 2 standard deviations away from the mean, or whatever you please.

I plan to implement even more sorting algorithms.

But doing so with your current design is extremely tedious and error-prone. That should be a sign of a problem. Before thinking about adding “features”, that is what I would want to see a prospective hire focused on; eagerly piling crap on crap does not give me confidence that someone is a good programmer, going back and fixing problems to make existing code better does.

What is your honest opinion about this project?

It’s actually a really, really good portfolio project, and if you do it well, a good thing to show off to prospective employers.

Therefore, you should really focus on doing it well.

If you showed this to me as a prospective employer, I’m not going to be interested in how “clever” your low-level code is—like the actual sort algorithms. I’m not really impressed by the knowledge of sort algorithms either; every comp-sci student knows a dozen of them. What I’ll be looking for is the high-level stuff:

  • How easy is it to add a new sort algorithm to test?
  • How easy would it be to change the nature of the testing (for example, adding tests for already-sorted data, reverse-sorted data, etc.)?
  • How flexible is it (for example, could I change the order of the tests, could I change the number of repeats, could I disable certain tests, etc.)?

I would be looking at the structure of your code, to see how well it reflects an organized mind, and an understanding of what’s really important in a program: clarity, testability, ease of maintenance, and so on.

Don’t go too far adding “features”, because as a portfolio sample, the code should be fairly small and lean. I’m not going to sit and read through thousands of lines of code; I want short samples, but short samples that really illustrate that a programmer understands what it means to be a programmer.

Code review

I’ve already covered my opinion on the current structure of main() in the design review, so I won’t repeat it.

So let’s move on timer.h.

First, I think it’s bad practice to name C++ header files with a .h extension. I know there are experts who disagree, but .h means that a header is a C header, or possibly polyglot. A C++ header would be .hpp.

Second, you are missing include guards.

You should also get in the habit of putting your code in a namespace.

Now, Timer is not a great name for this class, because it’s not just a timer. It’s actually a very specific type of timer; it’s a timer for sort algorithm testing. The name Timer misleads me into thinking that I can reuse it for other timing purposes.

This class should have a more purpose-specific name, and it should probably be in a purpose-specific header, because it doesn’t really have any general purpose use. You probably want a sort_testing.hpp header, which will hold the timer and other test functions.

(Note that if you used a sort-testing-specific namespace, then Timer would be an okay name for the class, because then it would actually be mynamespace::sort_testing::Timer.)

Timer(std::string sorting_alg, int num_quantity);

num_quantity should not be an int. If you want counts in C++, the correct type is usually std::size_t. If you use int, you are going to see errors with large datasets.

You should also consider that this class is functionally impossible to test, due to the fact that it writes its results to std::cout. That’s bad; untestable code is garbage code. Doesn’t matter how “well-written” it is; if code doesn’t have tests, it is completely useless for serious projects.

So you should give this class the ability to write its results to wherever the user chooses. An easy way is to add a std::ostream& argument to the constructor, and use that output stream in the destructor rather than std::cout.

OR…

Stop. Take a step back. Rethink.

Rather than writing all this job-specific stuff into the timer… perhaps rethink the problem as a timer that just has to do something when the timing is done. And then let that something be configurable.

So, for example, something like this:

template <std::invocable<std::chrono::microseconds> Func>
class timer
{
public:
    explicit timer(Func f) : _func{std::move(f)}
    {
        // start the timer after everything else is done
        _start = std::chrono::high_resolution_clock::now();
    }

    ~timer()
    {
        // stop the timer
        auto const end = std::chrono::high_resolution_clock::now();

        // calculate the duration
        auto const duration = std::chrono::microseconds(end - _start);

        // call the callback
        _func(duration);
    }

    // noncopyable
    timer(timer const&) = delete;
    auto operator=(timer const&) -> timer& = delete;

    // nonmovable
    timer(timer&&) = delete;
    auto operator=(timer&&) -> timer& = delete;

private:
    std::chrono::time_point<std::chrono::high_resolution_clock> _start;
    Func _func;
};

And you’d use it like:

class display_results
{
public:
    display_results(std::string algorithm, std::size_t quantity) :
        _algorithm{std::move(algorithm)},
        _quantity{quantity}
    {}

    auto operator()(std::chrono::microseconds duration)
    {
        using namespace std::literals;

        out.width(16);
        out << ("["s + algorithm + "]"s);

        out.width(7);
        out << " Took:";

        out.width(10);
        out << duration.count();

        out.width(2);
        out << " \xE6s";

        // etc.
    }

private:
    std::string _algorithm;
    std::size_t _quantity;
};

// in test code:
{
    auto const _ = timer{display_results{"Bubble sort", data.size()}};

    bubble_sort(data);
}
{
    auto const _ = timer{display_results{"Insertion sort", data.size()}};

    insertion_sort(data);
}
// etc.

That would net you a general-purpose, reusable timer. That ain’t bad.

Moving on…

Timer::Timer(std::string sorting_alg, int num_quantity) {
  _startTimepoint = std::chrono::high_resolution_clock::now();
  _algorythm = sorting_alg;
  _quantity = num_quantity;
}

So what you’re doing here is starting the clock… then proceeding to copy a string (and an int) that both have nothing to do with what you’re supposed to be timing. I mean, it won’t make much difference, but it’s not a good look.

The first thing you should look into is member initializer lists, so you constructor would be:

Timer::Timer(std::string sorting_alg, int num_quantity) :
    _algorythm{sorting_alg},
    _quantity{num_quantity}
{
  _startTimepoint = std::chrono::high_resolution_clock::now();
}

That gets all the initialization out of the way before you actually start the timer.

Next you should look into moving, rather than copying. It can make a huge difference for strings:

Timer::Timer(std::string sorting_alg, int num_quantity) :
    _algorythm{std::move(sorting_alg)},
    _quantity{num_quantity}
{
  _startTimepoint = std::chrono::high_resolution_clock::now();
}

Now, you go through a lot of theatrics to calculate your durations… but there’s really no need for most of it. Let’s start with what you have:

auto endTimepoint = std::chrono::high_resolution_clock::now();
auto start = std::chrono::time_point_cast<std::chrono::microseconds>(_startTimepoint).time_since_epoch().count();
auto end = std::chrono::time_point_cast<std::chrono::microseconds>(endTimepoint).time_since_epoch().count();

auto duration = end - start;
double miliseconds = duration * 0.001;
int seconds = miliseconds * 0.001;

The first line is obviously correct, so there’s no need to change that.

However, the next two lines are weird and pointless. You want the duration in microseconds? Then just get the duration in microseconds:

auto const endTimepoint = std::chrono::high_resolution_clock::now();

auto const duration = std::chrono::microseconds{endTimepoint - _startTimepoint};

That’s it.

Now to get milliseconds, you want those as doubles. So you need to do

auto const endTimepoint = std::chrono::high_resolution_clock::now();

auto const duration = std::chrono::microseconds{endTimepoint - _startTimepoint};
auto const miliseconds = std::chrono::duration<double, std::milli>{duration};

Finally, you want seconds as an integer, so:

auto const endTimepoint = std::chrono::high_resolution_clock::now();

auto const duration = std::chrono::microseconds{endTimepoint - _startTimepoint};
auto const miliseconds = std::chrono::duration<double, std::milli>{duration};
auto const seconds = std::duration_cast<std::chrono::seconds>(duration); // need a cast because of loss of precision

That’s it.

Now to print those values:

std::cout << duration.count(); // prints microseconds

std::cout.precision(3);
std::cout << milliseconds.count(); // prints milliseconds to 3 decimal places

std::cout << seconds.count(); // prints seconds

If you really want fixed-width printing of chunks of data, it’s much easier to use temporary string streams than all the shenanigans you’re doing with substring manipulation:

auto oss = std::ostringstream{};
oss.precision(3);
oss << " (" << milliseconds.count() << " ms)";

std::cout.width(17);
std::cout << oss.str();

Now onto sorter.h:

#pragma once

Don’t use #pragma once. It is non-standard, and it has some very nasty bugs that you do not want to run into. Include guards are standard, and are just as efficient.

#include <vector>

You’ve forgotten to include <string>.

class Sorter

Okay, let’s get into the design of this class. I’ve already said this class is a god object, and that’s bad… but let’s get into specific problems.

The class has two data members:

std::vector<int> _unsorted;
std::vector<int> _sorted;

The first one makes sense… you need to keep a copy of the raw data. But… why do you need to keep a copy of the sorted data?

Look at your test algorithms. Every single one has this chunk of code in it (which is buggy… but we’ll get to that):

const int numbers_count = _unsorted.size();
_sorted.clear();
_sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

This dance is necessary because you need to reset the sorted data. But… why? Why not just use a new vector in each test? Like so (using run_std_sort() because it’s the shortest):

void Sorter::run_std_sort(std::string const& output_filename) const
{
  if (_unsorted.empty() == true)
  {
    _die("Error: No numbers loaded.");
  }

  // can't get much simpler than this:
  auto numbers = _unsorted;

  {
    Timer t("STD Sort", numbers.size());

    std::sort(numbers.begin(), numbers.end());
  }

  //_save_numbers_to_file(output_filename);
  //
  // you need to pass the data to the write function:
  _save_numbers_to_file(output_filename, numbers);
}

void Sorter::_save_numbers_to_file(std::string const& output_filename, std::vector<int> const& numbers) const
{
  auto output_file = std::ofstream{output_filename};

  auto first = true;
  for (auto&& number : numbers)
  {
    // this is a standard trick to get nicely formatted output
    if (not std::exchange(first, false))
      output_file << ", ";

    output_file << number;
  }
}

So you don’t need _sorted at all.

As for _unsorted, you have another code smell: every test function has this chunk:

  if (_unsorted.empty() == true)
  {
    _die("Error: No numbers loaded.");
  }

If you have to check a class’s invariants in every public member function… you have a bad design.

There are two ways you might fix this. Option 1 is to move the whole of load_numbers() into a constructor, like so:

class Sorter
{
public:
    explicit Sorter(std::string const& filename)
    {
        auto file = std::ifstream{filename};

        // you should check that the file opened!
        //
        // you should also check for errors reading the numbers

        std::copy(
            std::istream_iterator<int>{file},
            std::istream_iterator<int>{},
            std::back_inserter(_unsorted)
        );

        // do any other checks you want here
        //
        // if anything is not kosher, throw an exception
    }

    // ...

With that, you will know that once your Sorter has been successfully constructed, _unsorted is good. No need to check in every member function. In fact, every member function can now be const, because it doesn’t change the (god) object’s state. This is a very good thing.

The other option—probably the better option—is to take the whole input function out of the class entirely. It shouldn’t be there in any case. It’s a completely separate job, so it should be in its own unit. This actually increases flexibility, because now you can load data from a file, or the network, or you can generate random data, and now Sorter doesn’t care.

So something like this:

auto load_numbers(std::filesystem::path const& path)
{
    auto data = std::vector<int>{};

    auto file = std::ifstream{path};

    std::copy(
        std::istream_iterator<int>{file},
        std::istream_iterator<int>{},
        std::back_inserter(data)
    );

    return data;
}

class Sorter
{
public:
    template <std::ranges::input_range R>
        requires std::same_as<std::ranges::range_value_t<R>, int>
    Sorter(R&& r)
    {
        std::ranges::copy(r, std::back_inserter(_unsorted));

        // do any checks you want, throw an exception if they fail
    }

    // ...
};

auto s = Sorter{load_numbers("nums.txt")};

As for load_numbers():

void Sorter::load_numbers(std::string filename) {
  /* 
   * Reads numbers from file and saves them to _unsorted vector
   * 
   * :param filename: filename to read numbers from
  */
  std::ifstream nums_file (filename);
  int curr_num;
  _unsorted.clear();

  while (nums_file >> curr_num) {
    // Add numbers from file to an array
    //std::cout << curr_num << ", ";
    _unsorted.push_back(curr_num);
  }

  nums_file.close();
}

There is no reason to take the filename by value. You’re only looking at it, not keeping a copy. You should take it by const& to avoid an unnecessary copy.

Even better, rather than a plain string, you could take a std::filesystem::path const&.

Within the function, you don’t really do any error checking at all. You don’t check that the file was even opened, and you don’t check that the numbers are valid. At the first invalid number read, the function will just assume there is no more input. You’ll never know that your data is bad.

Finally, there’s no need to explicitly close the file. That’s done automatically.

And again, this should not be a member function, it should be a separate function.

Now I’m going to skip around a bit and do _save_numbers_to_file() here, because it’s almost identical to load_numbers(). Everything from there applies here, but also:

  for (int i = 0; i < _sorted.size(); i++) {
    output_file << _sorted[i];
    if (i != _sorted.size() - 1) {
      output_file << ", ";
    }
  }

There’s a standard trick for what you’re trying to do here, that works even if you’re using data that you don’t know the size.

The trick is to use a flag for the first iteration, and not print the comma if the flag is true:

auto first = true;
for (auto&& number : _sorted)
{
    if (not first)
        out << ", ";

    first = false;

    out << number;
}

With std::exchange() you can compact that a bit:

auto first = true;
for (auto&& number : _sorted)
{
    if (not std::exchange(first, false))
        out << ", ";

    out << number;
}

Before I get into the sorting functions, let’s clear up the remaining stuff:

void Sorter::_swap(int *left, int *right) {
  /* 
   * Swaps two number in an array
   * 
   * :param *left: pointer to first number location
   * :param *right: pointer to second number location
  */
  int temp = *left;
  *left = *right;
  *right = temp;
}

This is completely unnecessary: use std::swap().

void Sorter::_die(const std::string& err_msg)
{
   /* 
   * Outputs error message on standard error output stream
   * and exits program
   * 
   * :param err_msg: error message to be displayed
  */
    std::cerr << err_msg << std::endl;
    exit(1);
}

Never, ever use std::exit() in a C++ program. It is a C library function that doesn’t work well in C++.

There is no clean way to abruptly exit a program in C++; that defies the nature of what C++ is. If you just want to do a hard exit, there is std::terminate(), but that’s ugly. A better option in almost every situation is to throw an exception.

Okay, now on to the sort functions, which are all more-or-less identical. I’ll focus on run_std_sort() because it’s the shortest.

void Sorter::run_std_sort(std::string output_filename) {
   /* 
   * Sorts an array with sort() function from
   * C++ Standard Library - from <algorithm> header
   *
   * :param output_filename: file name with sorted numbers
  */

  // Check if numbers were loaded from file
  if (_unsorted.empty() == true) {
    _die("Error: No numbers loaded.");
  }

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

  {
    Timer t("STD Sort", numbers_count);

    std::sort(_sorted.begin(), _sorted.end());
  }

  _save_numbers_to_file(output_filename);
}

Okay, first, as with the input/output functions, you don’t need to take the filename by value… because you don’t need to take the value, you only want to read the value. So you should use a const&. In addition, you should consider using a std::filesystem::path rather than a std::string. It’s always good to use the right types.

Next, that chunk that checks _unsorted shouldn’t be necessary. _unsorted should be set up in the class constructor, and if there’s a problem, it should be diagnosed there… not over-and-over in every member function.

The next chunk is the bit that resets _sorted:

  const int numbers_count = _unsorted.size();
  _sorted.clear();
  _sorted.insert(_sorted.end(), _unsorted.begin(), _unsorted.end());

The first line is wrong. int is not the right type, and you risk subtle bugs by using it. The correct type is std::vector<int>::size_type. But of course, you can just use auto. If you used auto all the time… which you should… it will automatically fix several bugs in your code.

The next two lines first clear the vector, then fill with data. Okay, but… you could just have done:

_sorted.assign(_unsorted.begin(), _unsorted.end());

That will replace all the existing content with the contents of _unsorted.

Or, even simpler:

_sorted = _unsorted;

Yeah, that’s all you need.

So this is what we have:

void Sorter::run_std_sort(std::filesystem::path const& output_filename)
{
   /* 
   * Sorts an array with sort() function from
   * C++ Standard Library - from <algorithm> header
   *
   * :param output_filename: file name with sorted numbers
  */

  const auto numbers_count = _unsorted.size();
  _sorted = _unsorted;

  {
    Timer t("STD Sort", numbers_count);

    std::sort(_sorted.begin(), _sorted.end());
  }

  _save_numbers_to_file(output_filename);
}

But as I have already mentioned, you don’t need _sorted at all, and you could simply refactor _save_numbers_to_file() to take the sorted data as an argument (although, _save_numbers_to_file() should probably be a separate function, outside of the class), which would allow you to make the entire function const:

void Sorter::run_std_sort(std::filesystem::path const& output_filename) const
{
   /* 
   * Sorts an array with sort() function from
   * C++ Standard Library - from <algorithm> header
   *
   * :param output_filename: file name with sorted numbers
  */

  const auto numbers_count = _unsorted.size();
  auto sorted = _unsorted;

  {
    Timer t("STD Sort", numbers_count);

    std::sort(sorted.begin(), sorted.end());
  }

  _save_numbers_to_file(output_filename, sorted);
}

Or even simpler:

void Sorter::run_std_sort(std::filesystem::path const& output_filename) const
{
   /* 
   * Sorts an array with sort() function from
   * C++ Standard Library - from <algorithm> header
   *
   * :param output_filename: file name with sorted numbers
  */

  auto sorted = _unsorted;

  {
    Timer t("STD Sort", sorted.size());

    std::sort(sorted.begin(), sorted.end());
  }

  _save_numbers_to_file(output_filename, sorted);
}

All of your test functions should take this form, with the only differences being the name of the algorithm, and the actual function called. By which I mean: none of those functions should have the sort algorithm implemented in-place. That’s bad. It makes the sort algorithms impossible to test. The sort algorithms should all be separate functions.

All of your sort algorithms could have the same format:

template <std::random_access_iterator I, std::sentinel_for<I> S>
auto bubble_sort(I first, S last) -> void
{
    // ...
}

Let’s start with bubble sort:

template <std::random_access_iterator I, std::sentinel_for<I> S>
auto bubble_sort(I first, S last) -> void
{
    /*
    bool swapped = false;

    for (int i = 0; i < numbers_count - 1; i++) {
      swapped = false;
      for (int j = 0; j < numbers_count - i - 1; j++) {
        if (_sorted[j] > _sorted[j+1]) {
          // Swap places
          _swap(&_sorted[j], &_sorted[j+1]);
          swapped = true;
        }
      }
      if (swapped == false) {
          // Array sorted
          break;
      }
    }
    */
}

For starters, that bool doesn’t need to exist outside of the loop.

Next, let’s convert that loop to use iterators rather than numbers. Why? Well, for starters, your loop is buggy. It uses int. That’s wrong. What’s right? Well that’s a good question. It is possible to figure that out… but really, really hard. And in any case, iterators are far more powerful and flexible.

So, for example:

template <std::random_access_iterator I, std::sentinel_for<I> S>
auto bubble_sort(I first, S last) -> void
{
    for (auto i = first; i != last; ++i)
    {
        auto swapped = false;

        for (auto j = first; j < i; ++j)
        {
            if (*j < *(j + 1))
            {
                std::ranges::iter_swap(j, j + 1);
                swapped = true;
            }
        }

        if (swapped = true)
            break;
    }
}

The same idea applies to all the other sort functions you want to test, but I won’t repeat the points over and over.

In summary:

  • You have a god object. It needs to be broken up into individual functional parts.
  • The input and output operations should probably be separate functions.
  • Every one of the sort functions should be a separate function.
  • The timer could be more flexible; you could make it reusable by using a callback in the destructor.
  • The test function could be more flexible, you could make a single test function that takes the sort function to test as an argument, and reuse that.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Now that's an hour of your life you aren't going to get back !! \$\endgroup\$
    – Mr R
    May 3, 2021 at 4:32
  • \$\begingroup\$ Insane answer. I appreciate the effort and of course I will try to make changes, looks like - everywhere \$\endgroup\$
    – Giovacho
    May 3, 2021 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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