Алгоритмы сортировки

ВВЕДЕНИЕ 

     Еще в раннем детстве в нас просыпается  стремление к разрушению и хаосу - один их базовых инстинктов человека. Но по мере взросления в нас крепнет противоположное начало - тяга к упорядочиванию и систематизации. Появление компьютеров дало возможность работать с куда большими объемами информации. Проблема упорядочивания стала более остро, на нее были кинуты силы лучших умов человечества.

     Часто нужно упорядочить предметы по какому-то признаку: записать данные числа в  порядке возрастания, слова —  по алфавиту, людей выстроить по росту. Если можно сравнить любые два предмета из данного набора, то этот набор всегда можно упорядочить. Процесс упорядочивания информации и называют «сортировкой»

     Пусть нам требуется упорядочить набор  {3,6,1,2,9,5} по возрастанию. Это лёгкая задача, ответ будет таким: {1,2,3,5,6,9}.

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

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

     «Алгоритм сортировки» — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Изучение алгоритмов совсем не лёгкая задача, здесь требуется внимательное рассмотрение каждой строчки.

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

     Существует огромное количество методов, которыми нам предлагают сортировать данные. Зачем же так много? И правда - может, достаточно одного эффективного способа, и не надо морочить себе голову таким обилием? Ответ на этот вопрос состоит в том, что очень трудно иногда бывает сопоставить эффективность двух разных методов. Проще говоря: одни более удобны в одних случаях, другие - в других.

     Все из существующих ныне способов сортировки отличаются друг от друга по скорости выполнения, понятности и длине кода, по красоте решения. Зачастую в код  уже разработанного алгоритма вносятся какие либо изменения и так возникает множество решений. Проблемам сортировок Дональд Кнут посвятил целый том своего «Искусства программирования».

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

1. Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования  памяти:

   Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;

   Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

2. Классификация алгоритмов сортировки

   Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

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

   Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n*log(n)), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его  сфера применения. Здесь основных типов упорядочения два:

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

   В современных  архитектурах персональных компьютеров  широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

   Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью:

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

   - объём данных не позволяет им разместиться в ОЗУ.

3. Список алгоритмов сортировки

              В этом списке n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.

                               3.1 Алгоритмы устойчивой сортировки

• Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку.
• Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n²)
• Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находится в упорядоченном списке и вставляем его туда
• Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти
• Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти
• Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки
• In-place merge sort — Сложность алгоритма: O(n²), O(n log² n) или O(n log n) в зависимости от применяемого алгоритма слияния.
• Двоичное дерево сортировки (Binary tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
• Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
• Гномья сортировка (Gnome sort) — Сложность алгоритма: O(n²)

                             3.2 Алгоритмы неустойчивой сортировки

• Сортировка выбором (Selection sort) — Сложность алгоритма: O(n²); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
• Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками
• Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
• Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
• Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
• Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
• Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
• Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
• Обменная поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти

                           3.3 Непрактичные алгоритмы сортировки

• Сортировка Акульшина (Akulshin sort) — O(n × n!) — худшее время. Генерируются всевозможные перестановки исходного массива и для каждой осуществляется проверка верного порядка.
• Глупая сортировка (Stupid sort) — O(n³); рекурсивная версия требует дополнительно O(n²) памяти
• Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение
• Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение

                       3.4 Алгоритмы, не основанные на сравнениях

• Блочная сортировка (Корзинная сортировка, Bucket sort)
• Лексикографичкская или поразрядная сортировка (Radix sort)
• Сортировка подсчётом (Counting sort)

                        3.5 Остальные алгоритмы сортировки

• Топологическая сортировка
• Внешняя сортировка

 
 
 
 
 
 

4. Описание некоторых алгоритмов

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

4.1 Сортировка пузырьком

  Чаще всего  используется для сортировки частично упорядоченных списков, так как именно для них скорость выполнения максимальна и может равняться O(N), где N количество элементов массива, а O время одного прохода через цикл.

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

    Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

4.2 Сортировка выбором

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