 |
|
Сортировки включением
Сортировка прямым включением.Элементы условно разделяют на готовую a[1],...,a[i-1] и входную последовательности a[i],...,a[n]. Сначала i=2. На каждом шаге, увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя на подходящее место.
Итак, в начале рассматривается второй элемент (i=2) последовательности ключей. Он сравнивается с первым элементом (a[i-1]) и если он его меньше, то они меняются местами. В противном случае проход заканчивается, i увеличивается на 1 и процесс повторяется. Заметим, что упорядоченная последовательность a[i-1] называется готовой последовательностью и новый элемент вставляется в готовую последовательность на свое место.
На каждом проходе происходит перемещение i-того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.
Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов(а).
Procedure Straight_Insertion(n:integer; Var a:t);
Var
i,j:word;
x:integer;
Begin
For i:=2 To n Do
begin
x:=a[i]; a[0]:=x; j:=i-1;
While x<a[j] Do
begin
a[j+1]:=a[j]; j:=j-1;
end;
a[j+1]:=x
end;
End;{Straight_Insertion}
Процедура упорядочивает элементы массива начиная с первого. Нулевой элемент используется процедурой как вспомогательный.
В основной программе массив необходимо объявить следующим образом:
TYPE
t=array[0..20] of integer;
VAR
A:t;
N,i:word;
Ввод массива:
FOR i:=1 to n do
Read(a[i]);
Вывод отсортированного массива:
FOR i:=1 to n do
Wrire(a[i],’ ‘);
Сортировка бинарными включениями.Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.
Procedure Binary_Insertion(n:word;Var a:t);
Var
i,j,k,r,m:word;
x:integer;
Begin
For i:=2 To n Do
begin
x:=a[i]; k:=1; r:=i-1;
While k<=r Do
begin
m:=(k+r) div 2;
If x<a[m] Then r:=m-1
Else k:=m+1
end;
For j:=i-1 DownTo l Do a[j+1]:=a[j];
a[k]:=x
end;
End; {Binary_Insertion}
Сортировка выбором
Прямой выбор. Этот метод основан на следующем правиле: выбираем элемент с наименьшим ключом. Он меняется местами с первым элементом. Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не останется только один элемент - наибольший. Этот метод называемый сортировкой простым выбором, в некотором смысле противоположен сортировке простыми включениями; при сортировке простым выбором рассматриваются все элементы входного массива для нахождения элемента с наименьшим ключом, и этот один очередной элемент отправляется в готовую последовательность.
Procedure Straight_Selection(n:word;Var a:t);
Var
i,j,k:word;
x:integer;
Begin
For i:=1 To n-1 Do
begin
x:=a[i]; k:=i;
For j:=i+1 To n Do
If x>a[j] Then
begin
k:=j; x:=a[j];
end;
a[k]:=a[i]; a[i]:=x;
end
End;{Straight_Selection}