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

 

          1.4. Сортировка перемешиванием

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

 Анализируя метод  пузырьковой сортировки можно  отметить два обстоятельства.

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

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

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

 

1.5. Сортировка методом вставок

Простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

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

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

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.2. Демонстрация сортировки по неубыванию методом простого включения.

 

В отличие от пузырьковой  сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1; в противном случае его производительность является величиной порядка n^2 [1, С 243 - 244].

 

1.6. Блочная сортировка

Блочная сортировка (Карманная сортировка, корзинная сортировка) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо иным другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

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

Алгоритм. Если входные  элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).

Идея алгоритма заключается  в том, чтобы разбить интервал [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных  величин. Поскольку входные числа  равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путем последовательного перечисления элементов каждого кармана.

 

 

 

 

 

 

 

 

                     Рис.3. Элементы распределяются по корзинам

 

 

 

 

 

 

 

 

 

                  Рис.4. Затем элементы в каждой  корзине сортируются

 

 

 

 

         1.7. Сортировка подсчетом 

 

Один из самых простых (но и самых медленных) способов сортировки – это сортировка подсчетом. Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Для каждого элемента нужно найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место.

 

      1.8. Сортировка слиянием

 

Сортировка  слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например - тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.

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

 

         1.9. Двоичное дерево

 

Сортировка  с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) - универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).

Алгоритм

1. Построение двоичного  дерева.

2. Сборка результирующего  массива путём обхода узлов  в необходимом порядке следования  ключей [7, С 4].

 

 

 

 

 

 

 

 

 

 

 

 

 

            Рис.5. Пример двоичного дерева

 

 

 

 

 

         1.10. Цифровая сортировка

 

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

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

 

         1.11. Гномья сортировка

 

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.

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

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

 

1.12. Сортировка методом выбора

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

Этот метод работает очень хорошо для небольших файлов. Кроме того, хотя сортировка выбором  является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.

 

1.13 Сортировка методом Шелла

Основная идея этого  алгоритма заключается в устранении  массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

 

1.14. Сортировка расчёской

Сортировка  расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).

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

 

 1.15. Пирамидальная сортировка

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

Сортировка пирамидой  использует сортирующее дерево. Сортирующее  дерево – это такое двоичное дерево, у которого выполнены условия:

-  каждый лист имеет  определенную глубину;

         -  значение в любой вершине больше, чем значения ее потомков.

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

 

 

 

 

1.16. Быстрая сортировка  

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

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