Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Сортировки включением




Сортировка прямым включением. Элементы условно разделяют на готовую 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}

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...