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

Previous  Top  Next

    
 

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

====================================================================

 

   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иколас Вирт.

Code:

{ Сортируются записи типа 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

                    if a[j].key < x.key then

                        begin k:=j; x:=a[j];

                        end;

                a[k]:=a[i]; a[i]:=x;

        end;

end;

 

 

 

http://algolist.manual.ru

©Drkb::04155


Code:

{ **** 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;

 

 

©Drkb::04156