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


Алгоритм


К прямым методам относится метод прямого выбора.

Рассматриваем весь ряд массива и выбираем элемент меньший или больший элемента а(i), определяем его место в массиве - k, и затем меняем местами элемент а(i) и элемент а(k).

for i = 1 to n - 1

  x = a(i)

  k = i

  for j = i + 1 to n

    if x > a(j) 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 x > a[j] then

        begin

          k := j;

          x := a[k];

        end;

    a[k] := a[i];

    a[i] := x;

  end;

 

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

§       Количество сравнений

§       Количество перемещений, когда массив упорядочен

§       Количество перемещений когда массив обратно отсортирован

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




- Начало -  - Назад -  - Вперед -



Книжный магазин