#java #algorithm #mergesort
#java #алгоритм #сортировка слиянием
Вопрос:
Я пытаюсь реализовать алгоритм сортировки слиянием с 4-сторонним разделением на Java, проблема в том, что он генерирует ArrayIndexOutOfBoundsException ошибку в строке 85 алгоритма. Код следующий, я основывался на 2-стороннем алгоритме Merge Sort (традиционный алгоритм):
public static void mergeSort3WayRec(Integer[] gArray, int low, int high,
Integer[] destArray) {
if (high - low < 2) {
return;
}
int mid1 = low ((high - low) / 4);
int mid2 = low 2 * ((high - low) / 4) 1;
int mid3 = low 3 * ((high - low) / 4) 2;
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, mid3, gArray);
mergeSort3WayRec(destArray, mid3, high, gArray);
merge(destArray, low, mid1, mid2, mid3, high, gArray);
}
public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3, int high,
Integer[] destArray) {
int i = low, j = mid1, k = mid2, l = mid3, m = high;
while ((i < mid1) amp;amp; (j < mid2) amp;amp; (k < mid3) amp;amp; (l < high)) {
if (gArray[i].compareTo(gArray[j]) < 0) {
if (gArray[i].compareTo(gArray[k]) < 0) {
if (gArray[i].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[l ];
}
} else {
destArray[m ] = gArray[k ];
}
} else {
if (gArray[j].compareTo(gArray[k]) < 0) {
if (gArray[j].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[j ];
} else {
destArray[m ] = gArray[l ];
}
} else {
if (gArray[k].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
}
}
while ((i < mid1) amp;amp; (j < mid2)) {
if (gArray[i].compareTo(gArray[j]) < 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[j ];
}
}
while ((j < mid2) amp;amp; (k < mid3)) {
if (gArray[j].compareTo(gArray[k]) < 0) {
destArray[m ] = gArray[j ];
} else {
destArray[m ] = gArray[k ];
}
}
while ((k < mid3) amp;amp; (l < high)) {
if (gArray[k].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
while ((i < mid1) amp;amp; (k < mid3)) {
if (gArray[i].compareTo(gArray[k]) < 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[k ];
}
}
while ((i < mid1) amp;amp; (l < high)) {
if (gArray[i].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[l ];
}
}
while ((j < mid2) amp;amp; (l < high)) {
if (gArray[j].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[j ];
} else {
destArray[m ] = gArray[l ];
}
}
while (i < mid1) {
destArray[m ] = gArray[i ];
}
while (j < mid2) {
destArray[m ] = gArray[j ];
}
while (k < mid3) {
destArray[m ] = gArray[k ];
}
while (l < high) {
destArray[m ] = gArray[l ];
}
}
Следует отметить, что gArray является копией исходного массива, введенного в метод main, код этой части выглядит следующим образом:
public static void main(String args[]) {
Integer[] data = new Integer[]{ 45, -2, -45, 78,
30, -42, 10, 19, 73, 93, 80, 60, 2, 98, 85, 99 };
mergeSort3Way(data);
System.out.println("After 3 way merge sort: ");
for (int i = 0; i < data.length; i ) {
System.out.print(data[i] " ");
}
}
public static void mergeSort3Way(Integer[] gArray) {
if (gArray == null) {
return;
}
Integer[] fArray = new Integer[gArray.length];
for (int i = 0; i < fArray.length; i ) {
fArray[i] = gArray[i];
}
mergeSort3WayRec(fArray, 0, gArray.length, gArray);
for (int i = 0; i < fArray.length; i ) {
gArray[i] = fArray[i];
}
}
Мой вопрос в том, как я могу устранить эту ошибку? Кроме того, если есть дополнительная ошибка реализации, я уже новичок, выполняющий этот тип алгоритма.
Спасибо.
Ответ №1:
Проблема, похоже, в … , m = high, за которым позже следует destArray [m ] = … .
При слиянии, когда 4-стороннее слияние достигает конца одного из 4 запусков, оно должно снизиться до 3-стороннего слияния. Чтобы избежать дублирования кода, вам нужно переместить индексы в low, mid1, mid2 и использовать mid3 или high для конца подмассива, начинающегося с mid2. Когда 3-стороннее слияние достигает конца одного из запусков, оно должно снизиться до 2-стороннего слияния, а затем снизиться до 1-сторонней копии.
При сортировке слиянием, если значение high-low < 4, вы можете захотеть просто выполнить сравнение пузырьковой сортировки и поменять местами значения high — low == 3 или high — low == 2.
Предполагая, что high-low < 4 обрабатывается отдельно, затем для несколько равномерной настройки внутренних индексов (меньшие прогоны слева):
int mid1 = low (high 0-low)/4;
int mid2 = mid1 (high 1-low)/4;
int mid3 = mid2 (high 2-low)/4;
Пример кода для 4-сторонней сортировки слиянием сверху вниз с использованием пары взаимно рекурсивных функций, чтобы избежать обратного копирования, и «развернутой» логики слияния. Этот метод быстрее, чем выполнение множества условных выражений, но я думаю, что основное улучшение производительности связано с использованием сортировки по вставке для небольших запусков. Это тот случай, когда отсутствие «goto» в Java является проблемой, поскольку обходной путь, позволяющий избежать дублирования кода, заключается в установке и тестировании переменной «наименьший запуск» в процедуре слияния.
static final int MINSIZE = 32; // must be >= 3
static void InsertionSort(Integer a[], int ll, int rr)
{
int i = ll 1;
int j;
Integer t;
while(i < rr){
t = a[i];
j = i;
while((j > ll) amp;amp; a[j-1].compareTo(t)> 0){
a[j] = a[j-1];
j -= 1;}
a[j] = t;
i = 1;}
}
public static void MergeSort(Integer[] a) // entry function
{
if(a.length < 2) // if size < 2 return
return;
Integer[] b = new Integer[a.length];
MergeSortAtoA(a, b, 0, a.length);
}
static void MergeSortAtoA(Integer[] a, Integer[] b, int ll, int rr)
{
if(rr - ll <= MINSIZE){
InsertionSort(a, ll, rr);
return;}
int m1 = ll (rr 0-ll)/4;
int m2 = m1 (rr 1-ll)/4;
int m3 = m2 (rr 2-ll)/4;
MergeSortAtoB(a, b, ll, m1);
MergeSortAtoB(a, b, m1, m2);
MergeSortAtoB(a, b, m2, m3);
MergeSortAtoB(a, b, m3, rr);
Merge(b, a, ll, m1, m2, m3, rr);
}
static void MergeSortAtoB(Integer[] a, Integer[] b, int ll, int rr)
{
if(rr - ll <= MINSIZE){
System.arraycopy(a, ll, b, ll, rr-ll);
InsertionSort(b, ll, rr);
return;}
int m1 = ll (rr 0-ll)/4;
int m2 = m1 (rr 1-ll)/4;
int m3 = m2 (rr 2-ll)/4;
MergeSortAtoA(a, b, ll, m1);
MergeSortAtoA(a, b, m1, m2);
MergeSortAtoA(a, b, m2, m3);
MergeSortAtoA(a, b, m3, rr);
Merge(a, b, ll, m1, m2, m3, rr);
}
static void Merge(Integer[] a, Integer[] b, int ll, int m1, int m2, int m3, int rr) {
int bb = ll; // b[] index
int a0 = ll; // a[] indexes
int a1 = m1;
int a2 = m2;
int a3 = m3;
while(true){ // 4 way merge
int sr; // smallest run
if(a[a0].compareTo(a[a1]) <= 0){
if(a[a2].compareTo(a[a3]) <= 0){
if(a[a0].compareTo(a[a2]) <= 0){
sr = 0;}
else{
sr = 2;}}
else{
if(a[a0].compareTo(a[a3]) <= 0){
sr = 0;}
else{
sr = 3;}}}
else{
if(a[a2].compareTo(a[a3]) <= 0){
if(a[a1].compareTo(a[a2]) <= 0){
sr = 1;}
else{
sr = 2;}}
else{
if(a[a1].compareTo(a[a3]) <= 0){
sr = 1;}
else{
sr = 3;}}}
if(sr == 0){
b[bb] = a[a0];
bb ;
a0 ;
if(a0 < m1)
continue;
a0 = a1;
a1 = a2;
a2 = a3;
m1 = m2;
m2 = m3;
m3 = rr;
break;}
if(sr == 1){
b[bb] = a[a1];
bb ;
a1 ;
if(a1 < m2)
continue;
a1 = a2;
a2 = a3;
m2 = m3;
m3 = rr;
break;}
if(sr == 2){
b[bb] = a[a2];
bb ;
a2 ;
if(a2 < m3)
continue;
a2 = a3;
m3 = rr;
break;}
else{ // sr == 3
b[bb] = a[a3];
bb ;
a3 ;
if(a3 < rr)
continue;
break;}
}
while(true){ // 3 way merge
int sr; // smallest run
if(a[a0].compareTo(a[a1]) <= 0){
if(a[a0].compareTo(a[a2]) <= 0){
sr = 0;}
else{
sr = 2;}}
else{
if(a[a1].compareTo(a[a2]) <= 0){
sr = 1;}
else{
sr = 2;}}
if(sr == 0){
b[bb] = a[a0];
bb ;
a0 ;
if(a0 < m1)
continue;
a0 = a1;
a1 = a2;
m1 = m2;
m2 = m3;
break;}
if(sr == 1){
b[bb] = a[a1];
bb ;
a1 ;
if(a1 < m2)
continue;
a1 = a2;
m2 = m3;
break;}
else{ // sr == 2
b[bb] = a[a2];
bb ;
a2 ;
if(a2 < m3)
continue;
break;}
}
while(true){ // 2 way merge
if(a[a0].compareTo(a[a1]) <= 0){
b[bb] = a[a0];
bb ;
a0 ;
if(a0 < m1)
continue;
a0 = a1;
m1 = m2;
break;}
else{
b[bb] = a[a1];
bb ;
a1 ;
if(a1 < m2)
continue;
break;}
}
System.arraycopy(a, a0, b, bb, m1-a0); // 1 way copy
}
Исправлена версия кода chqrlie.
public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3, int high,
Integer[] destArray)
{
int i = low, j = mid1, k = mid2, l = mid3, m = low;
while (m < high) {
if (i < mid1 amp;amp; (j >= mid2 || gArray[i].compareTo(gArray[j]) <= 0)) {
if (k >= mid3 || gArray[i].compareTo(gArray[k]) <= 0) {
if (l >= high || gArray[i].compareTo(gArray[l]) <= 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[l ];
}
} else {
if (k < mid3 amp;amp; (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
} else {
if (j < mid2 amp;amp; (k >= mid3 || gArray[j].compareTo(gArray[k]) < 0)) {
if (l >= high || gArray[j].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[j ];
} else {
destArray[m ] = gArray[l ];
}
} else {
if (k < mid3 amp;amp; (l >= high || gArray[k].compareTo(gArray[l]) < 0)) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
}
}
}
public static void mergeSort4WayRec(Integer[] gArray, int low, int high,
Integer[] tempArray) {
if (high - low < 2) {
return;
}
int mid1 = low (high 0 - low) / 4;
int mid2 = mid1 (high 1 - low) / 4;
int mid3 = mid2 (high 2 - low) / 4;
mergeSort4WayRec(tempArray, low, mid1, gArray);
mergeSort4WayRec(tempArray, mid1, mid2, gArray);
mergeSort4WayRec(tempArray, mid2, mid3, gArray);
mergeSort4WayRec(tempArray, mid3, high, gArray);
merge(tempArray, low, mid1, mid2, mid3, high, gArray);
}
public static void mergeSort4Way(Integer[] gArray) {
if (gArray != null) {
Integer[] tempArray = new Integer[gArray.length];
for (int i = 0; i < gArray.length; i ) {
tempArray[i] = gArray[i];
}
mergeSort4WayRec(gArray, 0, gArray.length, tempArray);
}
}
public static void main(String[] args) {
Integer[] a = new Integer[1024*1024];
Random r = new Random();
for(int i = 0; i < a.length; i )
a[i] = r.nextInt();
long bgn, end;
bgn = System.currentTimeMillis();
mergeSort4Way(a);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i ){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " (end-bgn));
}
Ответ №2:
ArrayIndexOutOfBoundsException Это должно быть связано с добавлением 2 для вычисления mid3 для (high - low)/4 < 2 . (Какая идея стояла за этим? (Вызов функции mergeSort3WayRec() бесполезен, как и добавление 1 для вычисления mid2 .))
Чтобы вычислить splitP для P = 1, 2, …, n-1 с отклонением 1 вместо до n-1,
пусть count = high - low и просто установите splitP = low (P * count) / n .
Комментарии:
1. ваше предложение в большинстве случаев дает правильные значения, но может привести к переполнению диапазона типов
intдля очень больших массивов.
Ответ №3:
В вашем коде множество проблем:
-
Вычисление точек разделения неверно для небольших промежутков:
low 3 * ((high - low) / 4) 2больше, чемhighдляhigh - low == 4. Вы должны просто использовать предлагаемое исправление rcgldr:int mid1 = low (high - low 0) / 4; int mid2 = mid1 (high - low 1) / 4; int mid3 = mid2 (high - low 2) / 4; -
выполнение 4-стороннего слияния для небольших массивов является излишним, особенно если размер меньше 4. Вам следует использовать сортировку по вставке на месте для
high - low < 4или, возможно, некоторое большее число, которое вы определите с помощью тщательного сравнительного анализа. -
название
mergeSort3WayRecвводит в заблуждение при реализации 4-сторонней сортировки слиянием 🙂 -
mдолжно быть инициализированоlow, а неhigh. -
на этапе 4-стороннего слияния отсутствует тест.
-
когда один из массивов исчерпан, вам следует вернуться к фазе 3-стороннего слияния, которая полностью отсутствует в вашем коде. Учитывая ваш подход, вам понадобятся 4 разных цикла 3-стороннего объединения.
-
тогда порядок, в котором выполняются оставшиеся фазы двухстороннего слияния, неверен, если вы хотите сохранить стабильность. На самом деле, вам следует протестировать с
<=, чтобы добиться стабильной сортировки. -
имя
destArrayв списке аргументовmergeSort3WayRecвводит в заблуждение, это временный массив, а не целевой массив. -
Циклы копирования в
mergeSort3Way()неверны.mergeSort2WayRecвычисляет отсортированное на месте, цикл копирования не требуется.
Вот более простой подход с комбинированными граничными тестами:
import java.io.*;
import java.lang.*;
public class main {
public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3,
int high, Integer[] destArray)
{
int i = low, j = mid1, k = mid2, l = mid3, m = low;
while (m < high) {
if (i < mid1 amp;amp; (j >= mid2 || gArray[i].compareTo(gArray[j]) <= 0)) {
if (k >= mid3 || gArray[i].compareTo(gArray[k]) <= 0) {
if (l >= high || gArray[i].compareTo(gArray[l]) <= 0) {
destArray[m ] = gArray[i ];
} else {
destArray[m ] = gArray[l ];
}
} else {
if (k < mid3 amp;amp; (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
} else {
if (j < mid2 amp;amp; (k >= mid3 || gArray[j].compareTo(gArray[k]) <= 0)) {
if (l >= high || gArray[j].compareTo(gArray[l]) < 0) {
destArray[m ] = gArray[j ];
} else {
destArray[m ] = gArray[l ];
}
} else {
if (k < mid3 amp;amp; (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
destArray[m ] = gArray[k ];
} else {
destArray[m ] = gArray[l ];
}
}
}
}
for (int i = low; i < high; i ) {
gArray[i] = destArray[i];
}
}
public static void mergeSort4WayRec(Integer[] gArray, int low, int high,
Integer[] tempArray) {
if (high - low < 2) {
return;
}
int mid1 = low (high - low 0) / 4;
int mid2 = mid1 (high - low 1) / 4;
int mid3 = mid2 (high - low 2) / 4;
mergeSort4WayRec(gArray, low, mid1, tempArray);
mergeSort4WayRec(gArray, mid1, mid2, tempArray);
mergeSort4WayRec(gArray, mid2, mid3, tempArray);
mergeSort4WayRec(gArray, mid3, high, tempArray);
merge(gArray, low, mid1, mid2, mid3, high, tempArray);
}
public static void mergeSort4Way(Integer[] gArray) {
if (gArray != null) {
Integer[] tempArray = new Integer[gArray.length];
mergeSort4WayRec(gArray, 0, gArray.length, tempArray);
}
}
public static void main(String[] args) {
Integer arr[] = { 3, 2, 4, 1, 99, 30, 5, 3, 3, 2, 4, 1, 99, 30, 5, 3,
3, 2, 4, 1, 99, 30, 5, 3 };
long ns = System.nanoTime();
mergeSort4Way(arr);
ns = System.nanoTime() - ns;
for (int i = 0; i < arr.length; i ) {
System.out.print(arr[i] " ");
}
System.out.println("n" arr.length "elements sorted in " ns " ns");
}
}
Комментарии:
1. (Я пропустил, что вы отклоняли диапазоны, а не допускали.)
2. @rcgldr: Я тоже так думал, но либо
mergeSort4WayRecсортирует на месте иmergeдолжен копировать обратно в исходный массив, либоmergeSort4WayRecсортирует вdestArrayи вызовmergeизtempвgArrayвыдает результат в исходном массиве, следовательно, сортирует на месте : (3. @rcgldr: Я, наконец, настроил свою систему для компиляции Java-материалов. Код компилирует и сортирует небольшую выборку правильно. Интересно, почему OP использует
Integer[]вместоint []и обычные<=операторы. Я полагаю, что реализацию можно более легко обобщить на другие типы. Жаль, что в Java нет перегрузки оператора, но я предполагаю, что код Java и так достаточно подробный и запутанный, без дополнительной сложности…4. @rcgldr: Боюсь, ваш исправленный код работает только для одного шага рекурсии.
5. @chqrlie — Я обновил свой ответ, включив main (тестовый код) и переключившись на прогоны более равномерного размера. Я протестировал 1 миллион целых чисел, которые должны выполнять несколько уровней рекурсии.