509

Алгоритмы: сортировка вставками и слиянием

Как быть, если есть массив, и его нужно отсортировать? В программировании это случается почти* каждый день. К счастью, сегодня мы перевели для вас новую часть курса алгоритмов — ту самую, где профессор Девадас рассказывает про эту фундаментальную задачу и способы её решения.

Устраивайтесь поудобнее, будет интересно.

Для вас старались:

Переводчики — Даниил Левицкий, Дерсим Даваод

Редактор и монтажёр — Олег Жданов

Корректор — Дмитрий Мирошниченко


Если ты умеешь в английский, русский или какую-нибудь тему наших переводов — присоединяйся к нам, мы найдём что-нибудь интересное и для тебя.


* по данным программистов, ежедневно пишущих сортировку

Дубликаты не найдены

+18

В нашем политехе объясняют гораздо проще и быстрее...

раскрыть ветку 3
+9

да! берешь из фреймворка существующую функцию и пишешь array.Sort() и не ебешь себе мозги всякими сортировками, потому что любая хуета, что ты напишешь будет хуже встроенной в фреймворк функции

раскрыть ветку 2
+2

А если тебе вдруг понадобится оптимизировать, то значит ты что-то делаешь не то.

-1

он объясняет не то как делать сортировку, а как грамотно писать алгоритмы.  преимущества принципа "разделяй и влавствуй" это возможность использовать неблокируемую многопоточность. Просто пример. последовательно Фибоначчи, подсчитать его в несколько потоков обычным складыванием невозможно, но если использовать подход через матрицы который O(logn) для расчета опорных значений, можно в несколько потоков рассчитать всю последовательность.
А вот такие как ты пишешь, пишут singlethread, где перфомансом даже не пахнет, при этом всё это говно крутится на 32 ядерном сервере, но на 1 ядре, дай бог

+7
Пффф....
Иллюстрация к комментарию
+5

Сперва подумал, что это - очередная бестолковщина, когда профессор МИТ целый академический час льёт воду в уши первокурам. (А такие лекции на ютубе - в ассортименте!).

Но потыкал и убедился в обратном: к счастью, хоть немножко фундамента с оценками сложности здесь есть.


Всё равно, 50 минут трындежа можно было легко заменить распечаткой субтитров с небольшим количеством слайдов-скриншотов, на чтение и рассматривание которых уйдёт меньше времени.

Формат таких видео-лекций - остаюсь при своём ИМХО - избыточен. Только если кому-то хочется потренироваться в слушании американского английского.


А для того, чтобы зритель мог сориентироваться, - втыкать ему в лекцию или мимо пройти, - нужен развёрнутый анонс. А не кликбейт "профессор дал решение фундаментальной задачи! смотреть бесплатно! будет интересно!"

Тем паче, что в жизни мало кто использует именно упомянутые алгоритмы в чистом виде. Потому что один из них асимптотически тупой (квадратный), а второй имеет отвратительный коэффициент при логлинейной асимптоте. И любой не-первокур об этом знает.

И на практике используют, например, всякие комбинации из квиксорта, слияния и вставок.

И поэтому заголовок выглядит кликбейтом и обманом, а к кликбейту в интернете сами знаете, какое отношение.

раскрыть ветку 8
0

"И на практике используют, например, всякие комбинации из квиксорта, слияния и вставок." можно пример? желательно на java:D

раскрыть ветку 7
+2

Я в потроха явовского фреймворка не полезу.

А в реализациях стандартной библиотеки для C++ бывают варианты.


Например, в убунте, реализация библиотеки от Silicon Graphics, сделано так:

- на глубину рекурсии, равной логарифму длины массива, выполняется частичный квиксорт

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

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


Реализацию с промежуточным слиянием я тоже встречал, но давно (кажется, в Dinkumware - которую использовала Visual Studio), подробностей не упомню. Суть такая же: короткие массивы удобно сортировать вставками или слиянием (и даже можно выделить промежуточный буфер под это дело), массивы среднего размера - слиянием, если у нас есть достаточно памяти под промежуточный буфер, всё остальное - квиксорт. Как только доходим в рекурсии до соответствующего размера подмассива, применяем вставки или слияния.


Вообще, сортировке Дональд Кнут чуть не целый том посвятил. Там хватает рокетсаенса и дьяволов в деталях.

раскрыть ветку 1
+1
Стандартный сорт c++
сначала qsort, который обрывается на глубине, потом heap sort вроде, плюс сортировка 4х элементов за 5 сравнений явно
раскрыть ветку 4
+21

Нормальные программисты сортировку не пишут. Они используют библиотечный вызов sort().

раскрыть ветку 98
+23

ага, а потом к тебе в компанию приходят дауны, которые фреймворки и библиотеки используют как ёбаные книги заклинаний без малейшего понимания, что там вообще внутри происходит

раскрыть ветку 12
+14
а потом к тебе в компанию приходят дауны, которые фреймворки и библиотеки используют как ёбаные книги заклинаний без малейшего понимания, что там вообще внутри происходит

или хуже того, задорные ребята, которые долго пишут свои велосипеды  и страшно обижаются, если их прервать

раскрыть ветку 5
+15
Ну так работает же, чего трогать.
+7

это кем надо быть и что делать, чтобы не понять, что функция sort сортирует массив, скажем. нахуя мне знать, как она там внутри сортирует, если она сортирует. нахуя мне знать, что оно там недайбоже юзает красночерное дерево, вот нахуя? мне надо знать, например, что sort может сортить по ключу скажем, и знать, как это написать. но мне нахер не нужно знать, что там внутри ибо один хер ты лучше напишешь, 2) порой нету времени изобретать свою хуебистику с кучей багов, когда есть оттестированный встроенный sort.

раскрыть ветку 3
+1
Бизнесу гораздо выгоднее иметь узких специалистов, чем набирать тех, кто сходил в универ и поковырялся везде понемногу. Человек, пишущий исключительно на React без глубокого понимания алгоритмов, структур данных и прочей академии, в долгосрочной перспективе будет в десятки раз выгоднее (разработка, поддержка, ущерб от багов) при разработке фронтенда, нежели какой-нибудь даун, который «знает Java, Swift, React, Vue, Angular, RoR, Node.js».
+3

Это же просто шутка.


Кстати, а библиотечную функцию sort нормальные программисты пишут?

раскрыть ветку 25
+26

Это другая каста программистов

Там такие программисты, что они почти математики

раскрыть ветку 24
+1
Нормальные программисты

кодеры


Компетенция разработчика ПО подразумевает знание базовых алгоритмов без всяких отговорок. Как иначе оценивать асимптотическую сложность?

раскрыть ветку 15
+11

Знать и использовать - разные вещи. Нормальный программист должен прочитать всего Кнута. Но для сортировки вызывать библиотечный вызов sort().

раскрыть ветку 12
+1
Ох уж эти «настоящие программисты», у которых все сводится к экономии миллисекунд.
0
Работает и ладно
0

В зависимости от того что сортируешь. Лично писал сортировку (баккет +квик), обходящую стандартную почти в 2 раза (на наших данных)

-2
Но ты же не настоящий программист, если не умеешь на бумаге написать имплементацию пузырьковой сортировки! А еще, фреймворками пользуются только нубы, тру программеры все пишут с нуля на плюсах!!!
раскрыть ветку 3
+1

Наоборот. Нубы пишут всё сами - так как они ещё не знают фреймворки. Опытные используют возможности фреймворков.

раскрыть ветку 2
-8

я конечно только начала учить программирование, но мне кажется, что нормальные программисты могут писать сортировку, потому что рукописная может работать быстрее, чем библиотечная в некоторых случаях

раскрыть ветку 37
+25

В 99.99% случаев не может. Только в очень-очень некоторых, которые в 99.99% реальных приложений не встречаются.

раскрыть ветку 28
+1

Все 10-15 известных алгоритмов сортировки давно накожены и есть в дефолтных библиотеках.


А вообще всем насрать, код оптимизируют единицы, и то по приколу.

раскрыть ветку 1
0

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


Проблема в том, что написав какую то простенькую сортировку, она скорее всего будет работать хуже чем библиотечная. Потому, что над библиотечной работали не один человек и не один год, в ней уже исправили большинство детских ошибок.


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

0

В реальных приложениях всем срать на то, что там работает быстрее или медленней. Главное НАПИСАТЬ быстрее.


Я бы даже сказал, главное подписать акты приёма-передачи быстрее :)

раскрыть ветку 4
ещё комментарии
+1

Сортировка с помощью танца

https://www.youtube.com/watch?v=5JMInXAtnQg

+1

https://www.youtube.com/watch?v=Gnp8G1_kO3I

визуализация разных алгоритмов сортировки, со звуком :)

раскрыть ветку 7
+4

Поставил скорость х2, упал на пол и начал биться в конвульсиях

раскрыть ветку 4
+2

Там вроде звуки тоже параллельно сортируются

раскрыть ветку 1
0

Какой вы чувствительный.

раскрыть ветку 1
0

https://youtu.be/BeoCbJPuvSE вот наткнулся на сравнительную визуализацию с одинаковым временным масштабом

раскрыть ветку 1
0

Годнота! спасибо!

0

https://www.youtube.com/watch?v=WaNLJf8xzC4 вариант покороче и красочнее

0

тру HPC использует только сортировку пузырьком

раскрыть ветку 1
0

ебать ты жесткий))

0

Ребят, маленько оффтоп по кодингу: посоветуйте для python 3 материалы для изучения для джуна, базовые знания?

Изучаю чисто для себя.

раскрыть ветку 3
+1

Гвидо ван Россум,

Язык программирования Python


Марк Пилгрим,

Dive into Python


Ну и если совсем новичок
Крэйг Ричардсон,

Программируем с Minecraft. Создай свой мир с помощью Python

раскрыть ветку 1
0

Благодарю! 🍺

+1

Вот если бы для друга...

0

Имхо достаточно помнить принципы сортировки пузырьком и быстрой сортировки

0

С универа помню сортировку пузырьком, при необходимости смогу реализовать.

0
На курсе cs50 есть похожее
-2
Спасибо, посмотрел уже
раскрыть ветку 1
0

на ютубе просто раньше выложили )

-3

За несколько лет программирования использовал сортировку (стандартным методом, не вручную) от силы раз пять. А в универе целый курс был, да.


Сортировка переоценена. =)

раскрыть ветку 1
+2

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

-11

Я с филологии пришел, что за чушь он несет? :)

-14

Профессор в MIT читает студентам сортировки? А это точно студенты?


Алгоритмы сортировки ведь входят в школьный курс, не?

-18

Ну очень полезные знания

ещё комментарии
Похожие посты
Возможно, вас заинтересуют другие посты по тегам: