Сортировка простыми включениями
Make it run,
Make it right,
Make it small,
Make it fast
Сделайте чтобы работало,
Сделайте чтобы работало правильно,
Сделайте чтобы было маленьким,
Сделайте чтобы работало быстро.
Лекция 1. Сортировки
Сортировки и поиск
В разделе описываются основные алгоритмы сортировки статических массивов.
Сортировкой обычно называют процесс перестановки элементов данного множества в определенном порядке. Цель сортировки – облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки и поиска присутствуют почти во всех задачах обработки информации.
Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы уже упорядочены по одному ключу, а сортировка ведется по другому ключу.
Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов необходимо выполнять in situ (на том же месте). Поэтому при выборе метода сортировки необходимо установить критерий эффективности, то есть определить ее быстродействие. При сортировке элементов в массиве выполняются два действия: сравнения элементов по некоторому ключу и пересылка элементов. И число сравнений ( C ), и число перестановок ( M ) зависят от размерности массива N.
Хорошие алгоритмы сортировки требуют порядка N*logN сравнений, более простые – порядка N2 сравнений ключей. Хотя в более сложных алгоритмах меньше операций, сами эти операции более сложны; поэтому при достаточно малых N простые методы работают быстрее, но их не следует использовать при больших N.
|
|
|
Существует много алгоритмов сортировки, выполняющих одну и ту же задачу. Причем одни из них имеют преимущество в некотором смысле перед другими. Поэтому при выборе того или иного алгоритма для конкретной задачи необходимо учитывать некоторые условия, например, такие:
q Исходная упорядоченность входного множества: во входном множестве могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе. Говорят, что сортировка демонстрирует естественное поведение, если C и M имеют наименьшие значения из возможных в случае упорядоченного массива и возрастают с ростом неупорядоченности, и неестественное поведение в противном случае.
q Временные характеристики операций: при определении алгоритма время выполнения считается обычно пропорциональным числу сравнений ключей. Ясно, однако, что сравнение числовых ключей выполняется быстрее, чем строковых; операции пересылки выполняются тем быстрее, чем меньше объем записи, и т.п. В зависимости от характеристик записи таблицы может быть выбран алгоритм, обеспечивающий минимизацию числа тех или иных операций.
|
|
|
Методы сортировки массива можно разбить на три основных класса в зависимости от лежащего в их основе приема:
- Сортировка выбором
- Сортировка включениями
- Сортировка обменом
Во всех программных примерах используются данные, определенные так:
q const N=… – целое положительное число, число элементов в массиве;
q type TData = array[1..N] of integer – сортируемые последовательности.
Результатом сортировки является массив, элементы которого упорядочены по возрастанию ключа. Для простоты ключом элемента считается значение самого элемента.
Сортировка простым выбором
Это простой и наиболее очевидный способ сортировки. Его алгоритм состоит их двух шагов:
q Выбирается элемент с наименьшим ключом
q Меняется местами с первым элементом массива
После этого массив можно рассматривать как состоящий из двух частей: левой – уже отсортированной – «готовой», и правой, с которой будут повторяться те же шаги – «входной».
|
|
|
Понятно, что для сортировки всего массива нужно сделать N – 1 пар шагов: на N – 1 паре шагов два крайних правых элемента займут свои места, и массив станет упорядоченным.
Сортировка простым выбором показана в листинге 7.1. Процедура имеет только один параметр – сортируемый массив.
Листинг 7.1. Сортировка простым выбором. Вариант 1
procedure SortSelection(var a: TData);
Var
i,j,imin : integer;
min :integer;
Begin
for I:=1 to N – 1 do begin
min:=a[I]; imin:=i;
for j:=i+1 to N do // в этом цикле ищем минимальный элемент
if a[j]<min then
Begin
min:=a[j]; imin:=j
end;
if i<>imin then
Begin
a[imin]:=a[i]; // обмен местами мин. элемента с первым
a[i]:=min // из оставшейся – не отсортированной –
Части массива
End;
end;
End;
Обмен местами двух элементов стандартно выполняется в три действия с использованием третьего – вспомогательного – элемента. Однако в этом примере роль вспомогательного элемента играет переменная min. Эта же переменная, участвуя в сравнении элементов, неявно уменьшает время работы программы, так как доступ к простой переменной осуществляется быстрее, чем к элементу массива.
|
|
|
Для сравнения приводится этот же алгоритм, реализующий вышеприведенные отличия:
Листинг 7.2. Сортировка простым выбором. Вариант 2
procedure SortSelection1(var a: TData);
Var
i,j,imin : integer;
tmp : integer;
Begin
for i:=1 to N - 1 do begin
imin:=i;
for j := i + 1 to N do // в этом цикле ищем минимальный элемент
if a[j]<a[imin] then imin:=j;
if i <> imin then begin
tmp := a [ imin ]; // обмен местами мин. элемента с первым
a [ imin ]:= a [ i ]; // из оставшейся – не отсортированной
a [ i ]:= tmp //– части массива
End;
end;
end;
Довольно простая модификация обменной сортировки выборкой предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума и обмен их с первым и с последним элементами множества соответственно.
Сортировка выборкой практически нечувствительна к исходной упорядоченности. В любом случае поиск минимума требует полного просмотра входного множества.
Число C сравнений ключей не зависит от исходной упорядоченности. C=1/2(N2-N). Число M перестановок минимально в случае изначальной упорядоченности: M~N и принимает наибольшее значение, если ключи изначально расположены в обратном порядке: M~trunc(N2/4)+3(N-1).
Сортировка включениями
Сортировка простыми включениями
Элементы массива условно разделяются на «готовую» последовательность a[1]…a[i] и «входную»: a[i+1]…a[N]. На каждом шаге, начиная с i=2, берут i-тый элемент массива – 1‑ый элемент «входной» последовательности и «вставляют» в нужное место «готовой» последовательности. Поскольку «вставить» между элементами массива новый элемент невозможно, приходится сдвигать j-тый элемент вправо, если вставляемый элемент меньше j-того, пока не найдется нужное место. Эта деятельность может закончиться при двух различных условиях:
q Найден элемент a[j], меньший, чем вставляемый элемент.
q Достигнут левый край массива.
Чтобы не использовать неэффективный цикл с двумя условиями, применим метод барьера, установив его в нулевой элемент массива. Для этого придется расширить диапазон индексов в описании массива до 0..N. Программа приведена в листинге 8.3.
Листинг 7.3. Сортировка простыми включениями
Type
TData = array[0..N] of integer;
procedure SortInsertion(var a: TData); // Внимание! Массив должен
// начинаться с нуля!
Var
I,j : integer;
tmp : integer;
Begin
for i:=2 to N do begin
tmp:=a[i]; j:=i-1;
a[0]:=tmp; // установка барьера
while tmp<a[j] do begin
a[j+1]:=a[j]; // сдвинуть элемент
j:=j-1
end;
a[j+1]:=tmp // поставить элемент на свое место
end;
End; // SortInsertion
В сортировке простыми вставками число сравнений ключей при помещении i-того элемента на свое место составляет в среднем Ci ~i/2. Число пересылок Mi=Ci +2. Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший случай встречается, если элементы расположены в обратном порядке.
Дата добавления: 2021-01-21; просмотров: 155; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!