Блог

все! Я пытаюсь реализовать алгоритм сортировки слиянием в C #. И у меня есть исключение StackOverflow с моим кодом. Я пытаюсь понять, в чем проблема, и не могу ее решить.

 using System;

class MainClass {
  
  static void merge(int[] arr, int leftIndex, int endLeftIndex, int endRightIndex){
    // leftArr [leftIndex ... endLeftIndex]
    // rightArr [endLeftIndex   1 ...  endRightIndex]
    int leftArrLength = endLeftIndex - leftIndex   1;
    int rightArrLength = endRightIndex - endLeftIndex;
    
    int[] leftArr = new int[leftArrLength], rightArr = new int[rightArrLength];

    // Copying the data from the parent Array to the leftArr amp; rightArr
    for(int i = 0; i < leftArrLength; i  )
      leftArr[i] = arr[leftIndex   i];
    for(int j = 0; j < rightArrLength; j  )
      rightArr[j] = arr[endLeftIndex   j   1];

    // the start index of the array that will be merged
    int mergedArrIndex = leftIndex;

    // set two start pointers for both left and right arrays
    int leftIndexMerge = 0, rightIndexMerge = 0;

    // the merging operation
    while(leftIndexMerge < leftArrLength amp;amp; rightIndexMerge < rightArrLength){
      if(leftArr[leftIndexMerge] < rightArr[rightIndexMerge])
        arr[mergedArrIndex  ] = leftArr[leftIndexMerge  ];
      else
        arr[mergedArrIndex  ] = rightArr[rightIndexMerge  ];
    }
    
    // copying the rest elements
    while(leftIndexMerge < leftArrLength)
      arr[mergedArrIndex  ] = leftArr[leftIndexMerge  ];
    
    while(rightIndexMerge < rightArrLength)
      arr[mergedArrIndex  ] = rightArr[rightIndexMerge  ];
  }
  
  static void mergeSort(int[] arr, int leftIndex, int endRightIndex){
    if(leftIndex < endRightIndex){
      // leftArr [leftIndex ... m]
      // rightArr [m   1 ...  endRightIndex]
      int m = leftIndex   (endRightIndex - 1) / 2;
      mergeSort(arr, leftIndex, m);
      mergeSort(arr, m   1, endRightIndex);
      merge(arr, leftIndex, m, endRightIndex);
    }
  }
  public static void Main (string[] args) {
    int[] arr = {1,2,5,10,1,2,3,4,4};
    mergeSort(arr, 0, arr.Length);
    foreach(int i in arr) Console.WriteLine(i);
  }
}
  

Просмотрите код в repl.it :https://repl.it/@MohamedMarzouk/MergeSortImplementationInCSharp

У вас было 2 проблемы

Первое, что вызвало ваше переполнение стека

 // int m = leftIndex   (endRightIndex - 1) / 2;
// should be
int m = leftIndex   (endRightIndex - leftIndex) / 2;
  

Глядя на источник, вы просто приняли l за 1

и следующее, которое дало бы вам ошибку index out of range

 // mergeSort(arr, 0, arr.Length);
// should be
mergeSort(arr, 0, arr.Length-1);
  

Никаких оправданий нет 🙂

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

• вычисление среднего индекса неверно: int m = leftIndex (endRightIndex - 1) / 2; должно быть

     int m = leftIndex   (endRightIndex - leftIndex) / 2;
    

• аргумент, переданный для первоначального вызова из Main неверен: mergeSort(arr, 0, arr.Length) должен быть

     mergeSort(arr, 0, arr.Length - 1);
    

Это показывает, что соглашение о включении начального и конечного граничных индексов подвержено ошибкам. Если endRightIndex и endLeftIndex исключены, больше нет необходимости в 1 / -1 корректировках. Я бы хотел, чтобы учебные пособия перестали преподавать эту бессмыслицу.

Вот упрощенная версия:

 using System;

class MainClass {
 
  static void merge(int[] arr, int leftIndex, int rightIndex, int endIndex) {
     // leftArr [leftIndex ... endLeftIndex)
     // rightArr [endLeftIndex ...  endIndex)
     int leftArrLength = rightIndex - leftIndex;
     int rightArrLength = endIndex - RightIndex;
   
     int[] leftArr = new int[leftArrLength];
     int[] rightArr = new int[rightArrLength];

     // Copying the data from the parent Array to the leftArr amp; rightArr
     for (int i = 0; i < leftArrLength; i  )
        leftArr[i] = arr[leftIndex   i];
     for (int j = 0; j < rightArrLength; j  )
        rightArr[j] = arr[rightIndex   j];

     // the start index of the array that will be merged
     int mergedArrIndex = leftIndex;

     // set two start pointers for both left and right arrays
     int leftIndexMerge = 0, rightIndexMerge = 0;

     // the merging operation
     while (leftIndexMerge < leftArrLength amp;amp; rightIndexMerge < rightArrLength) {
        if (leftArr[leftIndexMerge] <= rightArr[rightIndexMerge])
           arr[mergedArrIndex  ] = leftArr[leftIndexMerge  ];
        else
           arr[mergedArrIndex  ] = rightArr[rightIndexMerge  ];
     }
   
     // copying the rest elements
     while (leftIndexMerge < leftArrLength)
        arr[mergedArrIndex  ] = leftArr[leftIndexMerge  ];
   
     // This final loop is actually redundant: these elements are already in place
     //while (rightIndexMerge < rightArrLength)
     //   arr[mergedArrIndex  ] = rightArr[rightIndexMerge  ];
  }
 
  static void mergeSort(int[] arr, int leftIndex, int endIndex) {
     if (endIndex - leftIndex >= 2) {
        // leftArr [leftIndex ... m)
        // rightArr [m ...  endIndex)
        int m = leftIndex   (endIndex - leftIndex) / 2;
        mergeSort(arr, leftIndex, m);
        mergeSort(arr, m, endIndex);
        merge(arr, leftIndex, m, endIndex);
     }
  }

  public static void Main(string[] args) {
     int[] arr = { 1, 2, 5, 10, 1, 2, 3, 4, 4 };
     mergeSort(arr, 0, arr.Length);
     foreach (int n in arr)
        Console.WriteLine(n);
  }
}