ГЛАВА 7. СОРТИРОВКА МАССИВОВ

Под сортировкой массивов понимают процесс перестановки элементов массива в определенном порядке. Цель сортировки – облегчить последующий поиск элементов в отсортированном массиве.

Выводы сортировки важны при обработке данных, с ними связаны многие фундаментальные приемы построения алгоритмов.

Простые методы сортировки можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1)сортировка выбором;

2)сортировка обменом;

3)сортировка включением.

Простые методы сортировки требуют порядка n x n сравнений элементов (ключей).

Будем рассматривать массив A, состоящий из элементов вещественного типа. Сортировку будем осуществлять в порядке неубывания значений элементов массива.

Алгоритм сортировки будем представлять в виде процедур. Определим следующий тип данных:

Type vector=array[1..nmax] of real;

Здесь nmax – максимально возможный размер вектора.

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

Сортировка основана на идее многократного выбора (сначала находится наибольший элемент, затем второй по величине и т.д.) и сводится к следующему:

1.Найти элемент с наибольшим значением.

2.Поменять значениями найденный элемент и последний.

3.Уменьшить на единицу количество просматриваемых элементов.

4.Если количество элементов для следующего просмотра больше единицы, то повторить пункты, начиная с 1-го.

58

Алгоритм:

1.Цикл по количеству просматриваемых элементов {i:=n, n-1…2}.

2.Найти номер k-го максимального элемента среди a[1], a[2] …

a[i].

3. Поменять местами значения элементов a[k] и a[i].

Procedure sort_choice(var a : vector; n : integer); var x : real;

i, j, k : integer;

begin

for i:=n downto 2 Do begin

k:=1;

for j:=2 to i do

if a[j]>a[k] then k:=j; x:=a[k]; a[k]:=a[i]; a[i]:=x

end;

end;

Сортировка обменом (метод «пузырька»)

Сортировка обменом предусматривает систематический обмен значениями (местами) тех пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется.

Алгоритм:

1.Цикл по количеству просмотров.

2.Цикл по количеству сравниваемых значений при очередном просмотре. Если упорядоченность в паре нарушена, то выполнить обмен значениями.

Количество просмотров (повторений) во внешнем цикле равно n-1. Оно может быть уменьшено, если i-й шаг показал, что массив уже упорядочен (во внутреннем цикле не было перестановок).

59

Procedure sort_exсhange(var a : vector; n : integer); var x : real;

i,j : integer; bound : boolean; begin

bound:=true;

i:=1;

while bound do begin

bound:=false; for j:=1 to n-i do

if a[j]>a[j+1] then begin

bound:=true;

x:=a[j];

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

a[j+1]:=x

end

end;

if bound then i:=i+1

end;

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

Сортировка основана на следующем:

Предполагается, что элементы a[1], a[2],… a[i-1] упорядочены, a[i] ставится на соответствующее место, не нарушая свойства упорядоченности.

Для этого a[i] сравнивается по очереди с a[i-1], a[i-2],… до тех пор, пока не будет обнаружено, что элемент a[i] следует поставить между a[j] и a[j+1] (j – номер элемента в a[1], a[2],… a[i-1], за которым следует поставить a[i]).

60

Тогда элементы a[j+1],… a[i-1] сдвигаются на одну позицию вправо, а новая запись помещается в позицию j+1. Удобно совмещать сравнения и перемещения.

Procedure sort_include(var a : vector; n : integer); var x : real;

i,j : integer; begin

for i:=2 To n Do begin

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

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

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

end;

a[j+1]:=x

end

end;

Можно уменьшить количество сравнений при организации внутреннего цикла. Для этого используется метод барьера: вставляемое значение помещается в начало массива на дополнительное нулевое место (a[0]:=a[i]); диапазон индексов в определении типа vector расширяется:

Type vector=array[0..nmax] of real;

Получим другой вариант сортировки методом включения:

Procedure sort_include1(var a : vector; n : integer); var x : real;

i,j : integer; begin

for i:=2 to n do begin

x:=a[i];

61