Структуры и алгоритмы обработки данных

       

Сортировка методом прямого выбора


Этот прием основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом a 1.

3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый "большой" элемент.

Алгоритм формулируется так:

for i = 1 to n - 1

  x = a(i)

  k = i

  for j = i + 1 to n

    if  a(j) < x  then

      k = j



      x = a(k)

    endif

  next j

  a(k) = a(i)

  a(i) = x

next i

return

for i := 1 to n - 1 do

  begin

    x := a[i];

    k := i;

    for j := i + 1 to n do

      if a[j] < x then

        begin

          k := j;

          x := a[k];

        end;

    a[k] := a[i];

    a[i] := x;

  end;

 

Эффективность алгоритма:

Число сравнений ключей C, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для C  при любом расположении ключей имеем:

C = n(n-1)/2

Порядок числа сравнений, таким образом, О(n2)

Число перестановок  минимально Мmin = 3(n - 1) в случае изначально упорядоченных ключей и максимально, Мmax = 3(n - 1) + С, т.е. порядок О(n2), если первоначально ключи располагались в обратном порядке.

В худшем случае сортировка прямым выбором дает порядок n2, как  для   числа сравнений, так и для числа перемещений.

 



Содержание раздела