Для сортировки (упорядочения) по возрастанию или убыванию значений в массиве разработано множество методов [Вирт, Кнут. т 3].Рассмотрим три из них, считая, для определённости, что первые n, n=6, элементов массива Х
На каждом следующем i-том шаге, i=2, 3,…,n-1, значение из (i+1)-ой ячейки массива путем обмена положением с числом из предыдущей ячейки продвигают в сторону уменьшения индекса ячейки до тех пор, пока ни окажется, что в предыдущей ячейке находится меньшее число.
Из сказанного следует, что при реализации метода прямого включения внешний цикл должен выполняться n-1 раз, а максимально возможное число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет увеличиваться от 1 до n-1. Однако внутренний цикл следует организовать так, чтобы он заканчивался или вообще не выполнялся при наступлении условия: значение в предыдущей ячейке массива меньше, чем в текущей.
В нашем примере:
При i=2 число 15 из ячейки Х 3 последовательно обменяется местами с числом 34 из ячейки Х 2 , а затем с числом 21 из ячейки Х 1 ,
При i=4 число 25 из ячейки Х 5 обменяется местами с числом 34 из ячейки Х 3 ,
Ниже представлен фрагмент программы упорядочения по возрастанию первых n элементов массива X методом прямоговключения (включения с сохранением упорядоченности) .
while (X
R:=X[j];
X[j]:=X;
X:=R;
for i:=1 to n-1 do
Для упорядочения чисел в массиве по убыванию достаточно на каждом шаге изменить условие перестановки чисел в соседних ячейках массива на обратное, а именно, обмен значениями соседних ячеек выполнят в случае, когда предыдущее меньше текущего.
Метод прямого обмена (метод пузырька).
Этот метод, как и предыдущий, основан на обмене значениями соседних ячеек массива, но с первого же шага в последовательном анализе, при движении от одного конца массива к другому, участвуют все пары соседних ячеек массива.
На первом шаге последовательно, для j = n, n-1, …,2, сравниваются значения соседних ячеек массива, и при выполнении условия Х j <Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .
В нашем примере после выполнения первого шага данные в массиве расположатся так:
На каждом следующем шаге число проверяемых пар ячеек будет уменьшаться на 1. В общем случае, на любом шаге i, i=1, 2, 3, …, n-1, процесс будет выполняться для j от n до i+1, в частности, при i= n-1 – только один раз для n-ой и (n-1)-вой ячеек.
Из сказанного следует, что при реализации метода прямого обмена внешний цикл должен выполняться n-1раз, а число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет уменьшаться от n-1 до 1.
Происхождение термина “метод пузырька” объясняется так: если представить вертикальное расположение ячеек массива с ростом индекса сверху вниз, то самое маленькое число из рассматриваемых будет подниматься вверх подобно пузырьку в воде.
В нашем примере
При i=3 перестановки приведут к следующему состоянию массива
При использовании метода пузырька не имеет значения, в сторону увеличения или в сторону уменьшения индексов продвигается анализ пар чисел в массиве, а вид упорядочения (по возрастанию или убыванию) определяется только условием перестановки чисел (меньшее должно расположиться за большим или наоборот).
Модифицированный метод прямого обмена (модифицированный метод пузырька).
Как видно из приведенного выше числового примера массив оказался упорядоченным уже после четвёртого шага, то есть возможновыполнение внешнего цикла не n-1 раз, а меньше, когда станет известно, что массив уже упорядочен. Такая проверка основывается на следующем: если при выполнении внутреннего цикла не было ни одной перестановки, значит массив уже упорядочен и можно выйти из внешнего цикла. В качестве признака, выполнялась ли перестановка, используют переменную булевского типа: до входа во внутренний цикл ей дают одно значение, например, False, а при выполнении перестановки – другое, например, True.
Очевидно, эффект при использовании модифицированного метода пузырька по сравнению с не модифицированным методом в ускорении процесса сортировки будет наблюдаться, если исходная последовательность чисел близка к упорядоченности в нужном направлении. В предельном случае, когда массив уже упорядочен нужным образом тело внешнего цикла будет выполнено только один раз.
Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть
а ≤ а ≤ ... ≤ a .
Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j (1 ≤ j ≤ k -1), что а [j] ≤ a[k] < a. Затем вставить элемент а [k] на найденное место.
С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.
Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения
1 - й шаг
13 6 8 11 3 1 5 9 15 7 Рассматриваем часть массива из одного эле-
мента (13). Нужно вставить в нее второй
элемент массива (6) так, чтобы упорядочен-
ность сохранилась. Так как 6 < 13, вставляем
6 на первое место. Отсортированная часть
массива содержит два элемента (6 13).
3 - й шаг
6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8 , но 11 < 13.
5 - шаг
3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое
6 - шаг
1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря-
Доченной части - третье.
7 - шаг
1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое.
8 - шаг
1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего
Элемента 15. Оказывается, что этот эле-
мент массива уже находится на своем месте.
9 - шаг
1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для
Последнего элемента (7).
1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:
For k: = 2 To n Do
{ так как начинам сортировку с поиска подходящего места для a, i изменяется от 2 до n }
‘вставить x на подходящее место в a , ..., a[k] ‘
Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы a[ j ] , j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий:
· найден элемент a[j] < x, что говорит о необходимости вставки x между a и a[j].
· достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.
До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на первую позицию вправо, в результате чего в отсортированной части будет освобождено место под x.
Программа сортировки методом прямого включения:
program n3; { Сортировка по убыванию }
type ar=array of integer;
procedure sorting3(var a:ar);
var i,j,x,k:integer;
for k:=2 to n do
x:=a[k]; j:=k-1;
while (j>0)and(x>=a[j]) do
writeln("Введите исходный массив:");
for i:=1 to n do read(a[i]);
writeln("Отсортированный массив:");
for i:=1 to n do write(a[i]," ");
Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка этим методом производится последовательно шаг за шагом. На k –м шаге считается, что часть массива, содержащая первые k– 1 элемент, уже упорядочена, то есть .
Далее необходимо взять k –й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое что . Затем надо вставить элемент a(k) на найденное место.
С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n– 1 шаг.
Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х . Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а(j) , j изменяется от k– l до 1. Такой просмотр закончится при выполнении одного из следующих условий:
Найден элемент , что говорит о необходимости вставки х между и а(j) .
Достигнут левый конец упорядоченной части массива, следовательно, нужно вставить х на первое место.
До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на 1 позицию вправо, в результате чего в отсортированной части будет освобождено место под х .
Методику сортировки иллюстрирует таблица 2:
Таблица 2 – Пример сортировки с помощью прямого включения
Первоначально упорядоченная последовательность состоит из 1–го элемента 9. Элемент а(2) =5 – первый из неупорядоченной последовательности и 5 < 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент а(3) =15 неупорядоченной последовательности больше всех элементов упорядоченной последовательности, поэтому остаётся на своём месте и на следующем шаге упорядоченная последовательность состоит из 5, 9, 15, а рассматриваемый элемент 6. Процесс происходит до тех пор, пока последовательность не станет упорядоченной.
Шейкерная сортировка
Метод пузырька допускает три простых усовершенствования. Во–первых, если на некотором шаге не было произведено ни одного обмена, то выполнение алгоритма можно прекращать. Во–вторых, можно запоминать наименьшее значение индекса массива, для которого на текущем шаге выполнялись перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом уже отсортирована, и на следующем шаге можно прекращать сравнения значений соседних элементов при достижении такого значения индекса. В–третьих, метод пузырька работает неравноправно для "легких" и "тяжелых" значений. Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шаге опускается по направлению к нужному месту на одну позицию.
На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге "всплывает" очередной наиболее легкий элемент, а на другом "тонет" очередной самый тяжелый. Пример шейкерной сортировки приведен в таблице 3.
Таблица 3 – Пример шейкерной сортировки
Сортировка массива с помощью включений с уменьшающимися расстояниями (метод Шелла)
Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения.
Идея метода: все элементы массива разбиваются на группы таким образом, что в каждую группу входят элементы, отстоящие друг от друга на некоторое число позиций L . Элементы каждой группы сортируются. После этого все элементы вновь объединяются и сортируются в группах, при этом расстояние между элементами уменьшается. Процесс заканчивается после того, как будет проведено упорядочивание элементов с расстоянием между ними, равным 1.
Пример сортировки методом Шелла приведен в таблице 4.
Таблица 4 – Пример сортировки методом Шелла
Сначала рассмотрим вариант, когда первоначальное значение L равно половине числа элементов в массиве, а каждое последующее значение вдвое меньше предыдущего. Заметим, что обмениваются элементы, которые отстоят на величину шага. Если при сравнении 2–х элементов обмена не произошло, то места сравниваемых элементов сдвигаются вправо на одну позицию. Если обмен произошёл, то происходит сдвиг соответствующих сравниваемых элементов на L .
Сортировка разделением (быстрая сортировка)
Метод сортировки разделением был предложен Чарльзом Хоаром. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть методом быстрой сортировки – «Quicksort».
Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x , после чего массив просматривается слева, пока не встретится элемент a(i) такой, что a(i) > x , а затем массив просматривается справа, пока не встретится элемент a(i) такой, что a(i) < x . Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x . В результате массив окажется разбитым на две части – левую, в которой значения ключей будут меньше x , и правую со значениями ключей, большими x . Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива.
Процесс сортировки массива быстрым методом представлен в таблице 5.
Таблица 5 – Пример быстрой сортировки
Метод вставки с прямым включением можно улучшить, если отыскивать место для вставляемой записи в упорядоченной подтаблице с помощью метода бинарного (дихотомического, двоичного, логарифмического) поиска. Эта модификация метода вставки названа вставкой с бинарным включением.
Рассмотрим j ‑й шаг сортировки (j =2, 3, ..., n ). Если K [ j ]>= K [ j -1] , то упорядоченность не нарушилась и следует перейти к R [ j +1]– ой записи. Если же K [ j ]< K [ j -1] , то R [ j ] запоминается в рабочей переменной (Rab = R [ j ]) и для нее ищется место в упорядоченной части таблицы – в подтаблице. Обозначим нижнюю границу индекса этой подтаблицы через ng , верхнюю - через vg (первоначально ng =1. vg =j-1 ).
Согласно бинарному поиску ключ K [ j ] рассматриваемой записи R [ j ] должен сначала сравниться с ключом K [ i ] записи R [ i ] , находящейся в середине упорядоченной подтаблицы (i=(ng+vg) div 2) . Если K [ j ]> K [ i ], то отбрасывается (то есть больше не рассматривается) левая часть подтаблицы- записи с меньшими ключами (ng = i +1) . Если K [ j ]< K [ i ] , то отбрасывается правая часть подтаблицы - записи с большими ключами (vg = i -1). В оставшейся части подтаблицы поиск продолжается. Процесс деления частей подтаблицы пополам продолжается до тех пор, пока не возникнет одна из следующих ситуаций:
1) K [ j ]= K [ i ] , следовательно, (i+1) -я позиция является местом для рассматриваемой записи. Сдвинем записи R [ i +1], R [ i +2], …, R [ j -1] на одну позицию вправо и освободим тем самым место для вставки (R [ i +1]= Rab ).
2) K [ j ]<> K [ i ] и ng > vg – ключи не совпали, а длина последней подтаблицы равна 1. В этом случае местом для вставки является позиция ng , поэтому записи R [ ng ], R [ ng +1], … , R [ j -1] должны быть сдвинуты на одну позицию вправо (R [ ng ]= Rab ) .
Алгоритм бинарного поиска подробно описан в разделе "Дихотомический поиск по совпадению".
Рассмотрим на примере j -й шаг сортировки (определяется место записи с ключом, равным 9; j =7, K [ j ]=9 ):
Среднее число сравнений для данного метода составляет n log 2 (n) .
Метод двухпутевой вставки
Метод двухпутевой вставки является модификацией метода вставки с прямым включением; он позволяет улучшить характеристики сортировки.
Для реализации этого метода необходим дополнительный объем памяти, равный объему, занимаемому таблицей, подлежащей сортировке (назовем его зоной вывода T ). На первом шаге сортировки в середину зоны вывода (позиция m=(n div 2)+1 ) помещается первая запись таблицы R. Остальные позиции Т пока пусты. На последующих шагах сортировки ключ очередной записи R [ j ] (j =2, 3, …, n ) сравнивается с ключом записи T [ m ] и, в зависимости от результатов сравнения, место для R [ j ] отыскивается в Т слева или справа от T [ m ] методом вставки. При этом должны запоминаться номера самого левого (l ) и самого правого (r ) внесенных в зону вывода элементов. Конечные значения l и r равны 1 и n соответственно.
В алгоритме должны быть учтены также следующие ситуации:
ключ записи R[j] меньше ключа записи T[m] , но l=1 ;
ключ записи R[j] больше ключа записи T[m] , но r=n .
В этих случаях для вставки записи R [ j ] необходимо осуществлять сдвиг записей подтаблицы вместе с записью T [ m ] вправо или влево (используется метод вставки с прямым включением).
Рассмотрим пример сортировки с использованием этого метода.
Пусть исходная последовательность ключей таблицы имеет вид:
24, 1, 28, 7, 25, 3, 6, 18, 8 (n =9, m =(n div 2)+ 1=5)
|
Номер шага |
Зона вывода |
|||||||||
