Как реализовать сортировку слияния из "Введение в алгоритмы" Cormen and Co

Ответ 1

В коде есть две проблемы.

Во-первых, вам нужно уточнить, что означают параметры, которые вы передаете. Внутри merge_sort это выглядит как p - это первый элемент, который нужно отсортировать, а r - последний элемент для сортировки. Но, где вызывается merge_sort, в основном передается 0 и SIZE. Здесь 0 - это первый элемент, который нужно сортировать, но SIZE не может быть последним элементом, поскольку он (предположительно) содержит число элементов, которые нужно отсортировать. В вашем примере вы передаете 8, но последний элемент для сортировки - это 7. Поэтому решите, хотите ли вы изменить merge_sort, так что r - это количество элементов или вы хотите изменить main, чтобы передать SIZE-1. Аналогично, в слиянии p, кажется, является первым элементом для слияния, q является последним элементом первого диапазона (так что q + 1 является первым из второго), а r является последним элементом второго диапазона. Но когда вы копируете из array_of_integers в right_array, вы копируете из q + j. Когда j равно нулю, это копирует последний элемент первого диапазона, но вы хотите получить первый элемент второго диапазона. Поэтому вам нужно прояснить эти применения индексов. (Также вам нужны только n1 и n2 элементы для left_array и right_array, а не n1 + 1 и n2 + 1.) Также проверьте цикл на k, for(k = p; k < r; k++). Каким должно быть условие продолжения этого цикла?

Два, когда вы объединяете left_array и right_array, вы не учитываете тот факт, что массив может быть пустым (поскольку все элементы были ранее скопированы из него), поэтому сравнение left_array [i] с right_array [j] не работает, потому что я или j указывает элемент вне поля left_array или right_array, соответственно. Например, если я достиг своего предела (n1), то вы не должны сравнивать. Вместо этого вы должны просто взять элемент из right_array.

Ответ 2

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

import java.util.*;
class MergeSort
{

    public static void main(String args[])
    {
        int testArray[] = {1,3,5,3,1,7,8,9};
        mergeSort(testArray,0,testArray.length-1);
        System.out.println(Arrays.toString(testArray));
    }

    protected static void mergeSort(int arr[], int p, int r)
    {
        int q;
        if (p<r)
        {
            q = (p+r)/2;
            mergeSort(arr,p,q);
            mergeSort(arr, q+1, r);
            merge(arr,p,q,r);   
        }   
    }

    protected static void merge(int arr[], int p, int q, int r)
    {    
        int n = q-p+1;
        int m = r-q;

        int L[] = new int[n+1];
        int R[] = new int[m+1];
        int i,j,k;

        for(i=0; i< n; i++)
        {
            L[i] = arr[p+i];    
        }
        for(j=0; j< m; j++)
        {
            R[j] = arr[q+j+1];    
        }

        L[n] = Integer.MAX_VALUE;
        R[m] = Integer.MAX_VALUE;

        i = 0;
        j = 0;
        for(k = p; k<= r; k++)
        {

            if( L[i]<=R[j])
            {
                arr[k] = L[i];
                i = i+1;
            }
            else
            {
                arr[k] = R[j];
                j = j+1;

            }           
        }
    }
}

Ответ 3

This one worked for me

    // MergeSortRevisionAgain.cpp : Defines the entry point for the console application.
//Understanding merge sort
#include <iostream>

using std::cout;
using std::endl;


//The declaration of the merge sort function
void merge(int A[], int p, int q, int r);
int* mergeSort(int A[], int p, int r);


int main()
{

    /*My Code to test for the merge sort*/
    int myArray[]{ 2,3,5,7,1,4,7,9};
    int lengthOfArray = sizeof(myArray) / sizeof(myArray[1]);
    int* sortedOutput = mergeSort(myArray, 0, lengthOfArray-1);

    for (int i = 0; i <lengthOfArray; i++)
    {
        cout << sortedOutput[i] << " ";
    }

    cout << endl;


    return 0;
}


void merge(int A[], int p, int q, int r)
{
    //Declaration of number of variable in each half
    int n1 = q - p + 1;                                                             //1. n1 = q - p + 1
    int n2 = r - q;                                                                 //2. n2 = r-q

    //Declaration of left and right part of the array
    int* leftArray= new int[n1+1] ;                                                 //3. Let L[1...n1+1] and ... 
    int* rightArray= new int[n2+1] ;                                                //... R[1...n2+1] be new arrays

    //Entering the for loop for the left side
    for (int i = 0; i < n1; i++)                                                    //4.for i = 1 to n1 NB(change i to 0 since index in c++ starts from 0)
    {
        leftArray[i] = A[p + i ];                                                   //5. L[i] = A[p+i-1] NB(change to A[p+i] since "i" was changed to 0 hence A[p,...,p+i)
    }

    //Entering the for loop for the right side
    for (int  j = 0; j < n2; j++)                                                   //6. for j = 1 to n2 NB(change j j= 0 since index in c++ starts from 0)
    {
        rightArray[j] = A[q + j+1];                                                 //7. R[i] = A[q + j ] NB(change to A[q+j+1] since "j" was changed to 0  hence A[q+1,...q+1+j]
    }

    leftArray[n1] = 999;                                                            //8. Set L[n1+1] = sentinel NB last value in leftArray will be the sentinel
    rightArray[n2] = 999;                                                           //9. Set L[n2 + 2] = sentinel NB last value in rightArray will be the sentinel

    int i = 0;                                                                      //10. i = 1 change to i = 0 since index starts from 0 in c++
    int j = 0;                                                                      //11. j = 1 change to j = 0 since index starts from 0 in c++

    for (int k = p; k <= r; k++)                                                    //12. for k = p to r - change as specified in code since index of array p = 0, r = lengthofArray - 1
    {
        if (leftArray[i] <= rightArray[j])                                          //13. L[i] <= R[j]
        {
            A[k] = leftArray[i];                                                    //14. A[k] = L[i]
            i = i + 1;                                                              //15. i = i + 1
        }
        else
        {
            A[k] = rightArray[j];                                                   //16. A[k] = R[j]
            j = j + 1;                                                              //17. j = j+1;
        }
    }

    delete leftArray;                                                               //18. Free allocated dynamic memory for leftArray
    leftArray = nullptr;                                                            //19. Set pointer to nullptr to prevent access to deleted memory
    delete rightArray;                                                              //20. Free allocated dynamic memory for rightArray              
    rightArray = nullptr;                                                           //21. Set pointer to nullptr to prevent access to deleted memory
}

int* mergeSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = floor((p + r) / 2);
        mergeSort(A, p, q );
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }

    return A;
}