Это правильная реализация сортировки слиянием? - PullRequest
Новая
       38

Это правильная реализация сортировки слиянием?

0 голосов
/ 15 апреля 2019

В настоящее время я изучаю стратегию «разделяй и властвуй» для алгоритмов и решил, что сортировка слиянием - очень хороший пример, демонстрирующий стратегию.

У меня были некоторые проблемы с пониманием концепции, поэтому я решил попробовать реализовать ее самостоятельно.Я попробовал, и мне было интересно, что это правильная реализация сортировки слиянием. 

vector<int> mergeSort(vector<int> n) {
    if(n.size() == 1) {
        return n;
    } else if(n.size() == 2) {
        vector<int> newVector;
        newVector.reserve(2);
        if(n[0] < n[1]) {
            newVector.push_back(n[0]);
            newVector.push_back(n[1]);
        } else {
            newVector.push_back(n[1]);
            newVector.push_back(n[0]);
        }
        return newVector;
    } else {
        int endIndexLeft = floor(n.size() / 2);
        int startIndexRight = ceil(n.size() / 2);

        vector<int>::const_iterator first = n.begin();

        // divide into 2 vectors
        vector<int> L(first, first + endIndexLeft + 1);
        vector<int> R(first + endIndexLeft + 1, first + n.size());

        // recursive call on each
        L = mergeSort(L);
        R = mergeSort(R);


        // combine the resulting array accordingly
        vector<int> sorted;
        sorted.reserve(n.size());

        int index_l = 0, index_r = 0;

        for(int i=0; i<n.size(); i++) {
            if(index_l == L.size()) {
                sorted.push_back(R[index_r]);
                index_r++;
            } else if(index_r == R.size()) {
                sorted.push_back(L[index_l]);
                index_l++;
            } else if(L[index_l] < R[index_r]) {
                sorted.push_back(L[index_l]);
                index_l++;
            } else {
                sorted.push_back(R[index_r]);
                index_r++;
            }
        }
        return sorted;
    }
}

После некоторого тестирования кажется, что он генерирует правильный вывод (отсортированный вектор в порядке возрастания), но яне был уверен, что реализация показывает использование стратегии «разделяй и властвуй».Заранее спасибо!

[РЕДАКТИРОВАТЬ: понял, что мне даже не нужна часть n.size() == 2, поэтому я избавился от этого и отделил функцию слияния.] 

vector<int> mergeVector(vector<int> L, vector<int> R) {
    vector<int> combined;
    combined.reserve(L.size() + R.size());

    int index_l = 0, index_r = 0;

    for(int i=0; i<L.size() + R.size(); i++) {
        if(index_l == L.size()) {
            combined.push_back(R[index_r]);
            index_r++;
        } else if(index_r == R.size()) {
            combined.push_back(L[index_l]);
            index_l++;
        } else if(L[index_l] < R[index_r]) {
            combined.push_back(L[index_l]);
            index_l++;
        } else {
            combined.push_back(R[index_r]);
            index_r++;
        }
    }

    return combined;
}

vector<int> mergeSort(vector<int> n) {
    if(n.size() == 1) {
        return n;
    } else {
        int endIndexLeft = floor(n.size() / 2);

        vector<int>::const_iterator first = n.begin();

        // divide into 2 vectors
        vector<int> L(first, first + endIndexLeft);
        vector<int> R(first + endIndexLeft, first + n.size());

        // recursive call on each
        L = mergeSort(L);
        R = mergeSort(R);


        // combine the resulting arrays
        vector<int> sorted;
        sorted.reserve(n.size());
        sorted = mergeVector(L,R);

        return sorted;
    }
}
...