Что такое сортировка выбором
Сортировка выбором
Всем привет. Эту статью я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS.
Введение
Постановка задачи
Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.
Сортировка выбором
Одной из простейших сортировок является сортировка выбором.
Описание алгоритма
Реализация
Предлагаю посмотреть на реализацию данного алгоритма на языке C:
Анализ
В процессе вычислений, мы воспользовались сначала свойствами О — нотации, а затем формулой для вычисления суммы арифметической прогрессии.
Для порядка необходимо оценить еще и дополнительную память, которая требуется для выполнения алгоритма. Здесь все гораздо проще: мы выделяли память только для счетчиков цикла и переменной — буфера, позволяющей обменивать 2 элемента массива местами. Поэтому:
В результате анализа мы пришли к тому, что временная сложность алгоритма зависит от размера входного массива квадратично. Поэтому данную сортировку относят к классу квадратичных сортировок. Результат анализа не зависит от содержания массива: он верен в лучшем, в худшем и в среднем случае.
Также важно заметить, что сортировка выбором в такой реализации является устойчивой. Позволю себе напомнить, что сортировка называется устойчивой, если при ее выполнении порядок следования равных элементов не меняется. Это свойство не очень принципиально для такой учебной задачи, как сортировка массива чисел, но если бы мы сортировали какие-то более сложные объекты с установленным отношением порядка это могло бы быть важно. Подобный пример мы можем рассмотреть как-нибудь в следующий раз, когда будем говорить о поразрядной сортировке.
Двусторонняя сортировка выбором
Некоторый интерес может представлять оптимизация алгоритма, реализованного выше: во время прохода по неотсортированной части массива можно параллельно с минимальным элементом искать максимальный. Таким образом после итерации можно уменьшать неотсортированную часть массива не на единицу, а на двойку. Асимптотического улучшения алгоритма не происходит, но тем не менее скорость его выполнения может незначительно увеличиться, число сравнений ведь также увеличивается в два раза.
Рекурсивная сортировка выбором
В качестве упражнения можно попробовать написать алгоритм не с использованием цикла, а с использованием рекурсии. На java это может выглядеть следующим образом:
Итоги
Мы рассмотрели одну из квадратичных сортировок: сортировку выбором, посмотрели на устойчивую реализацию с использованием цикла, рекурсии, обсудили оптимизацию алгоритма с помощью двустороннего уменьшения неотсортированной части массива. Сортировка является исключительно учебной и не нашла широкого применения на практике.
Если вы хотите подробнее узнать о курсе, приглашаю всех на бесплатный вебинар, который пройдет уже 10 июля.
Сортировки выбором
В чём идея сортировок выбором?
Однако, сейчас в тренде нелинейность, поэтому, не написав ещё все публикации про сортировки вставками, сегодня начну параллельную ветку про сортировки выбором. То же самое потом сделаю для других алгоритмических классов: сортировок слиянием, сортировок распределением и т.п. Это в целом позволит писать публикации то по одной теме, то по другой. С таким тематическим чередованием будет веселее.
Сортировка выбором :: Selection sort
Просто и незатейливо — проходим по массиву в поисках максимального элемента. Найденный максимум меняем местами с последним элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает последний элемент, куда мы переставили найденный максимум). К этой неотсортированной части применяем те же действия — находим максимум и ставим его на последнее место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.
Сортировка простым выбором представляет из себя грубый двойной перебор. Можно ли её улучшить? Разберём несколько модификаций.
Двухсторонняя сортировка выбором :: Double selection sort
Похожая идея используется в шейкерной сортировке, которая является вариантом пузырьковой сортировки. Проходя по неотсортированной части массива, мы кроме максимума также попутно находим и минимум. Минимум ставим на первое место, максимум на последнее. Таким образом, неотсортированная часть при каждой итерации уменьшается сразу на два элемента.
На первый взгляд кажется, что это ускоряет алгоритм в 2 раза — после каждого прохода неотсортированный подмассив уменьшается не с одной, а сразу с двух сторон. Но при этом в 2 раза увеличилось количество сравнений, а число свопов осталось неизменным. Двойной выбор лишь незначительно увеличивает скорость алгоритма, а на некоторых языках даже почему-то работает медленнее.
Отличие сортировок выбором от сортировок вставками
Может показаться, что сортировки выбором и сортировки вставками — это суть одно и то же, общий класс алгоритмов. Ну, или сортировки вставками — разновидность сортировок выбором. Или сортировки выбором — частный случай сортировок вставками. И там и там мы по очереди из неотсортированной части массива извлекаем элементы и перенаправляем их в отсортированную область.
Главное отличие: в сортировке вставками мы извлекаем из неотсортированной части массива любой элемент и вставляем его на своё место в отсортированной части. В сортировке выбором мы целенаправленно ищем максимальный элемент (или минимальный), которым дополняем отсортированную часть массива. Во вставках мы ищем куда вставить очередной элемент, а в выборе — мы заранее уже знаем в какое место поставим, но при этом требуется найти элемент, этому месту соответствующий.
Это делает оба класса алгоритмов совершенно отличными друг от друга по своей сути и применяемым методам.
Бинго-сортировка :: Bingo sort
Интересной особенностью сортировки выбором является независимость скорости от характера сортируемых данных.
Например, если массив почти отсортирован, то, как известно, сортировка вставками его обработает гораздо быстрее (даже быстрее чем быстрая сортировка). А реверсно упорядоченный массив для сортировки вставками является вырожденным случаем, она будет его сортировать максимально долго.
А для сортировки выбором частичная или реверсная упорядоченность массива роли не играет — она обработает его примерно с той же скоростью что и обычный рандом. Также для классической сортировки выбором неважно, состоит ли массив из уникальных или повторяющихся элементов — на скорость это практически не влияет.
Но в принципе, можно исхитриться и модифицировать алгоритм так, чтобы при некоторых наборах данных работало быстрее. Например, бинго-сортировка учитывает, если массив состоит из повторяющихся элементов.
Здесь фокус в том, что в неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации. Это позволяет при повторяющихся максимумах не искать их заново каждый раз, а ставить на своё место сразу как только этот максимум в очередной раз встретили в массиве.
Алгоритмическая сложность осталась та же. Но если массив состоит из повторяющихся чисел, то бинго-сортировка справится в десятки раз быстрее, чем обычная сортировка выбором.
Цикличная сортировка :: Cycle sort
Цикличная сортировка интересна (и ценна с практической точки зрения) тем, что изменения среди элементов массива происходят тогда и только тогда, когда элемент ставится на своё конечное место. Это может пригодиться, если перезапись в массиве — слишком дорогое удовольствие и для бережного отношения к физической памяти требуется свести к минимуму количество изменений элементов массива.
Работает это так. Перебираем массив, назовём X очередную ячейку в этом внешнем цикле. И смотрим на какое место в массиве нужно вставить очередной элемент из этой ячейки. На том месте, куда нужно вставить находится какой-то другой элемент, его отправляем в буфер обмена. Для этого элемента в буфере тоже ищем его место в массиве (и вставляем на это место, а в буфер отправляем элемент, оказавшийся в этом месте). И для нового числа в буфере производим те же действия. До каких пор должен продолжаться этот процесс? Пока очередной элемент в буфере обмена не окажется тем элементом, который нужно вставить именно в ячейку X (текущее место в массиве в главном цикле алгоритма). Рано или поздно этот момент произойдёт и тогда во внешнем цикле можно перейти к следующей ячейке и повторить для неё ту же процедуру.
В других сортировках выбором мы ищем максимум/минимум, чтобы поставить их на последнее/первое место. В cycle sort так получается, что минимум на первое место в подмассиве как бы находится сам, в процессе того, как несколько других элементов ставятся на свои законные места где-то в середине массива.
И здесь алгоритмическая сложность так же остаётся в пределах O(n 2 ). На практике цикличная сортировка работает даже в несколько раз медленнее, чем обычная сортировка выбором, так как приходится больше бегать по массиву и чаще сравнивать. Это цена за минимально возможное количество перезаписей.
Блинная сортировка
Алгоритм, который освоили все уровни жизни — от бактерий до Билла Гейтса.
В самом простом варианте мы в неотстортированной части массива ищем максимальный элемент. Когда максимум найден — делаем два резких разворота. Сначала переворачиваем цепочку элементов так, чтобы максимум оказался на противоположном конце. Затем переворачиваем весь неотсортированный подмассив, в результате чего максимум попадает на своё место.
Подобные кордибалеты, вообще говоря, приводят к алгоритмической сложности в O(n 3 ). Это дрессированные инфузории кувыркаются одним махом (поэтому в их исполнении сложность O(n 2 )), а при программировании разворот части массива — это дополнительный цикл.
Блинная сортировка очень интересна с математической точки зрения (лучшие умы размышляли над оценкой минимального количества переворотов, достаточных для сортировки), есть более сложные постановки задачи (с так называемой подгоревшей одной стороной). Тема блинов крайне интересная, возможно, напишу более обстоятельную монографию по этим вопросам.
Сортировка выбором эффективна настолько, насколько эффективно организован поиск минимального/максимального элемента в неотсортированной части массива. Во всех разобранных сегодня алгоритмах поиск осуществляется в виде двойного перебора. А у двойного перебора, как ни крути, алгоритмическая сложность будет всегда не лучше чем O(n 2 ). Значит ли это, что все сортировки выбором обречены на средне-квадратичную сложность? Вовсе нет, если процесс поиска организовать принципиально по-другому. Например рассмотреть набор данных как кучу и производить поиск именно в куче. Однако тема кучи — это даже не на статью, а на целую сагу, о кучах поговорим обязательно, но в другой раз.
Ссылки
Selection / Выбор, Cycle, Pancake / Блины
Алгоритмы и структуры данных для начинающих: сортировка
В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого — сортировки пузырьком — и закончим «быстрой сортировкой» (quicksort).
Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.
Метод Swap
Пузырьковая сортировка
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива.
27–29 декабря, Онлайн, Беcплатно
Например, у нас есть массив целых чисел:
При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:
Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:
Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6.
И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.
При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.
Сортировка вставками
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.
Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса — уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом:
Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.
Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:
Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.
Далее мы переходим к числу 7. Поскольку 7 больше, чем любое значение в отсортированной части, мы переходим к следующему элементу.
На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.
Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:
Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.
Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.
Сортировка выбором
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка выбором — это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.
При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.
Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение — 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход — на этот раз по индексам от 1 до n — 1.
На втором проходе мы определяем, что наименьшее значение — 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию.
Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.
После еще двух проходов алгоритм завершает свою работу:
Сортировка слиянием
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n·log n) | O(n·log n) | O(n·log n) |
| Память | O(n) | O(n) | O(n) |
Разделяй и властвуй
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer).
Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге — один из примеров такого алгоритма.
Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много — до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную.
Насколько эффективны эти алгоритмы?
Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.
Сортировка слиянием
При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.
Давайте посмотрим на такой массив:
Разделим его пополам:
И будем делить каждую часть пополам, пока не останутся части с одним элементом:
Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.
Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.
Для работы алгоритма мы должны реализовать следующие операции:
Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием — не самое лучшее решение, когда надо отсортировать частично упорядоченный массив.
Быстрая сортировка
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n·log n) | O(n·log n) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:
Давайте посмотрим на работу алгоритма на следующем массиве:
Сначала мы случайным образом выбираем ключевой элемент:
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого — в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре).
На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.
Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное — помнить, что нам важно именно ключевое значение, а не его индекс.
Снова применяем быструю сортировку:
У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.
Заключение
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#.