есть ли причина, по которой моя сортировка слиянием не работает для длины массива 10 - PullRequest
Новая
       14

есть ли причина, по которой моя сортировка слиянием не работает для длины массива 10

0 голосов
/ 22 марта 2019

Я настраиваю сортировку слиянием для сортировки моего массива.Цель состоит в том, чтобы отсортировать массив любой длины.

Я попытался посмотреть на функцию mergesort, но я не вижу в этом ничего плохого.сортировка работает для некоторой длины массива, будь она нечетной или четной, но для длины массива, такой как длина 10, я получаю исключение с ограничениями.

import java.util.Arrays;

class MergeSort
{
 // Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to]
 public static void merge(int[] A, int[] temp, int from, int mid, int to)
 {
  int k = from, i = from, j = mid + 1;

  // loop till there are elements in the left and right runs
  while (i <= mid && j <= to) {
   if (A[i] < A[j]) {
    temp[k++] = A[i++];
   } else {
    temp[k++] = A[j++];
   }
  }

  // Copy remaining elements
  while (i <= mid) {
   temp[k++] = A[i++];
  }

  // Don't need to copy second half

  // copy back to the original array to reflect sorted order
  for (i = from; i <= to; i++) {
   A[i] = temp[i];
  }
 }

 // Iteratively sort array A[low..high] using temporary array
 public static void mergesort(int[] A)
 {
  int low = 0;
  int high = A.length - 1;

  // sort array A[] using temporary array temp
  int[] temp = Arrays.copyOf(A, A.length);

  // divide the array into blocks of size m
  // m = [1, 2, 4, 8, 16...]
  for (int m = 1; m <= high - low; m = 2*m)
  {
   // for m = 1, i = 0, 2, 4, 6, 8...
   // for m = 2, i = 0, 4, 8, 12...
   // for m = 4, i = 0, 8, 16...
   // ...
   for (int i = low; i < high; i += 2*m)
   {
    int from = i;
    int mid = i + m - 1;
    int to = Integer.min(i + 2 * m - 1, high);

    merge(A, temp, from, mid, to);
   }
  }
 }

 // Iterative Implementation of Mergesort algorithm
 public static void main(String[] args)
 {
  int[] A = { 5, 7, -9, 3, -4, 2, 8, 8, 10, 11 };

  System.out.println("Original Array : " + Arrays.toString(A));
  mergesort(A);
  System.out.println("Modified Array : " + Arrays.toString(A));
 }
}

Ответы [ 2 ]

1 голос
/ 22 марта 2019

Ваш средний расчет неверен.Иногда вы устанавливаете его вне диапазона области.

Это изменение, приведенное ниже, исправляет алгоритм, предотвращая выход середины за пределы, аналогично тому, как вы это делали с предотвращением выхода за пределы.

Измените int mid = i + m - 1; на int mid = Math.min(i + m - 1, A.length - 1);

Объяснение: Как уже упоминалось в вашем комментарии, кусочки исследуемой области увеличиваются в размере.Итак, вот как сортируется ваш массив, и когда происходит ошибка «вне границ», и почему она не возникает при размерах, равных 2: 

             [ -9,  5,  7,  3, -4,  2,  8,  8, 10, 11 ]           Array size
 First pass:   []  []  []  []  []  []  []  []  []  []             1
     Second:   [    ]  [    ]  [    ]  [    ]  [    ]             2
      Third:   [            ]  [            ]  [       ERROR]     4
0 голосов
/ 22 марта 2019

Вот ваше исправление:

Добавлен оператор if, чтобы ваши середины не пересекали границу массива 

if(mid<high) {
            merge(A, temp, from, mid, to);
        }

Полный код: 

// Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to]
public static void merge(int[] A, int[] temp, int from, int mid, int to)
{
    int k = from, i = from, j = mid + 1;

    // loop till there are elements in the left and right runs
    while (i <= mid && j <= to) {
        if (A[i] < A[j]) {
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }

    // Copy remaining elements
    while (i <= mid) {
        temp[k++] = A[i++];
    }

    // Don't need to copy second half

    // copy back to the original array to reflect sorted order
    for (i = from; i <= to; i++) {
        A[i] = temp[i];
    }
}

// Iteratively sort array A[low..high] using temporary array
public static void mergesort(int[] A)
{
    int low = 0;
    int high = A.length - 1;

    // sort array A[] using temporary array temp
    int[] temp = Arrays.copyOf(A, A.length);
    //System.out.println("temp Array : " + Arrays.toString(temp));

    // divide the array into blocks of size m
    // m = [1, 2, 4, 8, 16...]
    for (int m = 1; m <= high - low; m = 2*m)
    {
        // for m = 1, i = 0, 2, 4, 6, 8...
        // for m = 2, i = 0, 4, 8, 12...
        // for m = 4, i = 0, 8, 16...
        // ...
        for (int i = low; i < high; i += 2*m)
        {
            int from = i;
            int mid = i + m - 1;
            int to = Integer.min(i + 2 * m - 1, high);

            if(mid<high) {
                merge(A, temp, from, mid, to);
            }

        }
    }
}

// Iterative Implementation of Mergesort algorithm
public static void main(String[] args)
{
    int[] A = { 5, 7, -9, 3, -4, 2, 8, 8, 10, 11 };

    System.out.println("Original Array : " + Arrays.toString(A));
    mergesort(A);
    System.out.println("Modified Array : " + Arrays.toString(A));
}
...