Для ЯПматематиков пост: визуализация работы 19 алгоритмов сортировки

 [ Версия для печати ]
Добавить в Telegram Добавить в Twitter Добавить в Вконтакте Добавить в Одноклассники
Страницы: (3) 1 2 [3]   К последнему непрочитанному [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]
48576719297 13 апр. 2020 г. в 22:24
Юморист  •  На сайте 6 лет
0
Звук похож на zx spectrum

Размещено через приложение ЯПлакалъ
Tipakrut 13 апр. 2020 г. в 22:28
Шутник  •  На сайте 11 лет
1
Цитата (pupch @ 13.04.2020 - 15:25)
это ж разве визуализация? учитесь у цыган

Неплохо, ещё в курсе cs50 неплохо объясняют.

Размещено через приложение ЯПлакалъ
АйфонФеррари 13 апр. 2020 г. в 22:40
Ярила  •  На сайте 9 лет
2
Сижу себе, никого не трогаю, примус починяю массивы сортирую
Стамп 13 апр. 2020 г. в 23:21
а ты не ной  •  На сайте 13 лет
0
Цитата (b0bo4ka @ 13.04.2020 - 15:05)
Волшебно!
Про большую часть методов даже не слышал.

о да !! доставило
plotnick 13 апр. 2020 г. в 23:41
Ярила  •  На сайте 14 лет
0
Да прикольно посмотреть, но нужно внимательно за таймингом следить, некоторая визуализация выглядит быстрее прочих, а по таймингу намного медленнее. Например gravity sort.

Размещено через приложение ЯПлакалъ
Сугроб61 13 апр. 2020 г. в 23:49
Ярила  •  На сайте 7 лет
0
Рамштайн? шото новое?

Размещено через приложение ЯПлакалъ
Готтфрид 14 апр. 2020 г. в 00:10
Юморист  •  На сайте 9 лет
0
Ну дык квиксторт на то и квик
Юрковский 14 апр. 2020 г. в 08:45
Юморист  •  На сайте 17 лет
-1
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

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

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

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

Не поверишь, но после института "пузырёк" не пригодился в жизни ни разу. На небольших массивах даже вульгарный полный перебор работает быстрее. На больших или динамических массивах - "дерево" наше всё. Квик-сорт хорош, без всякого сомнения, но в тени его не запустишь, приходится отрубать запись в массив.
ssmsska 14 апр. 2020 г. в 09:12
Балагур  •  На сайте 10 лет
1
Странное видео. Массив разбивался то на 100 частей то на 650, то еще на сколько-то, постоянно разное количество. То скорость была в реальном времени, то в перемотке. При чем нигде это не акцентировалось. И зачем было сделано категорически не понятно.
Сиди с лупой разбирайся где сколько фрагментов и сколько времени было затрачено на массив, потом доставай калькулятор и выводи коэффициент скорости.

Это не для математиков, а для гуманитариев ИМХО. Картинка красивая просто.

Это сообщение отредактировал ssmsska - 14 апр. 2020 г. в 09:12
gods02 14 апр. 2020 г. в 11:17
Ярила  •  На сайте 7 лет
0
Цитата (artivenom @ 13.04.2020 - 22:07)
Цитата (gods02 @ 13.04.2020 - 19:00)
Цитата (Уфимский @ 13.04.2020 - 16:22)
Цитата (denisg2 @ 13.04.2020 - 15:49)
Обычно доверяю сортировку SQL серверу. "order by" решает.

Ну-ну... Давай из жителей Москвы, например, сделай сортировку по ИНН. Просто интересно: насколько сервер зависнет... shum_lol.gif

А сервер так и работает.
Фактически, он создает временный индекс по полю "ИНН", сортирует его, и, затем, на основании этого индекса расставляет результаты.
Так что специфический подбор метода сортировки для конкретного массива вряд ли будет более эффективней, чем стандартный метод сервера.
Ну, и откровенно говоря, 20 млн. записей - не такая уж большая база cool.gif
думаю, на современном сервере результат будет в районе 1 секунды.

Ну хз на счёт именно БД, всё же там реализовано дерево, а не хэш, в том числе и в индексе. Возможно там есть спец. оптимизация для чисел. Но по общему правилу сортировка дерева будет всегда сложнее и медленнее, чем вставить записи в 1 проход в массив по очереди. Смысл именно в том, что индекс элемента массива = значению ИНН. 1 обход побитого массива и всё отсортировано. Быстрее варианта не может существовать просто. даже с индексом.

там свой оптимизатор работает.
В данном конкретном случае, нужно смотреть план выполнения и там будет описано, какой индекс строится, почем и какого типа.
Кстати, инн , возможно, будет сортироваться как строковая переменная длиной 12 символов, с ведущими " "
ichthyandr 14 апр. 2020 г. в 11:31
водоплавающий  •  На сайте 11 лет
0
Цитата (Уфимский @ 13.04.2020 - 15:20)
Сортировка пузырьком / Bubble sort
...

там еще такое было

Сортировка «Американский флаг» :: American Flag Sort

тыц
ichthyandr 14 апр. 2020 г. в 11:33
водоплавающий  •  На сайте 11 лет
1
Цитата (Юрковский @ 14.04.2020 - 08:45)
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

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

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

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

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

вы путаете две задачи:
1. Задача сортировки
2. Задача поиска

Поиск производится или по сортированному массиву или по дереву. На видео "древесных" структур нет

Это сообщение отредактировал ichthyandr - 14 апр. 2020 г. в 11:35
ichthyandr 14 апр. 2020 г. в 11:50
водоплавающий  •  На сайте 11 лет
0
Цитата (Zeugl1271 @ 13.04.2020 - 21:45)
std::sort(std::begin(),std::end(),[](const &){...}); и ебись оно конём!

ооо, вижу лямду тут! pray.gif
sobor 14 апр. 2020 г. в 11:52
Ярила  •  На сайте 15 лет
-1
Только что дошло, что сортировка произошла от слова сортир
OTMOPO3OK 14 апр. 2020 г. в 15:11
Ветеран Япа  •  На сайте 21 год
0
Надо было ещё статью скопировать


https://habr.com/ru/post/335920/
Юрковский 14 апр. 2020 г. в 20:14
Юморист  •  На сайте 17 лет
0
Цитата (ichthyandr @ 14.04.2020 - 11:33)
Цитата (Юрковский @ 14.04.2020 - 08:45)
Цитата (riv1329 @ 13.04.2020 - 18:02)
Цитата (Eymerich @ 13.04.2020 - 15:16)
Круто. Сколько плохих методов оказывается есть.

зы а, забыл. Я так венду писал (par9)


В защиту "пузырька".

Не все так просто. Скорость каждого алгоритма очень сильно зависит от объема и типа данных. У умных алгоритмов делается меньше шагов, чем у тупого пузырька в пересчете на единицу данных, но сам шаг длиннее.

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

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

Но дело не только в скорости. Бывает что ситуация накладывает ограничения на возможность использования дополнительной памяти. Для пузырька нужна лишь одна лишняя ячейка. Рекурсивные алгоритмы потребляют память на стек тем больше, чем больше выборка (но не пропорционально больше). Для некоторых алгоритмов вообще заранее невозможно подсчитать необходимое количество памяти, что согласитесь, "не айс": программа может "вылететь" из-за нехватки доступной памяти раньше чем закончит сортировку.

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

вы путаете две задачи:
1. Задача сортировки
2. Задача поиска

Поиск производится или по сортированному массиву или по дереву. На видео "древесных" структур нет

Никак не пойму, за что мне влепили шпалу. Нет, я ничего не путаю. Есть такой метод сортировки массива, метод "дерева". При этом создаётся полная новая версия массива, и память, да, кушается прилично. Преимущества этого метода в том, что отключать режим записи в исходный массив нужно только в самый последний момент перед компоновкой нового.

Дерево данных от массива данных я таки отличаю с 1988-го года, честно. Не надо уж всех присутствующих за дурачков то считать, я думал, в этой теме собралось приличное общество ))
Понравился пост? Еще больше интересного в Телеграм-канале ЯПлакалъ!
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) Просмотры темы: 12886
0 Пользователей:
Страницы: (3) 1 2 [3]  [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]


 
 



Активные темы






Наверх