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

Я учусь алгоритмы из Кормена и Ко. и у меня есть проблема с реализацией merge sort из их псевдокода. Я составил его по: 

$ 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;
}

Edit: (правильное решение) 

 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);
   }
 }
2 9
algorithm mergesort

2 ответа:

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

Во-первых, вам нужно уточнить, что означают передаваемые параметры. Внутри merge_sort выглядит так, что p-это первый элемент, подлежащий сортировке, а r-последний элемент, подлежащий сортировке. Но, где merge_sort называется, в main, он передается 0 и SIZE. Здесь 0-это первый элемент, подлежащий сортировке, но размер не может быть последним элементом, потому что это (предположительно) число элементов, подлежащих сортировке. В вашем примере вы проходите 8, но последний элемент, подлежащий сортировке, равен 7. Поэтому решите, хотите ли вы изменить merge_sort так, чтобы r было числом элементов, или вы хотите изменить main на pass 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] не работает, потому что i или j указывает на элемент вне left_array или right_array соответственно. Например, если я достиг своего предела (n1), то сравнивать не стоит. Вместо этого вы должны просто взять элемент из right_array.

9

Этот работает, хотя он реализован в 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;

            }           
        }
    }
}
4