Java. Сортировка слиянием.
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- В данном видео приведен детальный разбор алгоритма сортировки слиянием, а так же рассматривается вариант реализации этого алгоритма на языке программирования Java. Кроме этого проводится сравнение эффективности работы сортировки слиянием и быстрой сортировки.
Исходный код:
github.com/Arh...
Поддержать канал💰:
yoomoney.ru/to...
#ArhiTutorialsJava #ityoutubersru
под эту музыку, когда сказал, что остается один элемент 36, которому не нашлось пары, я чуть слезу не пустил)
нифига себе просто , мне на неделю этого видео наверное хватит щас сидеть разбираться :)
это лучшее видео о merge() что я смог найти !!!
После восьми просмотров ЗАШЛО!!! Спасибо тебе, добрый человек!)
Отличное видео, доходчивая подача, складная речь.
Отличный материал. Спасибо огромное !
Я бы добавил в аннотации @cpu, @ram, чтобы сразу были видны сложности алгоритма, по памяти и по скорости работы.
Еще раз Спасибо!
Большое вам спасибо! Очень хорошо все объяснили и детально показали. Отдельное спасибо за код на гитхабе.
Большое спасибо вам за видео!
Спасибо вам, человечище!
Измеритель времени понравился, спасибо
Спасибо большое! Очень круто! 👍
Отличные видео,спасибо вам!
Большое спасбио за полезный и понятный урок!
Очень доходчивое объяснение. Спасибо, автору!
Но глядя на сам алгоритм, невольно назревает вопрос, много ли вообще людей, которые могут удержать в голове все те индексы, которые постоянно скачут в этой реализации?
Сидел, тыкался в дебаггер. Пытался понять и запомнить все связи, но это очень тяжело. Общая идея то ясна, но когда доходит до реализации с кучей индексов и циклов по динамически изменяющимся массивам, мозг ломается.
Теперь думаю, может есть какие-то другие реализации сего алгоритма. Где все не настолько запутано
Сделал методом рекурсии. Код стал в разы читаемее и яснее. Однако скорость работы сортировки слиянием при рекурсивной реализации стала примерно в 3-4 раза медленнее (!) при работе с массивом из 100 тысяч случайных целых чисел со значениями от -500_000 до +500_000 по сравнению с реализацией из этого урока. Так придется выбирать между производительностью и читаемостью кода))
лайк за музон из диско элизиум
Спасибо, очень познавательно!!!
Огромное спасибо!
Спасибо за нормальное объяснение !
Спасибо за видео!
спасибо большое за видео) очень подробно объясняется. Какая будет асимптотика у этой реализации( по On и ram(память)) спасибо
Даровенько Серый, не плохо объясняешь, но есть недостатки, вот бы ты хоть мельком показал весь код включая входные данные, вот для новичков и это проблема, в нэте проблема эту сортировку найти целиком в рабочем состоянии!) Ну и на будущее показывай пожалуйста весь код хоть мельком.
Хорошо. Думаю, не выложить ли мне код всех алгоритмов на гитхаб. Это будет по удобнее чем с видео переписывать)
@@arhitutorials Сергей выложи хоть куда нибудь плиз, второй день бьюсь, без вариантов, я уже 4 месяца изучаю java, полиндром написал и много ещё чего, надо сорт. слиянием выучить. Только на git подпиши их на будущее. Если выложишь дай знать пожалуйста.
@@dusheslov2700 , постараюсь завтра-послезавтра выложить код, как будет готово, напишу ссылку.
@@arhitutorials Буду благодарен.
@@dusheslov2700 , выложил исходный код
github.com/Arhiser/java_tutorials/blob/master/src/ru/arhiser/sort/MergeSort.java
Добавил ссылку в описание к видео.
А можно сделать разбор обхода дерева ходов в игре с ненулевой конечной суммой и альфа-бета отсечением? Типа как в шахматных программах делают, но на более простом примере, например, крестики-нолики или что-нибудь сравнимое по простоте. Пытался постичь альфа-бета отсечение, но про него во всех источниках или так муторно, что невозможно понять, или очень поверхностно, типа, и так всё само собой очевидно и пояснений не требует. Вот такой же понятно разобранный практический пример по этой теме был бы очень кстати.
Спасибо
Сергей, здравствуйте! Объясните, пожалуйста, почему при исходном массиве размером в 11 элементов, алгоритм сортирует некорректно?
Здравствуйте! Дайте тестовый пример на котором сортировка работает некорректно.
@@arhitutorials {15,78,89,9,12,12546,8,879,16,54,1}
@@ЕвгенийЛебедев-в5ы Исправил
github.com/Arhiser/java_tutorials/commit/565928296825898c738a3d4146b1afb48acae272
Моя ошибка. Не было обработки для случая, когда не с чем сливать остаток массива.
@@arhitutorials спасибо большое за материал!
@@arhitutorials насчет этого исправления, есть сомнения в правильности кода.
Я думаю, раз уж метод merge() имеет аргумент "destStart", полагаю, он рассчитан на работу, когда слияние двух массивов в третий ("dest") производится с индекса "destStart".
Т.к. "destStart" может отличаться от "src1Start", итерироваться в цикле for с помощью "i" можно только по одному из массивов. Для другого придется использовать другой итератор ("index1"). При этом следует корректно определить условие цикла.
if (src1Start + size > src1.length) {
for (int i = d_start; i < Math.min(desk.length, left.length); i++) {
desk[i] = left[index1++];
}
return;
}
топ
вроде-бы пропущена половина, нет??? сначала массив делится постепенно до маленьких частей, а потом так-же собирается и упорядочивается.
это рекурсивная сортировка слиянием???
быстрая сортировка не делит на части, а скорее отгрызает небольшие куски из левой части массива, которые сортируются за один прием, затем снова отгрызает кусок
Прикольно массив из 13 элементов становится массивом из 12 элементов... Это так зачем не понимаю?..
Решение перегружено лишними параметрами и переменными. Плюс, грех рассказывать про сортировку слиянием и не уделить времени рекурсивной реализации... Которая, кстати, займет меньше 30 строк кода. Тем не менее, условие внутри цикла слияния у метода merge понравилось.
увы но этот алгоритм не правильно отработает если второй массив будет больше первого
Протестировал на массивах разных длин, неправильную работу получить не удалось. Если вам не сложно, напишите пожалуйста тестовый пример, на котором алгоритм неправильно работает. Если есть ошибка, ее надо исправить.
@@arhitutorials
print(intext1)
print(intext2)
res = c = [c * '' for c in range(len(intext1)+len(intext2))]
#res=[]
index_intext1=0
index_intext2=0
for i in range(len(intext1)+len(intext2)):
if ((index_intext1=len(intext2)) or (intext1[index_intext1] < intext2[index_intext2])):
res[i]=intext1[index_intext1]
#res.append(intext1[index_intext1])
index_intext1=index_intext1+1
else:
#res.append(intext2[index_intext2])
res[i] = intext2[index_intext2]
index_intext2 = index_intext2 + 1
print(res)
['1', '4', '9']
['1', '8', '27', '88']
['1', '1', '4', '8', '27', '88', '9']
@@arhitutorials на яве всё работает, значит у меня ошибки
15.10.2022
а куда делось второе число 42? )))