Не работает сортировка слияния и разделения - PullRequest
Новая
       20

Не работает сортировка слияния и разделения

0 голосов
/ 04 января 2019

Вот код.Я просто сделал сортировку слиянием, используя алгоритм «Разделяй и властвуй», но он не работает, и я не нашел, почему.Я передаю неупорядоченный вектор, 0 и vector.size() в функцию mergeSort. 

#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");
}

1 Ответ

0 голосов
/ 04 января 2019

Могут быть и другие проблемы, но эту строку нужно исправить: 

        mergeSort(vec, middle + 1, right);

изменено на 

        mergeSort(vec, middle, right);

Я бы также предложил использовать имена начала и конца вместо левого и правого, чтобы соответствовать соглашению об именах, используемому для векторных итераторов, а также потому, что «правый» итератор или индекс указывает на «конец» вектора или массив, 1 после последнего элемента массива.

...