Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования.pdf

Рис. 2.1. Выполнение первого прохода с помощью шейкер-сортировки

Рис. 2.2. Выполнение второго прохода с помощью шейкер-сортировки

Теперь, вместо прохода колоды карт справа налево, пройдите слева направо: сравните вторую и третью карты и старшую карту поместите на третью позицию. Сравните третью и четвёртую карты, и при необходимости поменяйте их местами. Продолжайте сравнения вплоть до достижения пары (12, 13). По пути к правому краю колоды вы «захватили» короля и переместили его на последнюю позицию, как показано на рисунке 2.2.

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

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

Как и пузырьковая сортировка, шейкер-сортировка относится к неустойчивым алгоритмам.

1.3 Сортировка методом выбора (метод простого выбора)

Сортировка методом выбора (selection sort).

Рис. 3. Сортировка методом выбора

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

Сортировка методом выбора относится к алгоритмам класса О(n²). Количество выполняемых сравнений для первого прохода равно n, для второго n-1 и т.д. общее количество сравнений будет равно n(n+1)/2-1, т.е. сортировка принадлежит к классу О(n²). Тем не менее, количество перестановок намного меньше: при каждом выполнении внешнего цикла производится всего одна перестановка. Таким образом, общее количество перестановок (n-1), т.е. О(n). Что это означает на практике? Если время и требуемые ресурсы перестановки элементов массива намного больше, чем время сравнения, то сортировка методом выбора оказывается достаточно эффективной.

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

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

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

Сортировка методом вставок или сортировка простыми вставками (insertion sort). Рассмотрим принцип действия данного алгоритма на той же колоде карт.

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

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

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

Идея метода: делается предположение, что первый n элемент массива уже упорядочен и рассматривается n+1 элемент. Если окажется, что он меньше чем какой либо из первых n, то он занимает место большего, а участок массива ограниченный его новым местом и старым смещается вправо.

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

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

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

1.5 Сортировка двоичным (бинарным) деревом

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

Описание метода сортировки двоичным деревом детально рассмотрено в книге Н. Вирта: «Алгоритмы и структуры данных».^[3]

Вместо «предшественник» и «преемник» также употребляют термины «родитель» и «сын». Все элементы дерева также называют «узлами». При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом, вставляя на место. Если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить.

Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:

44 44 44 44 44

\ / \ / \ / \

55 12 55 12 55 12 55

\ \ \

42 42 94

(**) 44 44 (*) 44

/ \ / \ / \

12 55 12 55 12 55

\ \ / \ \ / \ \

42 94 06 42 94 06 42 94

/ / / /

18 18 18 67

Дерево может быть и более-менее ровным, как на (*), может и иметь всего две основные ветви (**), а если входная последовательность уже отсортирована, то дерево выродится в линейный список.

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

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

Общее быстродействие метода O(n×logn). Поведение неестественно, устойчивости, вообще говоря, нет.

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

Поэтому данная сортировка обычно применяют там, где:

- построенное дерево можно с успехом применить для других задач;

- данные уже построены в 'дерево';

- данные можно считывать непосредственно в дерево.