Линейный выбор с обменом

Идея. Сортировка линейным выбором с обменом рассматривает все записи исходной последовательности для нахождения записи с необходимым ключом и размещает ее в готовой последовательности на требуемой позиции. Просмотр последовательности записей, длина которой уменьшается на единицу при каждом просмотре, заканчивается, когда в

ней остается только одна запись, занимающая последнюю позицию.

Структурограмма алгоритма сортировки методом выбора с обменом приведена следующем рисунке.

J = 1, N - 1

В течениe 1-го просмотра находится запись с наименьшим ключом, которая меняется местами с первой записью. 2-й просмотр идентичен 1-му с той лишь разницей, что первая запись исключается из рассмотрения. 3-й просмотр начинается сравнением ключа из 3-й позиции и т.д. Эта

процедура заканчивается, когда свое место занимает (N-1)-я запись.

Пример.

5, 4, 1, 2, 3

J=1, L=1,

I=2; L=2,

I=3; L=3,

I=4;

I=5;

1 4 5 2 3

J=2, L=2,

I=3;

I=4; L=4,

I=5;

1 2 5 4 3

J=3, L=3,

I=4; L=4,

I=5; L=5,

1 2 3 4 5

J=4, L=4,

I=5;

1, 2, 3, 4, 5

procedure SortMin (var Arr : array of Integer; n : Integer);var i, j : Integer; Min, Pos, Temp : Integer;begin for i := 0 to n - 2 do begin Min := Arr [i]; Pos := i; for j := i + 1 to n-1 do if Arr [j] < Min then begin Min := Arr [j]; Pos := j; end; Temp := Arr [i]; Arr [i] := Arr [Pos]; Arr [Pos] := Temp; end;end;

Метод выбора характеризуется следующими параметрами.

Качественные:

1. Простота программирования.

2. Требуется наличие всех записей до начала сортировки.

3. Число записей сокращается от просмотра к просмотру. На

каждом последующем просмотре выполняется на одно сравнение меньше.

4. Нет ускорения, если записи отсортированы.

Количественные:

1. Число сравнений N*(N-1)/2.

2. Число перестановок (обменов) - (N-1).

3. Дополнительный объем памяти требуется для реализации операции

обмена.

Вернуться в оглавление