Файл: Методы сортировки данных.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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