Реализация сортировки слиянием в c ++ с использованием векторов - PullRequest
Новая
       10

Реализация сортировки слиянием в c ++ с использованием векторов

0 голосов
/ 17 июня 2020

Я пытаюсь реализовать сортировку слиянием с использованием векторов в C ++, это следующий код, который я выполняю: 

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &a, int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    
    int L[n1], R[n2];
    for (i = 0; i < n1; i++) {
        L[i] = a[l + i];
    }
    for (j = 0; j < n2; j++) {
        L[j] = a[m + 1 + j];
    }
    i = 0;
    j = 0;
    k = l;     //merged array
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        a[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        a[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int> &a, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        merge(a, l, m, r);
    }
}

int main() {
    int n;
    std::cin >> n;
    vector<int> a(n);
    for (int i = 0; i < a.size(); i++) {
        cin >> a[i];
    }
    mergeSort(a, 0, a.size() - 1);
    for (int i = 0; i < a.size(); i++) {
        cout << a[i];
    }
}

Когда я выполняю это и ввожу любые значения, я получаю значения мусора, возвращаемые в массив, a[i] = 7405024, Выдает ли код ошибку из-за того, что я не могу изменить значения вектора на месте, или есть что-то еще.

Ответы [ 5 ]

2 голосов
/ 17 июня 2020

Проблема в функции merge 

for(j=0;j<n2;j++)
{
    R[j]=a[m+1+j]; // not L[j]
}

Поскольку вы реализуете использование векторов, предложите также изменить L и R на векторы. VLA не поддерживаются C ++ по умолчанию. Некоторые компиляторы могут принять, но должны избегать использования в целом. 

std::vector<int> L(n1);
std::vector<int> R(n2);
1 голос
/ 24 июля 2020

Проблема заключается в вашей инициализации R. Вместо того, чтобы писать циклы для копирования в L и R, вы можете просто инициализировать их напрямую. 

std::vector<int> L(a.begin() + l, a.begin() + m + 1);
std::vector<int> R(a.begin() + m + 1, a.begin() + r + 1);

Обратите внимание, что проще просто использовать итераторы везде. 

using iter = std::vector<int>::iterator;

void merge(iter l, iter m, iter r) {
    std::vector<int> L(l, m);
    std::vector<int> R(m, r);
    
    iter i = L.begin();
    iter j = R.begin();
    while (i != L.end() && j != R.end()) {
        if (*i < *j) {
            *l = *i;
            i++;
        } else {
            *l = *j;
            j++;
        }
        l++;
    }

    std::copy(i, L.end(), l);
}

void mergeSort(iter l, iter r) {
    std::size_t d = std::distance(l, r);
    if (d > 1) {
        iter m = l + (d / 2);
        mergeSort(l, m);
        mergeSort(m, r);
        merge(l, m, r);
    }
}

int main() {
    std::size_t n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int & i : a) {
        std::cin >> i;
    }
    mergeSort(a.begin(), a.end());
    for (int i : a) {
        std::cout << i;
    }
}

Обратите внимание, что вы можете продвигаться вперед l, пока не найдете элемент, упорядоченный после *m перед инициализацией L, что сэкономит некоторое копирование.

1 голос
/ 17 июня 2020

Одно очевидное изменение, которое я вижу, это 

IN merge() function

for(j=0;j<n2;j++)
{
    R[j]=a[m+1+j];
}

, поскольку эти значения должны храниться в RIGHT векторе.

0 голосов
/ 24 июля 2020

Основная проблема в вашем коде - вы вообще не инициализируете R. В инициализации l oop есть простая опечатка, вероятно, ошибка вырезания и вставки: L[j] = a[m + 1 + j]; должно быть 

R[j] = a[m + 1 + j];

Обратите внимание, что в C ++ идиоматически c указать фрагмент с помощью индекс первого включенного элемента и индекс последнего исключенного элемента. Это соглашение, используемое в C, Python и многих других языках, позволяет использовать более простой и универсальный код c, вы можете указать пустой фрагмент с помощью l == h. Это также менее подвержено ошибкам, поскольку +1 / -1 корректировки не требуются, и можно безопасно использовать типы индексов без знака, такие как size_t.

Наконец, int L[n1], R[n2]; - это объявление C99, которое является расширение до C ++. Даже в средах, где поддерживаются VLA, автоматическое выделение c хранилища вызовет переполнение стека для достаточно больших наборов. Вы должны использовать vector для этих временных массивов.

Эти векторы могут быть инициализированы непосредственно из векторного среза, что позволяет избежать циклов копирования, подверженных ошибкам: 

vector<int> L(a.begin() + l, a.begin() + m);
vector<int> R(a.begin() + m, a.begin() + r);

Вот измененный версия: 

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &a, size_t l, size_t m, size_t r) {
    vector<int> L(a.begin() + l, a.begin() + m);
    vector<int> R(a.begin() + m, a.begin() + r);

    size_t i = 0;
    size_t j = 0;
    size_t k = l;     // index into the merged vector slice
    size_t n1 = m - l;
    size_t n2 = r - m;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k++] = L[i++];
        } else {
            a[k++] = R[j++];
        }
    }
    while (i < n1) {
        a[k++] = L[i++];
    }
    // the last loop in redundant as the remaining elements from R are already at
    // the end of a
}

void mergeSort(vector<int> &a, size_t l, size_t r) {
    if (r - l >= 2) {
        size_t m = l + (r - l) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m, r);
        merge(a, l, m, r);
    }
}

int main() {
    size_t n;
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); i++) {
        cin >> a[i];
    }
    mergeSort(a, 0, a.size());
    for (size_t i = 0; i < a.size(); i++) {
        cout << a[i];
    }
    return 0;
}
0 голосов
/ 24 июля 2020

Вы можете реализовать сортировку слиянием, используя следующий код: 

vector<int> merge(vector<int> l,vector<int> r)
        {
    
       vector<int> res;
            
            int i=0;
            int j=0;
            while(i!=l.size() && j!=r.size())
            {
                if(l[i]<=r[j])
                {
                    re.push_back(l[i++]);
                }
                else
                {
                    re.push_back(r[j++]);
                }
            }
            
            while(i!=l.size())
                re.push_back(l[i++]);
            
            while(j!=r.size())
                re.push_back(r[j++]);
            
            return res;
        }
        
        
        vector<int> merge_d(vector<int>&A, int s,int e)
        {
            if(s-e==0)
            {
                vector<int> t;
                t.push_back(A[s]);
                return t;
            }
        
            int m=(s+e)/2;
            
            vector<int> l;
            vector<int> r;
            l=merge_d(A,s,m);
            r=merge_d(A,m+1,e);
            
            return merge(l,r);
        }
...