Замудренная рекурсия - прошу подсказки.
Здравств.
У нас то-ли препод оч хитрий, то ли ХЗ. :) А то что-то как придумает.
Задача вроде бы проста, но уже несколько часов сижу и думаю как бы это сделать.
Фишка вот в чем. Нужно написать рекурсивный и итеративный MergeSort, - в интернете и книгах полно исходников. Но он дал вот такую схему.
Так вот что я намудрил:
первую часть последовательности разбивает правильно - например (32 2 256 8 512 4) - у меня еще спец условие для ввода, заходят только (2^n элементы). Это не важно.
Тоисть 32,2,256 - делит на 2 и так д...
а вот как делить вторую последовательность? после рекурсии right всегда изменяется. Никаких глобальных переменных нельзя, все должно функционировать в пределах этой функции.
Спасибо за подсказки.
У нас то-ли препод оч хитрий, то ли ХЗ. :) А то что-то как придумает.
Задача вроде бы проста, но уже несколько часов сижу и думаю как бы это сделать.
Фишка вот в чем. Нужно написать рекурсивный и итеративный MergeSort, - в интернете и книгах полно исходников. Но он дал вот такую схему.
Код:
public static void sort_iterativ(int[] a)
public static int[] sort_rekursiv(int[] a)
public static int[] sort_rekursiv(int[] a)
Так вот что я намудрил:
Код:
public static int[] sort_rekursiv(int[] a) {
//int[] result = new int[a.length];
int m = (a.length + 1) / 2;
int[] left = new int[(a.length + 1) / 2];
int[] right = new int[a.length - m];
if (a.length <= 1) {
return a;
} else {
for (int i = 0; i < left.length; ++i) {
left = a;
IO.println("left [" + i + "] = " + left);
}
sort_rekursiv(left);
for (int i = 0; i < right.length; ++i) {
right = a[i + m];
IO.println("right [" + i + "] = " + right);
}
sort_rekursiv(right);
}
return merge(left,right);
}
//int[] result = new int[a.length];
int m = (a.length + 1) / 2;
int[] left = new int[(a.length + 1) / 2];
int[] right = new int[a.length - m];
if (a.length <= 1) {
return a;
} else {
for (int i = 0; i < left.length; ++i) {
left = a;
IO.println("left [" + i + "] = " + left);
}
sort_rekursiv(left);
for (int i = 0; i < right.length; ++i) {
right = a[i + m];
IO.println("right [" + i + "] = " + right);
}
sort_rekursiv(right);
}
return merge(left,right);
}
первую часть последовательности разбивает правильно - например (32 2 256 8 512 4) - у меня еще спец условие для ввода, заходят только (2^n элементы). Это не важно.
Тоисть 32,2,256 - делит на 2 и так д...
а вот как делить вторую последовательность? после рекурсии right всегда изменяется. Никаких глобальных переменных нельзя, все должно функционировать в пределах этой функции.
Спасибо за подсказки.
Для рекурсивного варианта возьми QuickSort скажем отсюда: http://www.javenue.info/post/45
и передавай в функцию рекурсивно не диапазон сортируемых элементов, а куски массива исходного. Возвращаемые массивы склеивай.
и передавай в функцию рекурсивно не диапазон сортируемых элементов, а куски массива исходного. Возвращаемые массивы склеивай.
Дык, нужно именно MergeSort - задание такое.
решено
left = sort_rekursiv(left);
right = sort_rekursiv(right);
left = sort_rekursiv(left);
right = sort_rekursiv(right);