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

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


Такой метод  широко используется при игре в карты. Элементы мысленно делятся на уже готовую последовательность  a1,...,ai-1 и исходную последовательность. При каждом шаге, начиная с i = 2  и увеличивая i  каждый раз на единицу, из исхожной последовательности извлекается i-й элемент и перекладывается  в готовую последовательность, при этом он вставляется на нужное место.На рис. 6.2 показан в качестве примера процесс сортировки  с помощью включения шести случайно выбранных чисел. Алгоритм этой сортировки таков:

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   

С барьером:

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

Паскаль:

Без  барьера:

for i:= 2 to n do

  begin

    x:= a(i);

    for j:= i - 1downto 1 do

      if x < a(j ) then

         a(j +1):= a(j )

       else  goto  1;

      end;

     end;

1:   a(j + 1):= x;

  end;

  end;

С барьером:

  for i := 2 to n do

    begin

      x:= a(i);

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

      j:= i - 1;

      while  x < a(j ) do

        begin

          a(j +1):= a(j );

           j:=j - 1;

       end;

       a(j +1):= x;

  end;

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

 

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

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, Сmax = n(n - 1)/2, т. е. - О (n2).   Количество перестановок Mmax = Cmax + 3(n-1), т.е.  -  О (n2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: Cmin  = n-1; Mmin = =3(n-1).



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