如何实现Cormen and Co.的"算法导论"中的合并排序

Question

我正在学习Cormen和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);
     }
 }

Answer 1

您的代码中存在两个问题.

一,你需要弄清楚你传递的参数是什么意思.在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之外的元素.例如,如果我已达到其极限(n1),那么你不应该比较.相反,你应该从right_array中获取一个元素.

Answer 2

虽然它是用 Java 实现的，但它的工作原理显然是相同的。我已经处理了 Eric 在答案中提出的所有观点。请检查代码，它是不言自明的。

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;

            }           
        }
    }
}