 |
Листинг 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.
|
|
|
