34.Сортировка методом прямого включения. Сортировка методом прямого включения

Элементы мысленно делятся на уже готовую последовательность  a₁,...,a_i-1 и исходную последовательность.

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

Суть алгоритма такова:

for i = 2 to n

    x = a(i)

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

next i

Есть два алгоритма сортировки методом прямого включения. Первый - без барьера

Алгоритм сортировки методом прямого включения без барьера

for i = 2 to n

    x = a(i)

    for j = i - 1 downto 1

      if x < a(j)

         then  a( j + 1) = a(j)

         else  go to  L               

      endif

     next j

 L:  a( j + 1) = x

next i

return

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

Алгоритм сортировки методом прямого включения с барьером

for i = 2 to n

   x = a(i)

   a(0) = x   {a(0) - барьер}

   j = i - 1

   while  x < a(j )  do

       a( j +1) = a(j )

       j = j - 1

   endwhile 

   a( j +1) = x

next i

return

Эффективность алгоритма прямого включения

Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С_max = n(n - 1)/2, т. е. - О (n²).   Количество перестановок M_max = C_max + 3(n-1), т.е.  -  О (n²). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C_min  = n-1; M_min = =3(n-1).

35.Сортировка методом прямого обмена.

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

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

Как и в упоминавшемся методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на рисунке ниже).

Такой метод широко известен под именем "пузырьковая сортировка".

Алгоритм метода прямого обмена

for i = 2 to n

  for j = n to i step -1

    if a(j) < a(j - 1) then

        x = a(j - 1)

        a(j - 1) = a(j)

        a(j) = x

    endif

   next j

next i

return

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

fl = true

for i = 2 to n

if fl = false then return

endif

fl = false

  for j = n to i step -1

    if a(j) < a(j - 1) then

      fl = true

      x = a(j - 1)

      a(j - 1) = a(j)

      a(j) = x

    endif

  next j

next i

return

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

 

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

 

Эффективность алгоритма сортировки прямым обменом

Число сравнений C_max = n(n-1)/2  , порядок  О(n²).

Число перемещений М_max=3C_max=3n(n-1)/2,  порядок О(n²).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

C_min = n - 1, порядок  О(n),

а перемещения вообще отсутствуют

Сравнительный анализ прямых методов сортировок показывает, что обменная "сортировка"  в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно  упорядоченных массивов пузырьковая сортировка даже имеет преимущество.