#java #arrays #algorithm #java.util.scanner #mergesort
#java #массивы #алгоритм #java.util.scanner #сортировка слиянием
Вопрос:
В настоящее время я работаю над итеративной сортировкой слиянием, которая запрашивает у пользователя, сколько чисел нужно сгенерировать перед сортировкой. Если я ввожу число > 10, я получаю сообщение об ошибке: «Исключение в потоке «main» java.lang.Исключение NegativeArraySizeException «, но если я жестко закодирую одно и то же точное число (оба положительные), программа работает так, как задумано. Почему я получаю эту ошибку и как я могу ее исправить? Заранее благодарю вас за помощь.
Демонстрационный файл:
import java.util.Scanner;
public class MergeSortDemo
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
//int arraySize = 17;
int arraySize = MergeSortAlgorithms.getArraySize(keyboard);
int[] testArray = new int[arraySize];
MergeSortAlgorithms.fillArray(testArray);
MergeSortAlgorithms.printArray(testArray);
MergeSortAlgorithms.mergeSort(testArray);
MergeSortAlgorithms.printArray(testArray);
}//ends main
}//ends class
Итеративная сортировка слиянием:
public static void mergeSort(int arr[])
{
int n = arr.length;
// For current size of subarrays to
// be merged curr_size varies from
// 1 to n/2
int curr_size;
// For picking starting index of
// left subarray to be merged
int left_start;
// Merge subarrays in bottom up
// manner. First merge subarrays
// of size 1 to create sorted
// subarrays of size 2, then merge
// subarrays of size 2 to create
// sorted subarrays of size 4, and
// so on.
for (curr_size = 1; curr_size <= n-1;
curr_size = 2*curr_size)
{
// Pick starting point of different
// subarrays of current size
for (left_start = 0; left_start < n-1;
left_start = 2*curr_size)
{
// Find ending point of left
// subarray. mid 1 is starting
// point of right
int mid = left_start curr_size - 1;
int right_end = Math.min(left_start
2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid]
// amp; arr[mid 1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
public static void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l 1;
int n2 = r - m;
/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays L[]
and R[] */
for (i = 0; i < n1; i )
L[i] = arr[l i];
for (j = 0; j < n2; j )
R[j] = arr[m 1 j];
/* Merge the temp arrays back into
arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 amp;amp; j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i ;
}
else
{
arr[k] = R[j];
j ;
}
k ;
}
/* Copy the remaining elements of
L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i ;
k ;
}
/* Copy the remaining elements of
R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j ;
k ;
}
}
Методы, связанные с массивом:
public static int getArraySize(Scanner keyboard)
{
System.out.printf("How many numbers would you like to generate? n(More Numbers = Longer Sort): ");
int returnValue = keyboard.nextInt();
return returnValue;
}
public static void fillArray(int[] array)
{
Random random = new Random();
for(int i = 0; i < array.length; i )
{
int randomNumber = (int)(Math.random() * 700 1);
array[i] = randomNumber;
}
}
Поврежденный вывод (с размером массива 17):
How many numbers would you like to generate?
(More Numbers = Longer Sort): 17
241 272 539 456 242 571 333 28 292 426 7 595 191 162 1 542 394
Exception in thread "main" java.lang.NegativeArraySizeException
at MergeSortAlgorithms.merge(MergeSortAlgorithms.java:125)
at MergeSortAlgorithms.mergeSort(MergeSortAlgorithms.java:112)
at MergeSortDemo.main(MergeSortDemo.java:17)
Press any key to continue . . .
Тот же вывод, но 17 — это жестко заданный размер массива:
175 423 562 133 136 53 265 605 312 169 666 630 641 613 176 568 111
53 111 133 136 169 175 176 265 312 423 562 568 605 613 630 641 666
Press any key to continue . . .
Редактировать:
После дополнительного тестирования некоторые большие числа действительно работают. Например, 25, 30 и 56 работают так, как задумано.
Комментарии:
1. если этот алгоритм выдает это исключение, вы можете быть уверены, что предпринята попытка создать массив с отрицательным размером. проверьте строку 125 из
MergeSortAlgorithm, скорее всего,n1илиn2является отрицательной (вычислениеmidподозрительно)
Ответ №1:
Это не имеет ничего общего с получением ввода с консоли. Вместо этого в вашем коде ошибка.
int mid = left_start curr_size - 1;
int right_end = Math.min(left_start 2*curr_size - 1, n-1);
Рассмотрим приведенные выше строки. Всякий раз, когда left_start 2*curr_size - 1 оно достаточно больше n-1 , значение right_end будет становиться меньше mid .
В этом случае значение n2 в методе merge() становится отрицательным. Отсюда ошибка. Как только вы исправите это, вы решите проблему.
ОБНОВЛЕНИЕ Я добавил несколько if условий. Вот рабочий код.
public static void mergeSort(int arr[])
{
int n = arr.length;
// For current size of subarrays to
// be merged curr_size varies from
// 1 to n/2
int curr_size;
// For picking starting index of
// left subarray to be merged
int left_start;
// Merge subarrays in bottom up
// manner. First merge subarrays
// of size 1 to create sorted
// subarrays of size 2, then merge
// subarrays of size 2 to create
// sorted subarrays of size 4, and
// so on.
for (curr_size = 1; curr_size <= n-1;
curr_size = 2*curr_size)
{
// Pick starting point of different
// subarrays of current size
for (left_start = 0; left_start < n-1;
left_start = 2*curr_size)
{
// Find ending point of left
// subarray. mid 1 is starting
// point of right
int mid = left_start curr_size - 1;
int right_end = Math.min(left_start
2*curr_size - 1, n-1);
if(right_end<mid)
right_end=mid;
// Merge Subarrays arr[left_start...mid]
// amp; arr[mid 1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
public static void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l 1;
int n2 = r - m;
/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays L[]
and R[] */
for (i = 0; i < n1; i )
if(l i<arr.length)
L[i] = arr[l i];
for (j = 0; j < n2; j )
if(l j<arr.length)
R[j] = arr[m 1 j];
/* Merge the temp arrays back into
arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 amp;amp; j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i ;
}
else
{
arr[k] = R[j];
j ;
}
k ;
}
/* Copy the remaining elements of
L[], if there are any */
while (i < n1 amp;amp; i<n1 amp;amp; k<arr.length)
{
arr[k] = L[i];
i ;
k ;
}
/* Copy the remaining elements of
R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j ;
k ;
}
}
Я чувствую, что вы можете упростить код.
Ответ №2:
Я пытался запустить ваш код. Все прошло отлично. Вот вывод на консоль.
How many numbers would you like to generate?
(More Numbers = Longer Sort): 17
[303, 394, 315, 436, 196, 212, 629, 139, 666, 519, 4, 182, 36, 108, 129, 490, 174]
[4, 36, 108, 129, 139, 174, 182, 196, 212, 303, 315, 394, 436, 490, 519, 629, 666]
Исключений нет 🙂
Комментарии:
1. Попробуйте запустить с другими входными данными. В конечном итоге вы получите ошибку.