7
\$\begingroup\$

I'm new to algorithms. To be honest I am not really sure if my implementation is right. However, the output is sorted correctly in ascending order so perhaps it's correct. Please feel free to give critiques and suggest how to improve its overall efficiency.

  1. How can improve its performance and readability?
  2. Have I used bad practice?
  3. Did I implement the algorithm correctly?

Main.cpp

#include <vector>
#include <iostream>
using namespace std;
void sort(vector<int> & bar);
void mergeSort(vector<int>&left,vector<int>& right,vector<int>& bars);

int main() {
    vector<int> nums;
    for (size_t i = 0; i < 11; i++)
        nums.push_back(rand() % 1000);

    sort(nums);

    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] <<endl;
    system("pause");
    return 1;
}
void sort(vector<int> & bar) {
    if (bar.size() <= 1) return;

    int mid = bar.size() / 2;
    vector<int> left;
    vector<int> right;

    for (size_t j = 0; j < mid;j++)
        left.push_back(bar[j]);
    for (size_t j = 0; j < (bar.size()) - mid; j++)
        right.push_back(bar[mid + j]);

    sort(left);
    sort(right);
    mergeSort(left, right, bar);
}
void mergeSort(vector<int>&left, vector<int>& right, vector<int>& bars)
{
    int nL = left.size();
    int nR = right.size();
    int i = 0, j = 0, k = 0;

    while (j < nL && k < nR) 
    {
        if (left[j] < right[k]) {
            bars[i] = left[j];
            j++;
        }
        else {
            bars[i] = right[k];
            k++;
        }
        i++;
    }
    while (j < nL) {
        bars[i] = left[j];
        j++; i++;
    }
    while (k < nR) {
        bars[i] = right[k];
        k++; i++;
    }
}

Output

output

\$\endgroup\$
  • \$\begingroup\$ Why not simply using std::sort and std::merge? \$\endgroup\$ – πάντα ῥεῖ Jul 8 '17 at 6:50
  • 6
    \$\begingroup\$ Because I'm learning to implement common sorting algorithm and I want to know how merge sort works. \$\endgroup\$ – Emmaaaaaaa Jul 8 '17 at 7:04
  • \$\begingroup\$ Well, reinventing the wheel could probably considered bad practice. \$\endgroup\$ – πάντα ῥεῖ Jul 8 '17 at 7:23
  • \$\begingroup\$ Yes, I'm reinventing the wheel but in a positive way for learning purposes only. \$\endgroup\$ – Emmaaaaaaa Jul 8 '17 at 7:54
  • 1
    \$\begingroup\$ Don't paste pictures. Just run the code and copy and paste the output. You can prefix output with > in markdown to get it highlighted correctly. \$\endgroup\$ – Martin York Jul 8 '17 at 16:08
11
\$\begingroup\$

Overview

Good first try. It seems like it works. But currently it only works for vectors and ints.

Some thoughts for improving the algorithm in the future.

If you look at most C++ algorithms they don't take a container as a parameter (vector<> is a container), instead they take iterators into the container. That way the algorithm can be used on any type of container (or a sub range of a container).

Also be using templates you can make the code work with any type that supports the comparison operator less than operator<.

Code Review

Vertical White Space

Nothing wrong here:

#include <vector>
#include <iostream>
using namespace std;
void sort(vector<int> & bar);
void mergeSort(vector<int>&left,vector<int>& right,vector<int>& bars);

But it seems a bit cramped all together. If you add some judicious vertical white space you can make it easier to read. I tend to separate logically distinct parts with an extra blank line. Like this:

#include <vector>
#include <iostream>

using namespace std;

void sort(vector<int> & bar);
void mergeSort(vector<int>&left,vector<int>& right,vector<int>& bars);

Using namespace

Please don't do this:

using namespace std;

Yes. All the C++ text books use it. But they are trying to save space because a book only has so much space available for printing. In real programs this is actually quite dangerous and should be avoided.

The reason the Standard namespace is called std is so that prefixing members with std:: is not a big hurdle.

Read this for details: Why is “using namespace std” considered bad practice?

Prefer prefix ++

    for (size_t i = 0; i < 11; i++)

OK. In this case (and a lot of cases) it makes no difference if you use the prefix or postfix version. But it can make a difference when the object being incremented is an object (lot of container iterators). A lot of the time when modifying C++ code, you change the type in one place and the type changes will cascade through your code, so it is best to always use the most efficient version no matter what the current type is. So in these cases prefer to use the prefix increment.

If you always use prefix ++ then you will always have the optimal increment.

    for (auto i = 0; i < 11; ++i) // Also note the use of auto

rand() is not very random

        nums.push_back(rand() % 1000);

This is the C random number generator. C++ has its own random number generator that is much better.See here for interface and example: http://en.cppreference.com/w/cpp/numeric/random

Also note that because you don't use srand() you will get the same sequence of numbers every time (which is a useful feature for testing).

Prefer Range based for:

When iterating over a container (something that supports begin/end) prefer to use the range based for.

    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] <<endl;

    for (auto const& num: nums) {
        cout << num << "\n";
    }

Always use {} around sub blocks

I know it looks safe not to bother in places like this:

    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] <<endl;

But it is a common type of error to add an extra indent line or use a function that happens to be multiple statement macro. To avoid these issues simply add braces.

    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i] << "\n";
    }

Prefer '\n' over std::endl

The main difference in the two is that std::endl in addition to adding \n to the stream will flush the stream. The stream will already auto flush at the optimal times and forcing a manual flush will only result in a degradation in performance.

Don't use system dependent code

    system("pause");

This only works on windows. Easier to just ask the user for input.

    std::cout << "Hit Return to continue\n";
    std::string line;
    std::getline(std::cin, line);

Don't need return in main

    return 1;

The main() function is special. If you don't specify a return value then the compiler will auto generate one for you that returns 0.

So it has become traditional for simple applications that never fail to have no return statement as an indication that this application will never fail. If I see a return statement at the end of main I will look through main to find the other return statements that indicate a failure state.

You should also note that a return value of non zero from main() is an indication to the operating system that the application failed. So return 1; lets the OS know your application failed and can potentially cause it to throw up an error screen to the user.

The & and * are part of the type

The & and * are part of the type in C++ and usually placed syntactically with the type information.

void sort(vector<int> & bar) {

Putting a space between the type and the & just looks strange.

void sort(vector<int>& bar) {

Don't run if statement together

    if (bar.size() <= 1) return;

Prefer to use two lines for this (and the sub block brace).

    if (bar.size() <= 1) {
        return;
    }

When debugging the code and stepping through it this will make your life easier.

Use reserve

    int mid = bar.size() / 2;
    vector<int> left;
    vector<int> right;

To prevent potential re-allocation of the underlying storage you can use reserve to make sure these vectors have enough space.

    left.reserve(mid);
    right.reserve(bar.size() - mid);

Prefer to use standard algorithms rather than manual loops.

    for (size_t j = 0; j < mid;j++)
        left.push_back(bar[j]);
    for (size_t j = 0; j < (bar.size()) - mid; j++)
        right.push_back(bar[mid + j]);

There is a standard copy. You should check out the standard for a list of helpful algorithms. http://en.cppreference.com/w/cpp/algorithm

    std::copy(std::begin(bar), std::begin(bar) + mid, std::back_inserter(left));
    std::copy(std::begin(bar) + mid, std::end(bar), std::back_inserter(right));

One Line Per Variable (and use meaningful names)

    int i = 0, j = 0, k = 0;

There is a big push for self documenting code. Part of this is to make sure that you can understand what is happening by reading the names of the variables and the functions. So names like i,j,k are not meaningful (unless you happen to have done a lot of fortran programming).

    int leftLoop  = 0;
    int rightLoop = 0;
    int barLoop   = 0;

Stable Sort

An important property of sorting is to try and keep equal object in the same relative order after the sort. A sort that does this is called a stable sort. This means if two values are equal you should choose the one from the left rather than the right vector.

        // This is not stable.
        // When the objects are equal you select the one from the right.
        // To make this sort stable change to use `<=`
        if (left[j] < right[k]) {
            bars[i] = left[j];
            j++;
        }
        else {
            bars[i] = right[k];
            k++;
        }

Simplify using Ternary

This is a dangerous piece of advice. Use it judiciously as overuse can make the code harder to read. But sometimes it is useful to use ? : operator as it can make the code simpler and easier to read.

But sometimes it is useful to use the ternary operator instead of and if then else block. I think this is one of these places (others will disagree so use if you like).

        bars[i] = (left[j] <= right[k]) 
                    ? left[j++]
                    : right[k++];
        ++i;

Advanced Section

I would redesign this to use templates and iterators.

template<typename I>
void sort(I begin, I end);
template<typename I>
void merge(I leftBegin, I leftEnd, I rightBegin, I rightEnd, I destination);

When you start using templates and don't know what the type being sorted is things can get complicated because the underlying type may be very expensive to copy around. So you should prefer to move object rather than copy objects (for integers it makes no difference so I did not mention it above).

for(auto& val: container) {
    dest.emplace_back(std::move(val));
}

Also there is a move algorithm for moving objects from one container to another.

std::move(std::begin(container), std::end(container), std::back_inserter(dest));

You allocate a lot of temporary vectors (there is a left/right in each recursive call to sort()). You can pre-allocate these vectors and re-use them throughout your recursion (with a tiny bit of extra work).

\$\endgroup\$
  • \$\begingroup\$ Excellent review of the coding-style, though I disagree about making every single statement a block-statement. Also, you are a bit lean on optimizing allocation and all. By the way, I'm sure you wanted to use range instead of container in the section about range based for... \$\endgroup\$ – Deduplicator Jul 8 '17 at 19:00
  • \$\begingroup\$ Thank you. I really appreciate your answer. May I ask why is that I'm getting an error when I used std::back_inserter(left)? It says namespace "std" has no member "back_inserter". \$\endgroup\$ – Emmaaaaaaa Jul 9 '17 at 3:32
  • \$\begingroup\$ You probably forgot its header file. en.cppreference.com/w/cpp/iterator/back_inserter You will find it in <iterator> \$\endgroup\$ – Martin York Jul 9 '17 at 3:46
  • \$\begingroup\$ is there any difference between left[leftLoop++] and left[leftLoop]; leftLoop++; ? \$\endgroup\$ – Emmaaaaaaa Jul 12 '17 at 3:20
  • \$\begingroup\$ @Emmaaaaaaa: As written none (even if you add an assignment in there). Though I would change your second version to left[leftLoop]; ++leftLoop;. The reason is that post increment is not always as efficient as prefix increment. And given the choice between postfix and prefix you should choose prefix. But in left[leftLoop++] you have to use postfix otherwise it changes the meaning of the statement. \$\endgroup\$ – Martin York Jul 12 '17 at 4:45
2
\$\begingroup\$

There are some common errors you should try to avoid:

In you sort function you already know the size of the vectors, so you can reserve the memory for them beforehand. This prevents frequent reallocations.

left.reserve(mid);
right.reserve(bar.size()-mid);

Even better, you can directly construct the sub vectors from the midpoint.

auto midPoint = std::next(bar.begin(), std::distance(bar.begin(), bar.end())/2);
left = std::vector<int>(bar.begin(), midpoint);
right = std::vector<int>(std::next(midpoint, 1), bar.end());
\$\endgroup\$
1
\$\begingroup\$

How can improve its performance and readability?

What comes to performance, you can allocate an auxiliary vector only once and keep the original range and that very auxiliary vector and keep swapping their roles:

template<typename RandomAccessIterator1, typename RandomAccessIterator2>
void merge_sort_impl(RandomAccessIterator1 source_begin,
                     RandomAccessIterator1 source_end,
                     RandomAccessIterator2 target_begin,
                     RandomAccessIterator2 target_end)
{
    auto range_length = std::distance(source_begin, source_end);

    if (range_length < 2)
    {
        return;
    }

    auto left_chunk_length     = range_length >> 1;
    auto source_left_chunk_end = source_begin;
    auto target_left_chunk_end = target_begin;

    std::advance(source_left_chunk_end, left_chunk_length);
    std::advance(target_left_chunk_end, left_chunk_length);

    merge_sort_impl(target_begin,
                    target_left_chunk_end,
                    source_begin,
                    source_left_chunk_end);

    merge_sort_impl(target_left_chunk_end,
                    target_end,
                    source_left_chunk_end,
                    source_end);

    std::merge(source_begin,
               source_left_chunk_end,
               source_left_chunk_end,
               source_end,
               target_begin);
}

template<typename RandomAccessIterator>
void merge_sort(RandomAccessIterator begin, RandomAccessIterator end)
{
    auto range_length = std::distance(begin, end);

    if (range_length < 2)
    {
        return;
    }

    using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
    std::vector<value_type> aux(begin, end);
    merge_sort_impl(aux.begin(), aux.end(), begin, end);
}

With the above version, you can sort not just vectors, but arrays as well.

If you compile with -O3 optimization flag, you may see something like:

OP mergesort in 1007 milliseconds.
coderodde mergesort in 139 milliseconds.
std::sort in 95 milliseconds.
Algorithms agree: true

Did I implement the algorithm correctly?

It seems that it is correct.

(You can find the demo here: https://gist.github.com/coderodde/2aefd7dbf09552f5857c29ab5260dff6)

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Hm, you know not all randomaccess-iterators are the same as vector-iterators? So, you need an additional template-argument for the aux-range. \$\endgroup\$ – Deduplicator Jul 8 '17 at 13:26
  • \$\begingroup\$ This is not a review but rather just a presentation of an alternative solution, correct? \$\endgroup\$ – yuri Jul 8 '17 at 13:40
  • \$\begingroup\$ @yuri Fair enough. I will revisit my answer tomorrow. \$\endgroup\$ – coderodde Jul 8 '17 at 14:09

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.