Сортировка выбором
Материал из DRKB
Сортировка выбором.
- A[1..N] - сортируемый массив из n элементов.
for ( i=1; i<N; i++)
Hайти наименьший из элементов i..N и поменять его местами с i-м.
Пример действий для случайного массива A[1..8]
44 55 12 42 94 18 06 67 исходный массив i=1 06| 55 12 42 94 18 44 67 06 <-> 44 i=2 06 12| 55 42 94 18 44 67 12 <-> 55 i=3 06 12 18| 42 94 55 44 67 18 <-> 55 i=4 06 12 18 42| 94 55 44 67 42 <-> 42 i=5 06 12 18 42 44| 55 94 67 44 <-> 94 i=6 06 12 18 42 44 55| 94 67 55 <-> 55 i=7 06 12 18 42 44 55 67| 94 67 <-> 94
Вертикальной чертой отмечена граница уже отсортированной части массива.
Сортировка выбором - простейший алгоритм, на практике не используемый ввиду низкого быстродействия. Вместо этого применяют ее улучшение - пирамидальную сортировку (Heapsort), описанную в другом вопросе, а также (иногда) 'древесную сортировку' (TreeSort).
Пример на Паскале - Hиколас Вирт.
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure SelectSort;
var
i, j, k: index;
x: item;
begin
for i := 1 to n-1 do
begin
k := i;
x := a[i];
for j := i+1 to n do
begin
if a[j].key < x.key then
begin
k := j;
x := a[j];
end;
end;
a[k] := a[i];
a[i] := x;
end;
end;
Source: http://algolist.manual.ru
ID: 04155
{ **** UBPFD *********** by kladovka.net.ru ****
>> Сортировка различными методами
Сортировка одномерного массива значений типа Double методами:
2) Выбора (SelectionSort);
Зависимости: Math
Автор: iZEN, izen@mail.ru
Copyright: адаптация для Delphi
Дата: 14 сентября 2004 г.
********************************************** }
{ Сортировка SelectionSort }
procedure SelectionSort(var data: array of Double);
var
lo, hi, i, j: Integer;
t: Double;
begin
lo := Low(data);
hi := High(data);
for i := lo to hi do
for j := hi downto i + 1 do
if data[i] > data[j] then
begin
t := data[i];
data[i] := data[j];
data[j] := t;
end;
end;
Author: iZEN
ID: 04156