Сортировка выбором

Материал из 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