Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Линейный выбор с обменом
|
|
Идея. Сортировка линейным выбором с обменом рассматривает все записи исходной последовательности для нахождения записи с необходимым ключом и размещает ее в готовой последовательности на требуемой позиции. Просмотр последовательности записей, длина которой уменьшается на единицу при каждом просмотре, заканчивается, когда в
ней остается только одна запись, занимающая последнюю позицию.
Структурограмма алгоритма сортировки методом выбора с обменом приведена следующем рисунке.
|
В течени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. Дополнительный объем памяти требуется для реализации операции
обмена.