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

Листинг 2. Сортировка вставками





А[0].key:= - ∞;

for i:= 2 to n do

Begin

j:= i;

while (A[j] < A[j - 1]) or (j>=1) do

Begin

temp := A[j];

A[j] := A[j-1];

A[j-1] := temp;

j:= j - 1

End

End

Пример 7.2. В табл. 6 показан начальный список из табл. 5 и последовательные этапы алгоритма вставкой для i = 2, 3, ..., 6. После каждого этапа алгоритма элементы, расположенные выше линии, уже упорядочены, хотя между ними на последующих этапах могут быть вставлены элементы, которые сейчас находятся ниже линии.

Таблица 6. Этапы сортировки вставками

i начальное положение 1-й проход 2-й проход 3-й проход 4-й проход 5-й проход
1669
1669 1902
i i = 1 i = 2 i = 3 i = 4 i = 5 i = 6

 

Задача 7.11. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию вставками.

Листинг программы

program task2;

uses crt;

const n = 10;

type vector = array [1..n] of integer;

var

a : Vector;

i, j : integer;

temp : integer;

 

begin

clrscr;

randomize;

for i :=1 to n do a[i] := random(11)-4;

for i :=1 to n do

writeln ('a[', i, ']=', a[i]:3);

 

for i := 2 to n do

begin

j := i;

while (a[j] < a[j-1]) and (j>=1) do

begin

temp := a[j];

a[j] := a[j-1];

a[j-1] := temp;

j:=j-1;

end;

end;

 

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.

Сортировка посредством выбора

Идея сортировки посредством выбора также проста. На i-м этапе сортировки выбирается запись с наименьшим ключом среди записей A[i], ..., А[n] и меняется местами с записью A[i]. В результате после i-гo этапа все записи А[1], ..., A[i] будут упорядочены. Сортировку посредством выбора можно описать следующим образом:

for i: = 1 to n - 1 do

выбрать среди A[i], ..., А[n] элемент с наименьшим ключом и

поменять его местами с A[i];

Более полный код, реализующий этот метод сортировки, приведен в листинге 4.

Листинг 3. Сортировка посредством выбора

Var

lowkey: keytype; { текущий наименьший ключ, найденный

при проходе по элементам A[i], ..., А[n] }

lowindex: integer; { позиция элемента с ключом lowkey }

temp : recordtype;



Begin

for i:= 1 to n - 1 do begin

lowindex:= i;

lowkey:= A[i].key;

for j:= i + 1 to n do begin

{ сравнение ключей с текущим ключом lowkey}

if A[j].key < lowkey then begin

lowkey:= A[j].key;

lowindex: = j

end;

temp := A[i];

A[i] := A[lowindex];

A[lowindex] := temp;

End; End; End;

Пример 7.3. В табл. 7 показаны этапы сортировки посредством выбора для списка из табл. 5. Например, на 1-м этапе значение lowindex равно 6, т.е. позиции значения 79, которое меняется со значением 1902 , элементом А[1].

Линии в табл. 3 показывают, что элементы, расположенные выше ее, имеют наименьшие значения ключей и уже упорядочены. После (n - 1)-го этапа элемент А[n] также стоит на "правильном" месте, так как выше его все записи имеют меньшие значения ключей.

Таблица 7. Сортировка посредством выбора

i начальное положение 1-й проход 2-й проход 3-й проход 4-й проход 5-й проход
1980
1902 1963
i   i = 1 low = 6 i = 2 low = 2 i = 3 low = 3 i = 4 low = 6 i = 5 low = 6

 

Задача 7.12. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством выбора.

Листинг программы

program task3;

uses crt;

const n = 10;

type vector = array [1..n] of integer;

var

a : Vector;

i, j : integer;

temp : integer;

 

begin

clrscr;

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

 

for i := 1 to n-1 do

begin

for j := i+1 to n do

begin

if a[j] < a[i] then

begin

temp := a[j];

a[j] := a[i];

a[i] := temp;

end;

end;

end;

 

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.


Быстрая сортировка

Данный алгоритм является самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка".[1] В этом алгоритме для сортировки элементов массива А[1], ..., А[n] из этих элементов выбирается некоторое значение ключа v в качестве опорного элемента, относительно которого переупорядочиваются элементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса j все переставленные элементы А[1], ..., A[j] имели значения ключей, меньшие, чем v, а все элементы A[j + 1], ..., А[n] — значения ключей, большие или равные v. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов А[1], ..., A[j] и A[j + 1], ..., А[n] для упорядочивания этих множеств по отдельности. Поскольку все значения ключей в первом множестве меньше, чем значения ключей во втором множестве, то исходный массив будет отсортирован правильно.

Задача 7.13. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством быстрой сортировки.

Листинг программы

program task4;

uses crt;

const n = 10;

type vector = array [ 1..n] of integer;

var a : Vector;

i, j : integer;

temp : integer;

procedure QuickSort;

procedure sort (l, r : integer);

var i, j, w, x : integer;

begin

i := l;

j := r;

x := a[(l+r) div 2];

repeat

while a[i] < x do

i :=i+1;

while a[j] > x do

j := j-1;

if i <= j then

begin

w := a[i];

a[i]:=a[j];

a[j]:=w;

i := i+1;

j := j-1;

end;

until i > j;

if l < j then sort(l,j);

if i < r then sort(i,r);

end;

begin

sort (1,n);

end;

 

begin

clrscr;

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

quicksort;

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.





Рекомендуемые страницы:

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



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.