Лабораторная работа №4

Тема: Алгоритмы сортировки и поиска

Постановка задачи.

Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Варианты заданий приведены в табл. 3.

Таблица 3

Варианты заданий

Методические указания

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

Обменная сортировка.

Последовательно сравнивается элемент а₀ с каждым последующим a_i и, если a_i< а₀, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а₁ и т. д.

Шейкер – сортировка.

В этом методе проходы массива выполняются поочередно: слева направо, а потом справа налево. Последовательно сравниваются пары соседних элементов (а₀ и а₁, а₁ и а₂, и т.д.) и, если надо, переставляются. Запоминается индекс последнего переставляемого элемента (right). Далее массив просматривается справа налево, начиная с индекса right. В этом проходе массива также выполняются сравнения соседних элементов и их перестановка. Запоминается индекс последнего переставляемого элемента (left). Далее опять выполняется проход слева направо от индекса left до индекса right и т.д.

Сортировка Шелла.

Выбирается интервал d между сравниваемыми элементами, и выполняется сортировка массива методом «пузырька», но с шагом d. После этапа сортировки массива с выбранным интервалом, этот интервал уменьшается и опять выполняется сортировка массива методом «пузырька». Рекомендуется следующая последовательность значений d: 1, 3, 7, 15, 31, … ,т.е.

d_k=(d_k-1-1)/2

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

Челночная сортировка.

Последовательно сравниваются пары соседних элементов а₀ и а_1, а₁ и а₂, и т.д. и если а_i>a_i+1, то элемент a_i+1 продвигается влево насколько это возможно: он сравнивается со своим предшественником и, если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда передвигаемый влево элемент встречает меньшего предшественника, то процесс передвижения влево прекращается и возобновляется просмотр массива слева направо с той позиции, с которой выполнялся обмен при продвижении слева направо.

Быстрая сортировка (метод Хоара).

Идея метода заключается в том, что вначале переставляются элементы, которые находятся друг от друга на больших расстояниях. Выбирается элемент массива (например, центральный), который разбивает массив на два подмножества. Пусть значение этого элемента х. Элементы массива переставляются таким образом, чтобы слева от x находились элементы а_i<=x, а справа a_j>=x. После перестановок элемент x будет находиться на своем месте. Далее этот алгоритм разделения массива на левую и правую части применяется к левой, а затем к правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из единственного элемента. Таким образом, в этой сортировке используется рекурсия. Алгоритм разделения элементов массива начиная с элемента с индексом left до элемента с индексом right относительно «центрального» элемента x: вводятся два индекса i и j , i=left ; j = right. Элементы просматриваются слева направо до тех пор, пока не обнаружится элемент a_i>=x, затем массив просматривается справа налево, пока не обнаружится элемент a_j<=x . После этого элементы меняются местами. Далее процесс просмотра и перестановки повторяется до тех пор, пока не станет i>j.

Комбинированный метод быстрой сортировки с методом «пузырька».

В этом методе рекурсивный алгоритм разделения массива быстрой сортировки применяется только для подпоследовательностей массива, длина которых не менее определенного размера m (m<=n). Для сортировки коротких подпоследовательностей используется метод «пузырька».

Линейная вставка

Элементы массива делятся на уже упорядоченную последовательность а₀, а₁, …, а_i-1 и неупорядоченную а_i, a_i+1, …,a_n-1. В каждом проходе из неупорядоченной последовательности извлекается элемент а_i (в первом проходе i=1) и вставляется в упорядоченную последовательность из i элементов без нарушения упорядоченности в ней. Этот алгоритм повторяется для i=2,3,…,n-1. Алгоритм вставки а_i в упорядоченную последовательность из i элементов заключается в продвижении вставляемого элемента в начало последовательности, сравнивая его с а_i-1, a_i-2  и т.д. Продвижение заканчивается на элементе а_j<=a_i или при прохождении всей последовательности.

Бинарная вставка.

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