Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
package Algorithms.lessons;

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

public class MergeSort
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int N, start, end;
		do
		{
			start = scanner.nextInt();
			end = scanner.nextInt();
			N = scanner.nextInt();
		} while (N <= 0 && start < 0 && end > start && N < end);
		double[] arr = new double[N];
		for(int i = 0; i < N; i++)
		{
			arr[i] = Math.random();
		}
		mergeSort(arr, start, end);
		for(int i = 0; i < N; i++)
		{
			System.out.printf("arr[%d] = %f\n", i, arr[i]);
		}
	}
	
	public static void mergeSort(double[] arr, int start, int end)
	{
		int q;
		if(start >= end)  // подмассив arr содержит не более одного элемента
		{
			return;
		}
		else
		{
			q = (int)((start + end)/2);
			mergeSort(arr, start, q);
			mergeSort(arr, q + 1, end);
			merge(arr, start, q, end);
		}	
	}
	
	public static double[] merge(double[] arr, int start, int q, int end)
	{
		int n1 = q - start + 1;
		int n2 = end - q;
		double[] B = new double[n1 + 1];
		double[] C = new double[n2 + 1];
		B = Arrays.copyOfRange(arr, start, q + 1);
		C = Arrays.copyOfRange(arr, q + 1, end + 1);
		B[n1] = C[n2] = Double.MAX_VALUE;
		int i = 0;
		int j = 0;
		for(int k = start; k < q; k++)
		{
			if(B[i] <= C[j])
			{
				arr[k] = B[i];
				i++;
			}
			else
			{
				arr[k] = C[j];
				j++;
			}
		}
		return arr;
	}
}

Изучаю Java, решил подтянуть алгоритмы. Дошел до Merge-Sort. Решил написать код по книжке Кормена(сами алгоритмы там пишутся в серых табличках). Выдает ошибку
0
10
11
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
	at Algorithms.lessons.MergeSort.merge(MergeSort.java:54)
	at Algorithms.lessons.MergeSort.mergeSort(MergeSort.java:42)
	at Algorithms.lessons.MergeSort.mergeSort(MergeSort.java:40)
	at Algorithms.lessons.MergeSort.mergeSort(MergeSort.java:40)
	at Algorithms.lessons.MergeSort.mergeSort(MergeSort.java:40)
	at Algorithms.lessons.MergeSort.main(MergeSort.java:23)

Знаю, что вышел тупо за пределы массива. А нельзя тупо сделать в функции merge массив размера end - start + 1 каждый раз, а потом тупо сделать сортировку, например, quicksort?
5 июл 20, 02:56    [22162247]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
Не понимаю, как правильно организовать функцию merge. Если там запустить сортировку вставками, то все гуд, но сам алгоритм MergeSort теряет смысл.
5 июл 20, 04:33    [22162252]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz, а кто тебе подсказал эту реализацию? Ты сам ее написал или это скопировано из учебника?
5 июл 20, 11:57    [22162300]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Мой поинт вот в чем. Исторически merge-sort (MR) создавался как механизм сортировки данных на магнитных лентах.
Тоесть на тех устройствах где не было random-access, a было только последовательное чтение и последовательная
запись. Тоесть грубо говоря не было class RandomAccessFile а были только интерфейсы InputStream/OutputStream
и было очень мало (!) реально сцуко мало оперативки. Буквально несколько килобайт. Вот под эти условия
и проектировался MR.

+
Картинка с другого сайта.


Это очень старый алгоритм. И маэстро всех алгоритмов Дональд Кнут даже включил поддержку ленточных
устройств в свой виртуальный компьютер MMIX, просто чтобы было историческое наследие.

И невозможно тебе реализовать и понять назначение MR без понимания исторических предпосылок.

Сам по себе merge-sort прост и реализовать его легко. Но есть соблазн реализовать его неправильно.
И вот чтобы понять что ПРАВИЛЬНО и что НЕ-правильно - нужен исторический экскурс.
5 июл 20, 12:59    [22162318]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Ну, как мне говорили, что алгоритмы и структуры данных надо знать, так как иначе это будет говнокод.
https://en.wikipedia.org/wiki/Sorting_algorithm - тут куча алгоритмов. Как я понимаю, стажер (пока я, конечно, мечу туда) должен знать о них, и в какой ситуации применять. Я просто читаю Кормена и сам пытаюсь придумать код, хотя рецепт алгоритма в Кормене дается.
5 июл 20, 15:22    [22162352]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Помимо этого есть сортировки гномья, глупая, расческой и т.п.
5 июл 20, 15:24    [22162353]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

Ну, как мне говорили, что алгоритмы и структуры данных надо знать, так как иначе это будет говнокод.
https://en.wikipedia.org/wiki/Sorting_algorithm - тут куча алгоритмов. Как я понимаю, стажер (пока я, конечно, мечу туда) должен знать о них, и в какой ситуации применять. Я просто читаю Кормена и сам пытаюсь придумать код, хотя рецепт алгоритма в Кормене дается.

На собеседованиях тебя не будут просить каждый раз сделать реализацию этих сортировок.
В этом нет смысла т.к. они уже реализованы в коллекциях. И от программиста обычно требуется
указать компаратор для сортируемой сущности и на этом все.

Но тебя могут просто спросить про свойства сортирующих алгоритмов.
Например асимптоматику и потребление дополнительной памяти и стека.

Про Гномью - забудь. Я сколько работаю - никогда в практике собесов этого не слышал. Никогда этого никто не спросит.

Могут спросить сортировку Хоара и Шелла. Они имеют наилучшие характеристики в скорости и стабильности.

Вообще это тема "начать диалог". Тоесть понять насколько ты способен технически мыслить и соображать.
Некоторые из сортировок - (метод прямого выбора или метод вставок) настолько интуитивны что даже
если ты их не знал ты их сам напишешь на бумажке минут через 30 рассуждений.
5 июл 20, 15:32    [22162357]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Я вот думаю взять массив из 10^N элементов, где N от нуля до, например, 10 и сделать дял кажжого алгоритма график.
5 июл 20, 15:39    [22162358]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Я вот дебил не могу merge организовать никак, но алгоритм с точки зрения мозгов очень легкий, но написать это на ЯПе тяжело. А так мне понравился вставочная сортировка, но у нее много сравнений, то есть он хорош, когда массив изначально хорошо отсортирован.
5 июл 20, 15:41    [22162359]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

Я вот думаю взять массив из 10^N элементов, где N от нуля до, например, 10 и сделать дял кажжого алгоритма график.

График чего?
5 июл 20, 17:05    [22162371]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Зависимости числа операций от числа элементов
5 июл 20, 17:29    [22162383]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
А ну ОК. Одобряю. Только посчитать раздельно операции по категорям.

- сравнение двух элементов.
- чтение элемента
- запись элемента
- обмен

при этом мы будем понимать что обмен в себя всё равно включает чтение и запись но не всякое
чтение обязательно ассоциировано с обменом. Например в методе прямого выбора есть просто
прочёсывание диапазона на предмет максимального ключа и количество чтений при этом должно
быть учтено.
5 июл 20, 17:34    [22162386]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Сложность еще зависит от изначальной отсортированности массива. Где-то она будет лучше, где-то хуже.
5 июл 20, 17:48    [22162392]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

Сложность еще зависит от изначальной отсортированности массива. Где-то она будет лучше, где-то хуже.

Верно рассуждаешь. Твой эксперимент по сути должен еще разделиться на 3 части.

algorithmrandom shuffledordered ascordered desc
Hoare Sort
Shell Sort


Некоторые из них будут - благоприятным начальным раскладом. А некоторые - worst case. Это тот случай когда
изначально быстрый алгоритм начинает идти по избыточному пути и делать действия которые не нужны.
Здесь кстати в любой алгоритм можно опционально добавить проверку на то что массив уже отсортирован.
Это - наивно. Но это помогает отбросить worst-case.
5 июл 20, 17:54    [22162394]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Как я понимаю, можно еще комбинировать алгоритмы, то есть для одной части один алгоритм, а для другой - другой, но это надо заранее знать отсортированность алгоритма.
5 июл 20, 19:32    [22162413]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

А какие ты галеры знаешь, даже самые херовые, где могут взять таких унтерменшей, как я, в будущем? Я вообще изначально в 23 года узнал о веб-программировании, но сказали, что из-за орды школьников пробиться даже на стажера почти нереал.
5 июл 20, 19:35    [22162416]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Zzz79
Member

Откуда:
Сообщений: 583
алгоритмы и структуры данных спрашивают на каждом собесе
знать нужно обязательно ,реализовыват нет
5 июл 20, 21:24    [22162440]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Zzz79
Member

Откуда:
Сообщений: 583
Alexandrietz
mayton,

А какие ты галеры знаешь, даже самые херовые, где могут взять таких унтерменшей, как я, в будущем? Я вообще изначально в 23 года узнал о веб-программировании, но сказали, что из-за орды школьников пробиться даже на стажера почти нереал.

Из какого ты города?
5 июл 20, 21:25    [22162441]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
Zzz79,

Moscow
5 июл 20, 21:37    [22162442]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

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

Да. Никто не запретит тебе комбинировать алгоритмы. Но асимптоматику результата еще сложнее
будет изучать и доказывать т.к. у нас появляется еще одна ветка if-else где надо расчитать с какой
вероятностью мы вылетим с позитивным условияем (уже отсортирован) и как дорого для нас
это будет стоить.

Это опять-же игры не столько с алгоритмами а больше с композицией алгоритма + тех сведений
которые известны о самих данных.
5 июл 20, 22:40    [22162456]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 5388
Alexandrietz
mayton,

А какие ты галеры знаешь, даже самые херовые, где могут взять таких унтерменшей, как я, в будущем? Я вообще изначально в 23 года узнал о веб-программировании, но сказали, что из-за орды школьников пробиться даже на стажера почти нереал.

Не своди все свои топики на ПТ о жизни
6 июл 20, 07:44    [22162508]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Zzz79
Member

Откуда:
Сообщений: 583
Alexandrietz
Zzz79,

Moscow

если есть диплом о технической вышке - стучись в любой бодишоп - если диплома нет зайти в IT сферу будет невозможно
Это первый же вопрос любого HR,ты вроде говорил что 3 курса окончил в универе- мей би есть какие то универы кто возьмут это в зачет- и поступай на it заочно - через 2-3 года получишь диплом и я тебе гарантию даю - заедешь сразу мидлом в любой бодишоп
6 июл 20, 09:23    [22162525]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

А какие ты галеры знаешь, даже самые херовые, где могут взять таких унтерменшей, как я, в будущем? Я вообще изначально в 23 года узнал о веб-программировании, но сказали, что из-за орды школьников пробиться даже на стажера почти нереал.

По конторам ничего не мог сказать. Щас ситуация меняется каждый квартал.
Нет никакого инсайда у меня. Иди в крупные галеры (от 10 000 чел) стажёром.
И спокойно там расти до джуна.

Тыж сам говорил что деньги для тебя не имеют значения. Вот и посиди пол-годика
без амбиций.
6 июл 20, 10:03    [22162547]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
Zzz79,

Все разное говорят. Нет, у меня нет технической ВО. Поэтому не знаю, что делать. Если только идти в Бауманку ради технопарка. Потому и спросил про галеры, где есть возможность дорасти до джуна.
6 июл 20, 15:03    [22162806]     Ответить | Цитировать Сообщить модератору
 Re: Не могу понять, в чем ошибка в Merge-Sort.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Ок, а если дорасту до джуна теоретически, дальше что?
6 июл 20, 15:09    [22162813]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Java Ответить