-1

Here is the code. I simply did a merge sorting using a Divide and Conquer algorithm but it doesn't work and i haven't found why. I'm passing an unordered vector, 0 and vector.size() to the mergeSort function.

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
void directInsertion(std::vector<T>& vec, int start, int end);

template<typename T>
void merge (std::vector<T>& vec, int left, int middle, int right);

template<typename T>
void mergeSort(std::vector<T>& vec, int left, int right);

template<typename T>
void directInsertion(std::vector<T>& vec, int start, int end)
{
    T value = T();
    int i;
    int j;

    for(i = start + 1; i < end; ++i)
    {
        value = vec[i];
        for(j = i - 1; j >= 0 && !(vec[j] < value); --j)
            vec[j + 1] = vec[j];
        vec[j + 1] = value;
    }
}

template<typename T>
void mergeSort(std::vector<T>& vec, int left, int right)
{
    int length = right - left;

    if(length <= 3)
        directInsertion(vec, left, right);
    else
    {
        int middle = left + (length >> 1);
        mergeSort(vec, left, middle);
        mergeSort(vec, middle, right);
        merge(vec, left, middle, right);
    }
}

template<typename T>
void merge (std::vector<T>& vec, int left, int middle, int right)
{
    int length = right - left;
    int p = left;
    int q = middle + 1;

    std::vector<T> tmp;

    for(size_t l = 0; l < length; ++l) {
        if (p <= middle && (q >= right || vec.at(p) <= vec.at(q)))
            tmp.push_back(vec.at(p++));
        else
            tmp.push_back(vec.at(q++));
    }
    for(size_t l = 0; l < length; ++l)
        vec.at(left + l) = tmp.at(l);
}

void printMessage(bool passed, const char* message)
{
    if(passed)
        std::cout << message << "............... PASS" << std::endl;
    else
        std::cout << message << "............... FAIL" << std::endl;
}

void printVector(std::vector<int>& v)
{
    std::cout << "[";
    for(auto i: v)
        std::cout << " " << i << " ,";
    std::cout << "]";
}

int main()
{
    std::vector<int> v = {1, 2, 3, 4};
    std::vector<int> orderedVector = v;
    std::vector<int> aux;

    bool passed = true;

    do {
        aux = v;
        mergeSort(aux, 0, aux.size());
        if(aux != orderedVector)
        {
            printVector(aux);
            std::cout << " != ";
            printVector(orderedVector);
            std::cout << std::endl;
            passed = false;
        }
    } while(std::next_permutation(v.begin(), v.end()) && passed);

    printMessage(passed, "MERGE SORT");
}
SGodoy
  • 703
  • 1
  • 5
  • 13
  • 6
    This is a problem that should be solved by debugging. Using your favorite debugger (and/or) IDE, step through the code line by line, each time formulating your _expected_ result of a step before letting the code do it. If the line of code does something else than you expect, investigate there. Debugging like this is a crucial skill to have as a programmer, so use this opportunity! – Max Langhof Jan 04 '19 at 13:31
  • 3
    Did you run your code using a debugger? Compare your code with [the implementation here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c/24650627). What is the difference? Also, claiming that a function is working, thus you won't post the function many times ends up wasting a lot of time *if* the function that isn't posted is the faulty function. – PaulMcKenzie Jan 04 '19 at 13:31
  • @PaulMcKenzie If i weren't 100% sure that `directInsertion` is working i would have post it. I debugged the code and i changed a couple of things but still not working. – SGodoy Jan 04 '19 at 13:40
  • 5
    @Repikas *If i weren't 100% sure that directInsertion is working i would have post it* -- If I had a dollar for every post where the unposted "working code" was the actual problem, I would be a rich man. Please post a [mcve]. – PaulMcKenzie Jan 04 '19 at 13:46
  • @PaulMcKenzie I post it. Let's see if i have to pay you that dollar haha. – SGodoy Jan 04 '19 at 13:47
  • 1
    This isn't a bet. It is what is required for a [mcve]. We have no idea except your word that the unposted code works correctly. What is the test data? How are you calling your function? Where is your `main()` function that tests your merge sort? – PaulMcKenzie Jan 04 '19 at 13:49
  • @UmNyobe I changed it in mergeSort function and still not working. – SGodoy Jan 04 '19 at 13:49
  • @PaulMcKenzie Main function added, now it is complete, sorry and thanks for the advice. – SGodoy Jan 04 '19 at 13:56
  • 1
    @Repikas Your code fails for this simple `main()` program: `std::vector v = { 23, 1, 45, 0}; mergeSort(v, 0, v.size());`. Also, I suggest you use `at()` for *all* of your `vector` accesses instead of `[ ]`. If (when) the `std::out_of_range` exception is thrown, remove each call to `at()` until you isolate the one that is giving the issue. – PaulMcKenzie Jan 04 '19 at 14:04
  • 3
    I fixed the missing includes, missing print functions, and reordered the functions so it would run. Your example should run without my having to do that. I got a vector index out of range. I'm not saying where because you should get the same when you debug it, and that will be a lot more useful to you. – Kenny Ostrom Jan 04 '19 at 14:19
  • @PaulMcKenzie @KennyOstrom The index out of range is here `vec[p] <= vec[q]`, `vec[q]` to be precise. – SGodoy Jan 04 '19 at 14:27
  • 3
    also avoid name conflicts. "vector" isn't a wise choice for a variable name. But nice test case -- I would recommend you make it as small as you can and still get the error, so it will be easy to debug. – Kenny Ostrom Jan 04 '19 at 14:28
  • Consider std::vector data{ 2, 3, 1 }; Now try to write a merge call which will work. merge(data, 0, 1, 2) thinks it has 2 elements. merge(data, 0, 1, 3) gives the out of range condition. – Kenny Ostrom Jan 04 '19 at 14:38
  • @KennyOstrom I changed this line `if(p <= middle && (q > right || vec[p] <= vec[q]))` for this line `if(p <= middle && (q >= right || vec[p] <= vec[q]))` and now i don't get out of range but still failing the test because the vector is not sorted correctly. – SGodoy Jan 04 '19 at 15:26
  • When i try to sort [1, 3, 2, 4] it fails but doesn't throw out of range.. – SGodoy Jan 04 '19 at 16:12
  • 1
    Read the **first comment** please and do what @MaxLanghof says. – domen Jan 04 '19 at 16:14
  • See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. – Prune Jan 04 '19 at 17:04

1 Answers1

0

There may be other problems, but this line needs to be fixed:

        mergeSort(vec, middle + 1, right);

changed to

        mergeSort(vec, middle, right);

I would also suggest using the names begin and end instead of left and right, to be consistent with the naming convention used for vector iterators, and because the "right" iterator or index points to the "end" of a vector or array, 1 past the last element of the array.

rcgldr
  • 27,407
  • 3
  • 36
  • 61