Блог

Главная - Вопросы по программированию - Сортировка слиянием: ошибки в этом коде

Сортировка слиянием: ошибки в этом коде

#java #algorithm #sorting

#java #алгоритм #сортировка

Вопрос:

При попытке запустить этот код я получаю исключение index out of bounds .

мы используем два разных массива слева и справа для слияния ..

и использование рекурсивной сортировки слиянием для разделения массива на отдельные элементы и их слияния…

Вот алгоритм из CLR, который я использую :

     Merge(A, p, q, r)
    n1 ← q - p   1
    n2 ← r - q
    create arrays L[1..n1   1] and R[1..n2   1]
    for i ← 1 to n1
    do L[i] ← A[p   i - 1]
    for j ← 1 to n2
      do R[j] ← A[q   j]
    L[n1   1] ← ∞
    L[n2   1] ← ∞
    i ← 1
    j ← 1
    for k ≤ p to r
        do if L[i] ≤ R[j]
          then A[k] ← L[i]
             i ← i   1
          else A[k] ← R[j]
              j ← j   1

     MergeSort(A, p, r)
     if p < r
      then q ← ⌊(p   r)/2⌋
       MergeSort(A, p, q)
       MergeSort(A, q   1, r)
       Merge(A, p, q, r)

вот код:

 import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {
   public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      System.out.println("Enter the size of array to be sorted");
      int size = input.nextInt();
      int[] A = new int[size];
      System.out.println("Enter the elements of array");
      for (int i = 0; i < A.length; i  ) {
         A[i] = input.nextInt();
      }
      System.out.println("The UNSORTED array elements are"   Arrays.toString(A));
      int p = 0, r = size;
      mergeSort(A, p, r);
      System.out.println("The SORTED array elements are"   Arrays.toString(A));
   }

   public static void mergeSort(int[] A, int p, int r) {
      if (p < r) {
         int q = (p   r) / 2;
         mergeSort(A, p, q);
         mergeSort(A, q   1, r);
         merge(A, p, q, r);
      }
   }

   public static void merge(int[] A, int p, int q, int r) {
      int n1 = q - p   1;
      int n2 = r - q;
      int[] L = new int[n1   1];
      int[] R = new int[n2   1];
      L[n1] = Integer.MAX_VALUE;
      R[n2] = Integer.MAX_VALUE;
      for (int i = 0; i < n1; i  ) {
         L[i] = A[p   i];
      }
      for (int j = 0; j < n2; j  ) {
         R[j] = A[q   j   1];
      }
      int x = 0, y = 0;
      for (int k = p; k < r; k  ) {
         if (L[x] <= R[y]) {
            A[k] = L[x];
            x  ;
         } else {
            A[k] = R[y];
            y  ;
         }
      }
   }
}

Комментарии:

1. Пользовательские инструкции println для проверки состояния переменных непосредственно перед созданием исключения. В частности, проверьте длину массива A и значение всех переменных, которые в совокупности составляют индекс массива A.

2. Возможно, вы могли бы, по крайней мере, сообщить нам, какая строка получает исключение, но просто сброс всего вашего задания сюда, чтобы его выполнил кто-то другой, вряд ли найдет большую пользу в SO или где-либо еще, о чем я могу думать. В сети есть множество рабочих примеров.

3. это не присвоение … я не хожу в школу . это просто небольшая ошибка, которую я не мог заметить .. как указал @Gandalf

Ответ №1:

После второго, но более длительного просмотра ваша реализация алгоритма кажется правильной, я запутался в ваших входных параметрах, потому что они не соответствовали вашей реализации на основе нуля. Так что, может быть, вы не хотите называть это так:

 int p = 0, r = size;
mergeSort(A, p, r);

но скорее так:

 int p = 0, r = size - 1;
mergeSort(A, p, r);

Ответ №2:

Просто для полноты картины и после изменения, предложенного Гэндальфом, в merge() методе цикл for должен включать значение r, поэтому, заменив

 for (int k = p; k < r; k  ) {

с

 for (int k = p; k <= r; k  ) {

ваша реализация сортирует массив правильно.