Зачем знать алгоритмы сортировки
29 Января 2019 Программирование 
5 
2
На первом стриме меня спросили, какие алгоритмы нужно знать и я в качестве основных назвал поиск и сортировку. Сегодня под одним из видео о алгоритмах заметил много комментариев о том, что знание алгоритмов сортировки нужно только для ответа на собеседовании на вопрос, который любят задавать.
На самом деле знание базовых алгоритмов необходимо не только для прохождения собеседования, но и для саморазвития и умения решать типовые задачи.
Возможно вы даже не замечаете, как вы используете эти знания. Понимание алгоритмов даже сортировки, даже пузырьком позволяет вам понять просто типичные решения пробелем, которые вы будете накладывать в других задачах.
Очень часто нам не нужно реализовывать сортировку, уже все за нас сделано, особенно в простых прикладных приложениях. Но в алгоритмах сортировки и поиска есть что-то более важное. Если вы знаете их, то на примерах уже видели, как разные задачи решаются простым делением (поиск, сортировка) и можете использовать этот же патерн в других задачах.
На собеседованиях как раз начали в последнее время спрашивать на много более сложные вопросы. У меня на работе вообще спрашивают банальный вопрос о поиске в строке и то из 10 человек пока только один смог решить проблему более менее терпимо, хотя задача реально банальная.
Проблема в том, что многие не знают даже базовых алгоритмов и когда им говоришь — а найди мне что-то, они начинают тупо решать проблему в лоб, потому что нет багажа знаний, а потом так же и решают на работе задачи. И слава богу появился LINQ, благодаря которому C# программистам не нужно знать алгоритмы вообще, если уметь хорошо пользоваться LINQ. А стоит дать программисту PHP, как они вообще в ступор входят.
Понравилось? Кликни Лайк, чтобы я знал, какой контент более интересен читателям. Заметку уже лайкнули 2 человек
Сортировки
Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. Сортирующие сети), время работы которых в лучшем случае $O(\log n)$.
Классификация сортировок
Время работы
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
Память
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
Устойчивость
Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
Количество обменов
Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
Детерминированность
Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.
Сравнение сортировок
Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.
| Название | Лучшее время | Среднее | Худшее | Память | Устойчивость | Обмены (в среднем) | Описание |
|---|---|---|---|---|---|---|---|
| Сортировка пузырьком (Bubble Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. |
| Сортировка вставками (Insertion Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован. |
| Сортировка Шелла (Shellsort) |
$O(n\log^2)$ | Зависит от выбора шага | $O(n^2)$ | $O(1)$ | Нет | $O(n^2)$ | Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах. |
| Сортировка выбором (Selection Sort) |
$O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Нет | $O(n)$ | На $i$-ом шаге алгоритма находим минимальный среди последних $n — i + 1$, и меняем его местами с $i$-ым элементом в массиве. |
| Быстрая сортировка (Quick Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (маловероятно) |
$O(\log n)$ (стек вызовов) |
Нет | $O(n \log n)$ | Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них. |
| Сортировка слиянием (Merge Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ (обычная реализация) $O(1)$ (модифицированная реализация) |
Да | $O(n \log n)$ | Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии. |
| Timsort | $O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Да | $O(n\log)$ | Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием. |
| Сортировка кучей (Heap Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Нет | $O(n \log n)$ | Строим из массива кучу, по очереди извлекаем минимум кучи. |
| Плавная сортировка (Smoothsort) |
$O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(1)$ | Нет | $O(n\log)$ | Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо. |
| Терпеливая сортировка (Patience sorting) |
$O(n\log)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Нет | $O(n\log)$ | Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. |
| Сортировка с помощью бинарного дерева (Tree Sort) |
$O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | $O(n)$ | Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания. |
| Карманная сортировка (Bucket Sort) |
$O(n + k)$ | $O(n \log_k n)$ | $O(n \cdot k)$ | $O(n)$ | Да | — | Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения. |
| Цифровая сортировка (Radix Sort) |
$O(n \lg n)$ | $O(n \lg n)$ | $O(n \lg n)$ | $O(n)$ | Да | — | Сортировка объектов равной длины, имеющих «разряды». обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим. |
| Сортировка подсчетом (Counting Sort) |
$O(n)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | Да | $O(n + k)$ | Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа. |
| Сортировка Хэна (Han’s Sort) |
$O(n \log \log n)$ | $O(n \log \log n)$ | $O(n \log \log n)$ | $O(n)$ | Да | $O(n \log \log n)$ | Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона. |
| Многопоточная сортировка слиянием (Multithreaded merge sort) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(n)$ | Да | $O(n \log n)$ | Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток. |
| PSRS-сортировка (PSRS-sorting) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(N_^2)$ | Нет | $O(n \log n)$ | Разделим массив на $N_$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы. |
См. также
- Поисковые структуры данных
- Приоритетные очереди
- Поиск подстроки в строке
Источники информации
- Википедия — Алгоритмы сортировки
- Wikipedia —Sorting algorithm
- Хабрахабр — Бенчмарк алгоритмов сортировки
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2
Для чего надо столько алгоритмов сортировки?
Есть куча эффективных алгоритмов сортировки, навскидку помню : Хоара, Слиянием, Пирамидальная. Кто-то устойчив, кто-то нет. Для каких целей их так много?
Отслеживать
задан 29 ноя 2013 в 19:21
2,444 3 3 золотых знака 27 27 серебряных знаков 42 42 бронзовых знака
Ну например один алгоритм работает более эффективно с мелкими массивами данных, другой наоборот — с большими. Один алгоритм используется для обучения, а другой уже в продакшене.
29 ноя 2013 в 19:58
У верблюда два горба, потому что жизнь — борьба.
29 ноя 2013 в 20:26
@voipp, если интересно поиграться (в Linux), то можете скачать. Одно время я тоже увлекся этой темой. Там «измеритель» (его нужно править для задания разных наборов данных) и довольно много разных быстрых сортировок.
29 ноя 2013 в 20:51
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
А зачем нужно столько разных моделей телефонов или машин? По той же причине. Кому то нужна чуточку выше, кому-то, чуточку легче.
С алгоритмами сортировки такая же история. Разные люди придумывали свои алгоритмы для своих специфических задач. Одни алгоритмы хороши для больших объемов, другие — для почти отсортированных данных, третьи, когда есть много памяти или когда памяти впритык.
- И снова про сортировки: выбираем лучший алгоритм
- Алгоритмы и структуры данных — шпаргалка
Отслеживать
ответ дан 29 ноя 2013 в 20:05
112k 6 6 золотых знаков 93 93 серебряных знака 159 159 бронзовых знаков
Ответ — потому что. Дело в том, что есть разные ситуации. В каких-то ситуациях нет ограничений на время или на кол-во потребляемой памяти при сортировке. В некоторых случаях необходимо, чтобы объекты сортировались с учетом исходной последовательности (это и есть устойчивость сортировки). Иногда требуется, чтобы сортировка была максимально быстрой, при этом есть какие особенности во входных данных. Учитывая, что компьютер «тупой», то программист должен ему подсказать какой алгоритм выбрать в каждом конкретном случае. Поэтому и нужно знать разные алгоритмы и их слабые и сильные стороны, чтобы выбрать необходимый для решения конкретной задачи.
Отслеживать
ответ дан 30 ноя 2013 в 0:44
14k 33 33 серебряных знака 46 46 бронзовых знаков
- сортировка
- алгоритм
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.1.26.3951
Суть алгоритмов программирования. Для чего они нужны?
Каждый программист знает о важности использования алгоритмов. В этой статье мы поговорим о том, что такое алгоритм и какими характеристиками он обладает. А самое главное — составим список алгоритмов, которые широко применяются в программировании на разных языках и, стало быть, будут полезны для любого программиста.
Algorithm — что это?
Если говорить неофициально, то алгоритмом можно назвать любую корректно определённую вычислительную процедуру, когда на вход подаётся какая-нибудь величина либо набор величин, а результатом выполнения этой процедуры становится выходная величина либо набор значений. Можно сказать, что алгоритм — это некая последовательность действий (вычислительных шагов), благодаря чему происходит преобразование входных данных в выходные данные.
Также нужно понимать, что алгоритм как последовательность шагов позволяет решать конкретную задачу и должен: 1. Работать за конечный объём времени. Если алгоритм не способен разобраться с проблемой за конечное количество времени, можно сказать, что он бесполезен. 2. Иметь чётко определённые инструкции, порядок. Любой шаг должен точно определяться. Его инструкции должны быть однозначны для любой последовательности шагов. 3. Быть пригодным к использованию. Алгоритм должен быть способен решить проблему, для устранения которой его создавали.
Если интересуют подробности, вот отдельные статьи про свойства алгоритма, а вот про способы представления и записи алгоритма.
Сегодня алгоритмы используются при обработке данных как в информатике и программировании, так и в математике. Кстати, наиболее ранними математическими алгоритмами называют разложение на простые множители и извлечение квадратного корня — их использовали в древнем Вавилоне ещё в 1600 г. до н. э. Но мы не будем уходить далеко в прошлое, а рассмотрим, как и обещали, основные алгоритмы программирования на сегодняшний день.
Алгоритмы сортировки (пирамидальная, быстрая, слиянием)
Какой алгоритм сортировки считают лучшим? Здесь нет однозначного ответа, ведь всё зависит от ваших предпочтений и поставленных перед вами задач. Рассмотрим несколько основных: 1. Сортировка слиянием. Важнейший на сегодня, базируется на принципе сравнения элементов и задействует подход «разделяй и властвуй», позволяя более эффективно решать проблемы, которые когда-то решались за время O (n^2). Сортировка слиянием была изобретена математиком Джоном фон Нейманом в далёком 1945 году. 2. Быстрая сортировка. Это уже другой подход и несколько иная процедура. Тут алгоритм базируется, как на in-place разделении, так и на принципе «разделяй и властвуй». Однако эта сортировка нестабильна, что и является её проблемой. Зато алгоритм эффективен при сортировке массивов в оперативной памяти. 3. Пирамидальная сортировка. Алгоритм in-place который использует приоритетную очередь (за счёт этой очереди сокращается время поиска данных).
Некоторые пользователи утверждают, что именно благодаря алгоритмам сортировки у нас сегодня есть искусственный интеллект, глубинный анализ данных и даже интернет.
Преобразование Фурье. Быстрое преобразование Фурье
Электронно-вычислительные устройства используют алгоритмы для функционирования, в том числе и алгоритм преобразования Фурье. И телефон, и смартфон, и компьютер, и маршрутизатор, и интернет — всё это не может работать без алгоритмов для функционирования, запомните это.
Dijkstra’s algorithm
Без этого алгоритма, опять же, не сможет эффективно работать тот же интернет. С его помощью решаются задачи, в которых проблема представляется в виде графа, обеспечивающего поиск наикратчайшего пути между 2-мя узлами. Даже сегодня, когда у нас есть решения и получше, программисты по-прежнему используют поиск кратчайшего пути, если речь идёт о системах, требующих повышенной стабильности.
Algorithm RSA
Пришёл к нам из криптографии и сделал криптографию доступной всем, предопределив её будущее. Вообще, он служит для решения простой задачи с неочевидным решением и позволяет делиться открытыми ключами между конечными пользователями и независимыми платформами таким образом, чтобы можно было применять шифрование.
Алгоритм безопасного хэширования
Ну, это не совсем algorithm. Скорее, его можно назвать семейством криптографических хэш-функций (SHA-1, SHA-2 и т.д.), которые разработаны в США и имеют важнейшее значение для всего мира. Антивирусы, электронная почта, магазины приложений, браузеры и т. п. — во всём этом используются алгоритмы безопасного хэширования (на деле хэш является результатом их работы). Алгоритм служит для определения, удалось ли пользователю загрузить то, что хотелось, а также не подверглись ли вы фишингу или атаке «человек посередине».
Анализ связей
Идея анализа связей проста. К примеру, вы легко сможете представить график в виде матрицы, что сведёт задачу к проблеме уровня собственной значимости каждого узла. Данный подход к структуре графа позволит оценить относительную важность каждого объекта, который включён в систему.
Algorithm был создан в далёком 1976 году и используется сегодня при ранжировании страниц в процессе поиска в Google, при генерации ленты новостей, при составлении списка возможных друзей на Facebook, при работе с контактами в LinkedIn и во многих других случаях. Любой из перечисленных сервисов работает с различными объектами и параметрами и объектами, однако сама математика по сути не меняется.
Пропорционально-интегрально-дифференцирующий algorithm
Пользовались ли вы автомобилем, самолётом, сотовой связью? Видели ли вы робота в работе? Во всех этих случаях вы можете сказать, что видели данный algorithm в действии.
Его обычно применяет замкнутый механизм обратной связи для контура управления. Это необходимо для минимизации ошибки между реальным выходным сигналом и желаемым выходным сигналом. Задействуется там, где необходимо создать систему для обработки сигнала либо для управления гидравлическими, механическими и тепловыми механизмами автоматизированного типа.
Сжатие данных
Сложно сказать, какой algorithm для сжатия наиболее важен, ведь в зависимости от поставленных задач он может меняться от zip до mp3 либо от JPEG до MPEG-2. Но эти алгоритмы важны почти для всех сфер деятельности.
Алгоритм сжатия — это не только очередной заархивированный документ. Он позволяет выполнять сжатие данных на веб-странице при их загрузке на компьютер. Или задействуется в базах данных, видео, музыке, облачных вычислениях. По сути алгоритмы сжатия данных делают системы дешевле и эффективнее.
Алгоритм генерации случайных чисел
На самом деле не существует «настоящего» генератора случайных чисел, и мы уже об этом говорили. Зато у нас существуют генераторы псевдослучайных чисел, которые прекрасно делают свою работу. Они имеют расширенную вариативность использования: программные приложения в программировании, криптография, алгоритмы хэширования, видеоигры, искусственный интеллект, тесты при разработке программ и т. д.
Алгоритмы в науке и технике
Роль алгоритмических последовательностей в современной науке и технике очень велика. Их без преувеличения считают богатством науки и техники, которое накапливалось десятилетиями. Можно вспомнить пресловутую машину Тьюринга и не только.
Однако на деле наибольшее значение имеют algorithms, которые накоплены в математике, ведь именно математика пронизывает иные технические науки и делает их более структурированными. Замечено, что если удается получить алгоритмическую последовательность данных, позволяющую решить конкретную задачу, то можно создать соответствующую машину, что если удалось получить алгоритм решения какой-нибудь задачи, то можно создать машину, стало быть, автоматизировать решение этой задачи. А автоматизация важна не только в IT-сфере, но и в промышленности, технике, науке, медицине и многих других отраслях.
С этой точки зрения суть алгоритмов можно выразить иначе, то есть они являются: — формой изложения научных данных, результатов исследований и анализа; — реальным руководством к действию по решению ранее изученных проблем; — средством экономии времени и умственной работы; — важным и нужным этапом по автоматизации; — инструментом исследования новых проблем (особенно в математике).
Да, algorithms — важная часть как всей науки, так и локальной обработки исходных данных, но эта часть не исчерпывает содержание самой науки. Не менее важны понятия и определения, которые входят в эту науку, установленные факты (доказанные теоремы), выработанные подходы к изучаемым явлениям и объектам.
Раз уж вспомнили математику, скажем, что большой вклад в развитие алгоритмов здесь внесли советские (российские) ученые. К примеру, хорошо известен так называемый алгоритм четырех русских — метод алгоритмического ускорения с использованием булевых матриц. Он был создан четырьмя русскими учеными В. Л. Арлазаровым, Э. А. Диницем, М. А. Кронродом и И. А. Фараджевым в 1970 г. в Москве. Также упоминания заслуживает один известный метод русского ученого Анатолия Карацубы — созданный им алгори тм служит для быстрого умножения. И так далее.
Говорить на эту тему можно очень долго. Если же вы хотите освоить нужные алгоритмические последовательности на практике и в контексте программирования, добро пожаловать на специальный курс в OTUS!