Реализация сортировки слиянием выдает неверные результаты

Question

Я пытаюсь реализовать сортировку слиянием в C ++ 14. Я написал полный код и несколько раз корректировал его на наличие логических сбоев, но не могу его найти.Но код выводит неправильный отсортированный массив, который иногда даже содержит повторяющиеся элементы и / или элементы, которые никогда не вводились в массив в первую очередь.

Вот мой код:

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
void merge_sort(vector<int>&, int, int);
void print_vector(vector<int>&);
void merge(vector<int>&, int, int, int);

int main() {
    int arr_len = 0;
    cout << "Enter the length of the array to be sorted: " << endl;
    cin >> arr_len;

    vector<int> arr(arr_len);

    cout << "Enter the elements of the array: " << endl;
    for (int i = 0; i < arr_len; i++) {
        int buff;
        cin >> buff;
        arr[i] = buff;
    }

    cout << "The elements entered in the unsorted vector are: " << endl;
    print_vector(arr);

    merge_sort(arr, 0, arr_len - 1);

    cout << "After Merge sorting, the elements in the vector are: " << endl;
    print_vector(arr);

    return 0;
}

void print_vector(vector<int>& arr) {
    for (auto itr = arr.begin(); itr != arr.end(); ++itr) {
        cout << *itr << " ";
    }
    cout << endl;
}

void merge_sort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;           // used this instead of (low + high) / 2 to avoid overflow problems
        merge_sort(arr, low, mid);                  // recursive call to merge_sort with high = mid's updated value
        merge_sort(arr, mid + 1, high);
        merge(arr, low, mid, high);                 // call to merge to sort and merge the fragmented arrays.
    }
}

void merge(vector<int>& arr, int low, int mid, int high) {
    int l_arr_len = mid - low + 1;
    int r_arr_len = high - mid;
    vector<int> l_arr(l_arr_len);
    vector<int> r_arr(r_arr_len);

    for (int i = 0; i < l_arr_len; i++) {        // initialise elements of temp_arr1 (l_arr) to 0.
        l_arr[i] = 0;
    }

    for (int i = 0; i < r_arr_len; i++) {        // initialise elements of temp_arr2 (r_arr) to 0.   
        r_arr[i] = 0;
    }

    for (int i = 0; i < l_arr_len; i++) {        // transfer elements from arr to l_arr, upto length of the fragmented l_arr.
        l_arr[i] = arr[low + i];
    }

    for (int i = 0; i < r_arr_len; i++) {        // transfer remaining elements from arr to r_arr, upto length of the fragmented r_arr.
        r_arr[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = 0;
    while (i < l_arr_len && j < r_arr_len) {            // compare and replace elements in the mother array arr
        if (l_arr[i] <= r_arr[j]) {                      // smallest element goes first
            arr[k++] = l_arr[i++];
        } else {
            arr[k++] = r_arr[j++];
        }
    }

    while (i < l_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = l_arr[i++];
    }

    while (j < r_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = r_arr[j++];
    }
}

Длявходной массив элементов [2, 9, 4, 5, 7], правильный отсортированный результат был бы: [2, 4, 5, 7, 9].

Но моя реализация выводит: [5, 5, 7, 7, 9].Я не понимаю, откуда появились повторяющиеся элементы и почему они заменили оригинальные элементы.Несмотря на то, что я пытался добавить комментарии почти к заявлениям для облегчения доступа к SO-сообществу, некоторые из них могут быть избыточными.

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

Заранее спасибо!:)

Answer 1

Основная проблема была обнаружена другими, k должен быть инициализирован как low вместо 0.

Есть еще вопросы, на которые стоит обратить внимание:

• правильный тип для значений и размеров индекса массива - size_t, а не int, который может иметь гораздо меньший диапазон.

• Передача индекса последнего элемента вместо исключенной верхней границы создает громоздкий код с корректировкой индекса.

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

• print_vector должен принимать const ссылку.

Вот модифицированная версия:

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
void merge_sort(vector<int>&, size_t, size_t);
void merge(vector<int>&, size_t, size_t, size_t);
void print_vector(const vector<int>&);

int main() {
    size_t arr_len = 0;
    cout << "Enter the length of the array to be sorted: " << endl;
    cin >> arr_len;

    vector<int> arr(arr_len);

    cout << "Enter the elements of the array: " << endl;
    for (size_t i = 0; i < arr_len; i++) {
        cin >> arr[i];
    }

    cout << "The elements entered in the unsorted vector are: " << endl;
    print_vector(arr);

    merge_sort(arr, 0, arr_len);

    cout << "After Merge sorting, the elements in the vector are: " << endl;
    print_vector(arr);

    return 0;
}

void print_vector(const vector<int>& arr) {
    for (auto itr = arr.begin(); itr != arr.end(); ++itr) {
        cout << *itr << " ";
    }
    cout << endl;
}

void merge_sort(vector<int>& arr, size_t low, size_t high) {
    if (high - low > 1) {
        size_t mid = low + (high - low) / 2;    // used this instead of (low + high) / 2 to avoid overflow problems
        merge_sort(arr, low, mid);              // recursive call to merge_sort with high = mid's updated value
        merge_sort(arr, mid, high);
        merge(arr, low, mid, high);             // call to merge to sort and merge the fragmented arrays.
    }
}

void merge(vector<int>& arr, size_t low, size_t mid, size_t high) {
    size_t l_arr_len = mid - low;
    size_t r_arr_len = high - mid;
    vector<int> l_arr(l_arr_len);
    vector<int> r_arr(r_arr_len);

    for (size_t i = 0; i < l_arr_len; i++) {    // transfer elements from arr to l_arr, upto length of the fragmented l_arr.
        l_arr[i] = arr[low + i];
    }
    for (size_t i = 0; i < r_arr_len; i++) {    // transfer remaining elements from arr to r_arr, upto length of the fragmented r_arr.
        r_arr[i] = arr[mid + i];
    }

    size_t i = 0, j = 0, k = low;
    while (i < l_arr_len && j < r_arr_len) {    // compare and replace elements in the mother array arr
        if (l_arr[i] <= r_arr[j]) {             // smallest element goes first
            arr[k++] = l_arr[i++];
        } else {
            arr[k++] = r_arr[j++];
        }
    }
    while (i < l_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = l_arr[i++];
    }
    while (j < r_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = r_arr[j++];
    }
}

Answer 2

В функции слияния инициализируйте k как низкий, а не ноль:

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

Я только что заметил, что комментарий Кенни Острома, вероятно, касается внесения этого изменения.

Answer 3

В моем коде, в частности, в функции void merge(...) я инициализировал переменную от k до 0.Эта переменная k должна отслеживать, где в материнском массиве arr размещен отсортированный элемент в зависимости от его значения.

В результате получилось то, что независимо от того, какой фрагмент материнского массива arr при сортировке и объединении элементов из разных фрагментов массива k жестко закодировано в 0, первый (уже отсортированный) элемент arr заменяется следующим элементом из любого изфрагменты массива, удовлетворяющие условию.Таким образом, массив будет заполнен в конце концов, и программа будет корректно завершать работу, но не раньше, чем вводить дубликаты в частично отсортированный массив, дубликаты, получаемые при замене элемента arr[k++] любым из фрагментов массива: l_arr илиr_arr.Конечно, это неправильно в соответствии с принципом сортировки слиянием, поскольку шаблон слияния элементов массива должен поддерживаться.Вероятно, это трудно визуализировать, поэтому вот представление сортировки слиянием для справки:

Итак, вот исправление: k должно бытьинициализируется low вместо 0.Таким образом, шаблон сортировки слиянием сохраняется, соответствующие элементы из соответствующих фрагментов рекурсивно объединяются для формирования отсортированного массива.

Это исправление было предложено Кенни Остром и rcgldr .Большое спасибо им обоим!