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

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

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

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

	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;If Pos<>I then begin Temp:= Arr [i]; Arr [i]:= Arr [Pos]; Arr [Pos]:= Temp; end; end;end;

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

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

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

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

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

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

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

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

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

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

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

обмена.