Внедрение MergeSort в C#

Question

В настоящее время изучается алгоритм анализа, а вместо слепого спуска с псевдокода из моего учебника я реализую каждый алгоритм в C#. Это псевдо-код:

MERGE-SORT(A,p,r) 
1 if p < r 
2  q = (p+r)/2 
3  MERGE-SORT(A,p,q) 
4  MERGE-SORT(A,q+1,r) 
5  MERGE(A,p,q,r) 

MERGE(A,p,q,r) 
1 n1 = q - p + 1 
2 n2 = r - q 
3 let L[1..n1+1] and R[1..n2+1] be new arrays 
4 for i = 1 to n1 
5  L[i] = A[p+i-1] 
6 for j = 1 to n2 
7  R[j] = A[q+j] 
8 L[n1+1] = INF 
9 R[n1+1] = INF 
10 i = 1 
11 j = 1 
12 for k = p to r 
13 if L[i] <= R[j] 
14  A[k] = L[i] 
15  i = i + 1 
16 else 
17  A[k] = R[j] 
18  j = j + 1 

Это мой код:

static void Main(string[] args) 
{ 
    int[] unsortedArray = new int[] { 5, 2, 7, 4, 1, 6, 8, 3, 9, 10 }; 
    MergeSort(ref unsortedArray, 1, unsortedArray.Length); 
    foreach (int element in unsortedArray) 
    { 
     Console.WriteLine(element); 
    } 
    Console.Read(); 
} 

private static void MergeSort(ref int[] unsortedArray, int leftIndex, int rightIndex) 
{ 
    if (leftIndex < rightIndex) 
    { 
     int middleIndex = (leftIndex + rightIndex)/2; 
     //Sort left (will call Merge to produce a fully sorted left array) 
     MergeSort(ref unsortedArray, leftIndex, middleIndex); 
     //Sort right (will call Merge to produce a fully sorted right array) 
     MergeSort(ref unsortedArray, middleIndex + 1, rightIndex); 
     //Merge the sorted left & right to finish off. 
     Merge(ref unsortedArray, leftIndex, middleIndex, rightIndex); 
    } 
} 

private static void Merge(ref int[] unsortedArray, int leftIndex, int middleIndex, int rightIndex) 
{ 
    int lengthLeft = middleIndex - leftIndex + 1; 
    int lengthRight = rightIndex - middleIndex; 
    int[] leftArray = new int[lengthLeft + 1]; 
    int[] rightArray = new int[lengthRight + 1]; 
    for (int i = 0; i < lengthLeft; i++) 
    { 
     leftArray[i] = unsortedArray[leftIndex + i - 1]; 
    } 
    for (int j = 0; j < lengthRight; j++) 
    { 
     rightArray[j] = unsortedArray[middleIndex + j]; 
    } 
    leftArray[lengthLeft] = Int32.MaxValue; 
    rightArray[lengthRight] = Int32.MaxValue; 
    int iIndex = 0; 
    int jIndex = 0; 
    for (int k = leftIndex; k < rightIndex; k++) 
    { 
     if (leftArray[iIndex] <= rightArray[jIndex]) 
     { 
      unsortedArray[k] = leftArray[iIndex]; 
      iIndex++; 
     } 
     else 
     { 
      unsortedArray[k] = rightArray[jIndex]; 
      jIndex++; 
     } 
    } 
} 

Я не уверен, где я Мессинг вещи - я пытался следовать за псевдо-код, а также как я мог, но мой результат фанк (т. е. повторяющиеся значения и не отсортированы должным образом).

Отладка этого не помогла мне разобраться с проблемой (рекурсивные решения слишком запутаны).

Где я ошибаюсь и как его исправить?

Answer 1

Как правильно указано в комментариях, индексирование массива C# основано на нулевом уровне, в то время как ваш псевдокод основан на одном.

Это, как говорится, вот ошибки:

1) Основной метод

MergeSort(ref unsortedArray, 1, unsortedArray.Length); 

должен быть изменен на:

MergeSort(ref unsortedArray, 0, unsortedArray.Length - 1); 

2) Слияние методом

leftArray[i] = unsortedArray[leftIndex + i - 1]; 

должно быть изменение:

leftArray[i] = unsortedArray[leftIndex + i]; 

3) Объединить метод

rightArray[j] = unsortedArray[middleIndex + j]; 

должен быть изменен на:

rightArray[j] = unsortedArray[middleIndex + j + 1]; 

4) Слияние методу

for (int k = leftIndex; k < rightIndex; k++) 

должен быть изменение:

for (int k = leftIndex; k <= rightIndex; k++) 

BTW, ref ключевого слова в вашем коде на самом деле не necessay, так как вы просто изменяя значения в массиве, а не создавать новый экземпляр этого ,

Answer 2

Простая реализация сортировки слияния.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MergeSort.cs

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace AlgorithmsMadeEasy 
{ 
    class MergeSort 
    { 
     public void MergeSortMethod() 
     { 
      var input = System.Console.ReadLine(); 
      string[] sInput = input.Split(' '); 
      int[] numbers = Array.ConvertAll(sInput, int.Parse); 
      int len = numbers.Length; 
      MergeSort_Recursive(numbers, 0, len - 1); 
      for (int i = 0; i < len; i++) 
      { 
       Console.Write(numbers[i] + " "); 
      } 

      Console.ReadLine(); 
     } 

     static public void MergeSort_Recursive(int[] numbers, int left, int right) 
     { 
      int mid; 

      if (right > left) 
      { 
       mid = (right + left)/2; 
       MergeSort_Recursive(numbers, left, mid); 
       MergeSort_Recursive(numbers, (mid + 1), right); 

       DoMerge(numbers, left, (mid + 1), right); 
      } 
     } 

     static public void DoMerge(int[] numbers, int left, int mid, int right) 
     { 
      int[] temp = new int[numbers.Length]; 
      int i, left_end, num_elements, tmp_pos; 

      left_end = (mid - 1); 
      tmp_pos = left; 
      num_elements = (right - left + 1); 

      while ((left <= left_end) && (mid <= right)) 
      { 
       if (numbers[left] <= numbers[mid]) 
        temp[tmp_pos++] = numbers[left++]; 
       else 
        temp[tmp_pos++] = numbers[mid++]; 
      } 

      while (left <= left_end) 
       temp[tmp_pos++] = numbers[left++]; 

      while (mid <= right) 
       temp[tmp_pos++] = numbers[mid++]; 

      for (i = 0; i < num_elements; i++) 
      { 
       numbers[right] = temp[right]; 
       right--; 
      } 
     } 
    } 
} 

/* 
Sample Input: 
6 5 3 2 8 

Calling Code: 
MergeSort ms = new MergeSort(); 
ms.MergeSortMethod(); 
*/