12

我正在从 Cormen and Co. 学习算法，我在从他们的伪代码中实现合并排序时遇到问题。我通过以下方式编译它：

$ gcc -Wall -g merge_sort.c

我有一个问题，因为对于数字：

2 4 5 7 1 2 3 6

结果是：

1 2 2 3 3 4 5 5

我试图仔细阅读伪代码，但这对我没有帮助。我想知道我做错了什么。下面是我的代码：

#include <stdio.h>

#define SIZE 8

void merge(int *array_of_integers, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q; 
    int i, j, k;
    int left_array[n1 + 1];
    int right_array[n2 + 1];

    for (i = 0; i < n1; i++)
        left_array[i] = array_of_integers[p + i];
    for (j = 0; j < n2; j++)
        right_array[j] = array_of_integers[q + j];

    i = 0;
    j = 0;

    for (k = p; k < r; k++){
        if (left_array[i] <= right_array[j]) {
            array_of_integers[k] = left_array[i];
            i++;
        } else {
            array_of_integers[k] = right_array[j];
            j++;
        }   
    }
}

void merge_sort(int *array_of_integers, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(array_of_integers, p, q);
        merge_sort(array_of_integers, q + 1, r);
        merge(array_of_integers, p, q, r);
    }
}

void print_array(int *array_of_integers, int amout_of_integers) {
    int i;
    for(i = 0; i < amout_of_integers; i++)
        printf("%d ", array_of_integers[i]);
    puts("");
}

int main(void) {
    int dataset[] = { 2, 4, 5, 7, 1, 2, 3, 6 };

    print_array(dataset, SIZE);
    merge_sort(dataset, 0, SIZE);
    print_array(dataset, SIZE);

    return 0;
}

编辑：（正确的解决方案）

 void merge(int *array_of_integers, int p, int q, int r) {
     int n1 = q - p + 1;
     int n2 = r - q; 
     int i, j, k;
     int left_array[n1 + 1];
     int right_array[n2 + 1];

     left_array[n1] = 123456798;
     right_array[n2] = 123456798;

     for (i = 0; i < n1; i++)
         left_array[i] = array_of_integers[p + i];
     for (j = 0; j < n2; j++)
         right_array[j] = array_of_integers[q + j + 1];

     i = 0;
     j = 0;

     for (k = p; k <= r; k++) {
         if (left_array[i] <= right_array[j]) {
             array_of_integers[k] = left_array[i];
             i++;
         } else {
             array_of_integers[k] = right_array[j];
             j++;
         }
     }
 }

 void merge_sort(int *array_of_integers, int p, int r) {
     if(p < r) {
         int q = (p + r) / 2;
         merge_sort(array_of_integers, p, q);
         merge_sort(array_of_integers, q + 1, r);
         merge(array_of_integers, p, q, r);
     }
 }
4

5 回答 5

9

您的代码中有两个问题。

一，您需要澄清您传递的参数的含义。在 merge_sort 内部，看起来 p 是要排序的第一个元素，而 r 是要排序的最后一个元素。但是，在调用 merge_sort 的地方，在 main 中，它被传递 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 为零时，这将复制第一个范围的最后一个元素，但您需要第二个范围的第一个元素。因此，您需要清除索引的这些用途。（另外，left_array 和 right_array 只需要 n1 和 n2 个元素，而不是 n1+1 和 n2+1。）还要检查 k 上的循环，for(k = p; k < r; k++). 该循环的继续条件应该是什么？

二，当你合并left_array和right_array时，你没有考虑到一个数组可能是空的（因为之前所有的元素都被复制出来了），所以比较left_array[i]和right_array[j]是行不通的，因为i 或 j 分别表示 left_array 或 right_array 之外的元素。例如，如果 i 已达到其极限 (n1)，则不应进行比较。相反，您应该只从 right_array 中获取一个元素。

于 2012-08-21T14:45:09.470 回答
6

这个虽然是用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;

            }           
        }
    }
}
于 2015-04-04T18:03:24.430 回答
0 
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;
}
于 2019-06-15T10:56:26.837 回答
0

这是我的尝试。已知错误：由于 INT_MAX 用作哨兵，对包含 INT_MAX 的数组进行排序可能会导致指针在合并期间溢出。

#include <stdio.h>
#include <limits.h>
void merge(int A[], unsigned int p, unsigned int q, unsigned int r){
    unsigned int n1 = q - p; //differs from book because C indexes from 0
    unsigned int n2 = r - q;


    int L[n1 + 1]; // L contains the first elem of A, up to the midpoint (not including the midpoint)
    int R[n2 + 1]; // R contains the elems including the midpoint of A all the way to the end.

    L[n1] = INT_MAX; //INT_MAX is our sentinel, which will be used in the merge step. No possible int will be greater than INT_MAX, so during the merge,
    R[n2] = INT_MAX; // INT_MAX is similar to the infinity used in the book

    for (unsigned int i = 0; i < n1; i++){
        L[i] = A[p + i];
    }

    for (unsigned int i = 0; i < n2; i++){
        R[i] = A[q + i];
    }
    // Now we just need to merge L and R and sort A
    // The sorting occurs here, during the merge.
    unsigned int i = 0;
    unsigned int j = 0;

    for (unsigned int k = p; k < r; k++){
        if (L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }
        else{
            A[k] = R[j];
            j++;
        }
    }
}
void merge_sort(int A[], unsigned int p, unsigned int r) { // input is array A, first elem p, and last elem + 1 r

    if (p < r - 1) { //differs from book... since C indexes from 0, if we have an array of size 1, we will subtract 1 to get 0 and then hit the base case

        // Otherwise, find the midpoint and divide and conquer
        unsigned int q = (p + r) / 2; //q is the midpoint of A
        merge_sort(A, p, q); //this must process the midpoint
        merge_sort(A, q, r); //this must process the elem after the midpoint to the last elem
        merge(A, p, q, r);
        return;


    }

}


int main(){

    int A[] = {432, 5, 99, 101, 43};
    unsigned int len_A = sizeof(A)/sizeof(A[0]);

    printf("original order of elems in A: \n");

    for (unsigned int i = 0; i < len_A; i++){
        printf("%d ", A[i]);
    }

    merge_sort(A, 0, len_A);

    printf("\n\n");
    printf("after performing merge_sort: \n");


    for (unsigned int i = 0; i < len_A; i++){
        printf("%d ", A[i]);
    }

    printf("\n\n");

return 0;
}
于 2020-01-10T23:15:42.523 回答
0

Python实现

from math import inf


def merge(A, p, q, r):

    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1+1)
    R = [0] * (n2+1)

    for i in range(0, n1):
        L[i] = A[p + i]

    for j in range(0, n2):
        R[j] = A[q + j + 1]

    L[n1] = inf
    R[n2] = inf

    i = 0
    j = 0
    for k in range(p, r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1


def mergesort(A, p, r):

    if p < r:
        q = (p + r)//2
        mergesort(A, p, q)
        mergesort(A, q + 1, r)
        merge(A, p, q, r)


A = [00, 11, 12, 13, 14, 15, 16, 17, 18, 2, 4,
     5, 7, 1, 2, 3, 6, 22, 23, 34, 56, 78, 77]

merge(A, 9, 12, 16)

print(A)

mergesort(A, 9, 16)
print(A)

print(A)
于 2022-02-01T14:28:04.690 回答