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


Краткая теория - часть 2


 

       Неформальный алгоритм

for i = 2 to n

  x = a(i)

  находим место среди а(1)…а(i) для включения х

next i

Программа  на Паскале:

for i := 2 to n do

  begin

    x := a[i];

    a[0] = x;

    for j := i - 1 downto 1 do

      if x < a[j]

          then a[j + 1] := a[j]

          else a[j + 1] := x;

  end; 

 

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

Количество сравнений в худшем случае будет равно

(n - 1)(n - 1).

 

 

 

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

 

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

Программа на Паскале:

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;

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

Число сравнений М =

.

Число перемещений Cmin = 3(n - 1), Cmax = 3(n - 1)

 

(порядок n2).

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

 

   3.2.3 Сортировка с помощью прямого обмена (пузырьковая)

Идея: n - 1 раз проходят массив снизу вверх. При этом ключи попарно сравниваются. Если нижний ключ в паре меньше верхнего, то их меняют местами.

Программа на  Паскале:

for i := 2 to n do

  for j := n downto i do

    if a[j - 1] > a[j] then

      begin

        x := a[j - 1];

        a[j - 1] := a[j];

        a[j] := x;

      end;

 

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не переставлять элементы, можно ввести флажок.

Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление внутри цикла.

 

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

число сравнений М =

,             

число перемещений Cmax = 3

.

 




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



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