Методы сортировки массивов. Метод вставки с бинарным включением Сортировка данных методом прямого включения
Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На 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]," ");
Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел (обычно называемых ключами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:
27 412 71 81 59 14 273 87.
Отсортированный список создается заново; вначале он пуст. На каждой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается, начиная с наименьшего числа, до тех пор, пока не находят соответствующее место для нового числа, т.е. пока все отсортированные числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями --- после него. Следующая последовательность списков показывает,как это делается:
Итерация 0
Отсортированный 27
Итерация 1 Неотсортированный 412 71 81 59 14 273 87
Отсортированный 27 412
Итерация 2 Неотсортированный 71 81 59 14 273 87
Отсортированный 27 71 412
Итерация 3 Неотсортированный 81 59 14 273 87
Отсортированный 27 71 81 412
Итерация 4 Неотсортированный 59 14 273 87
Отсортированный 27 59 71 81 412
Итерация 5 Неотсортированный 14 273 87
Отсортированный 14 27 59 71 81 412
Итерация 6 Неотсортированный 273 87
Отсортированный 14 27 59 71 81 273 412
Итерация 7 Неотсортированный 87
Отсортированный 14 27 59 71 81 87 273 412
В следующем алгоритме заводится только один список, и переорганизация чисел производится в старом списке.
Algorithm SIS (Сортировка Прямым включением). Отсортировать на старом месте последовательность целых чисел I(1), I(2), . . . ,I (N) в порядке возрастания.
Шаг 1. [ Основная итерация ]
For J← 2 to Ndo through шаг 4 od ;and STOP.
Шаг 2. [ Выбор следующего целого ] Set K← I(J); and L←J−1.
Шаг 3.
[ Сравнение с отсортированного целыми ] While
K AND L≥1 do set
I (L+1)←
I(L); and
L←L−1 od.
Шаг 4.
[ Включение ] Set
I(L+1)←K. QUICKSORT
:Алгоритм сортировки со средним временем работы О(N ln N)
Основная причина медленной работы алгоритма SIS заключается в том, что, все сравнения и обмены между ключами в последовательности а 1 , а 2 , . . . ,а N
происходят для пар из соседних элементов. При таком способе требуется относительно большое 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Строк 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47Действие
1 38 47 уменьшение j 5 04 38 обмен 6 08 38 увеличение i 10 38 79 обмен 14 02 38 обмен 15 76 38 увеличение i,> 16 38 76 обмен 17 38 56 уменьшение j 19 24 38 обмен 20 57 38 увеличение i,> 21 38 57 обмен,уменьшение 22 04 08 16 06 02 24 38
57 56 76 58 48 79 70 45 47 (1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16) время, чтобы поставить ключ, находящийся не на месте, в нужную позицию в сортируемой последовательности. Естественно попытаться ускорить этот процесс, сравнивая пары элементов, находящихся далеко друг от друга в последовательности. К.Хоор изобрел и весьма эффективно применил эту идею (алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка О(N 2) до порядка О(N ln N). Поясним этот алгоритм следующим примером. Предположим, что мы хотим отсортировать последовательность чисел из первой строки на рис. 15. Начнем с предположения, что первый
ключ в этой последовательности(38) служит хорошей аппроксимацией ключа, который в конечном счете появится в середине отсортированной последовательности. Используем это значение в качестве ведущего элемента, относительно которого ключи могут меняться местами, и продолжим следующим образом. Устанавливаем два указателя I и J , из которых I начинает отсчет слева (I=1) ,а J- слева в последовательности (J=N). Сравнивая а I
и а J
. Если а I ≤a J
, устанавливаем J←J−1 и проводим следующее сравнение. Продолжаем уменьшать
J до тех пор, пока не достигнем а I >а J .
Тогда поменяем местами а I ↔a J
(Рис.15 , строка 5 , обмен ключей 38 и 04), устанавливаем I←I+1 и продолжаем увеличивать
I до тех пор, пока не получим а I >а J .
После следующего обмена (строка 10, 79↔38) снова уменьшаем J. Чередуя уменьшение J и увеличение I , продолжаем этот процесс с обоих концов последовательности к «середине» до тех пор, пока не получим I=J. Теперь имеют место два факта. Во-первых,ключ(38),который сначала находился в первой позиции, к этому времени занимает надлежащее место в сортируемой последовательности. Во- первых,все ключи слева от этого элемента будут меньшими, а все ключи справа- большими. Ту же процедуру можно применить к левой и правой подпоследовательностям для окончательной сортировки всей последовательности. Последняя строка (с номером 22) рис.15 показывает, что когда будет получено I=J, то I=7. После этого процедура снова применяется к подпоследовательностям (1,6) и (8,16). Рекурсивный характер алгоритма наводит на мысль, что следует значения индексов крайних элементов большей из двух неотсортированных подпоследовательностей (8,16) поместить на стек и затем перейти к сортировке меньшей подпоследовательности (1,6). В строке 4 на рис.15 число 04 перешло в позицию 2 и сортировке подлежат подпоследовательности (1,1) и (3,6). Так как (1,1) уже отсортирована (число 02), сортируем (3,6), что в свою очередь ведет к строке 6 , в которой подлежат сортировке (3,4) и (6,6). В строке 7 подпоследовательность (1,6) отсортирована. Теперь извлекаем (8,16) из стека и начинаем сортировку этой подпоследовательности. В строке 13 находятся подпоследовательности (8,11) и (13,16), которые надо отсортировать. Помещаем (13,16) на стек, сортируем (8,11) и т.д. В строке 20 последовательность целиком отсортирована. Прежде чем описать алгоритм QUICKSORT формально, нужно точно показать,как он работает. Мы пользуемся стеком [ LEFT (K), RIGHT (K) ] для запоминания индексов крайних левого и правого элементов еще не не отсортированных подпоследовательностей. Так как короткие подпоследовательности быстрее сортируются при помощи обычного алгоритма, алгоритм QUICKSORT имеет входной параметр М, который определяет, насколько короткой должна бать подпоследовательность, чтобы ее сортировать обычным способом.Для этой цели пользуемся сортировкой простыми включениями (SIS). Поиск
Теперь обратимся к исследованию некоторых основных проблем, относящихся к поиску информации на стуктурах данных. Как и в предыдущем разделе, посвященному сортировки, будем предполагать, что вся информация хранится в записях, которые можно идентифицировать значениями ключей, т.е. записи R i соответствует значение ключа,обозначаемое K i . Предположим,что в файле расположены случайным образом N записей в виде линейного массива. Очевидным методом поиска заданной записи будет последовательный просмотр ключей. Если найден нужный ключ, поиск оканчивается успешно; в противном случае будут просмотрены все ключи, а поиск окажется безуспешным.Если все возможные порядки расположения ключей равновероятны, то такой алгоритм требует O(N) основных операций как в худшем, так и в среднем случаях. Время поиска можно заметно уменьшить, если предварительно упорядочить файл по ключам. Эта предварительная работа имеет смысл, если файл достаточно велик и к нему обращаются часто. Предположим, что мы обратились к середине файла и обнаружили там ключ K i . Сравним К и К i . Если К=К i , то нужная запись найдена. Если К<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части. Блок-схема этой процедуры, известной под названием двоичный поиск
, приведена на рис.16 Algorithm
BSEARCH (Binary search- двоичный поиск) поиска записи с ключом К в файле с N≥2 записями, ключи которых упорядочены по возрастанию К 1 <К 2 …<К N . Шаг 0.
[Инициализация] Set
FIRST←1 ; LAST← N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.) Шаг 1.
[Основной цикл ] While
LAST≥FIRST do through
шаг 4 od.
Шаг 2.
[Получение центрального ключа] Set
I←|_(FIRST + LAST)/2_| .(К i - ключ, расположенный в середине или слева от середины еще не просмотренной части файла.) Шаг 3.
[Проверка на успешное завершение ] If
К=К I then
PRINT «Успешное окончание, ключ равен К I »;and
STOP fi.
Шаг 4.
[ Сравнение] If
K<
K I then set
LAST←I-1 else set
FIRST←I+1 fi.
Шаг 5.
[ Безуспешный поиск] PRINT «безуспешно»; and
STOP. Алгоритм BSEARCH используется для отыскания К=42 на рис.17. Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева. Значение ключа, найденное при первом выполнении шага 2 (К(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (9,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (К(4)=33) становится следующим после корня элементом влево, если его значение меньше значения корня, и следующим вправо в противном случае. Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3) , (5,7)] помещаются теперь на стек.Эта процедура повторяется до тех пор, пока стек не окажется пустым. На рис.18 показано двоичное дерево, которое было бы построено для 16 упорядоченных ключей с рис.17. Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу К равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания К. Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка этим методом производится последовательно шаг за шагом. На 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)
Номер шага Зона вывода Необходимые определения и классификация сортировок.
Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность
Сортировка
– это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю
(сортировка в оперативной памяти) и внешнюю сортировки
(сортировка во внешней памяти). Регулярность
расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве. Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов
. Этот метод применяют в таблице адресов ключей
. Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки
. Эффективность сортировки можно рассматривать с нескольких критериев: 1)
время, затрачиваемое на сортировку; 2)
объем оперативной памяти, требуемой для сортировки; 3)
время, затраченное программистом на написание программы. Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов. Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn)
до о(n 2)
, где о(n)
- идеальный и недостижимый случай. Методы сортировки можно классифицировать примерно так: 1) строгие (прямые) методы
(их эффективность примерно одинакова): · прямого включения
; · прямого выбора
; · прямого обмена
; 2) улучшенные методы
. В жизни принцип данной сортировки присутствует при раскладывании пасьянсов, уборки квартиры, когда необходимо расположить кучу смешанных вещей в должном порядке и т.д. Очень естественный способ сортировки был применён и к упорядочиванию данных. Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1
и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i-
й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности. Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию. Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом. Таблица 11.1 Принцип работы сортировки прямым включением Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов. Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).
Да
Метод двухпутевой вставки
