7.3 Сортировка вставками


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


    Ниже приведен пример алгоритма сортировки простыми вставками (просеиванием или погружением).

    Процедура сортировки вставками на языке "Паскаль"

    procedure insert(item:array of char; n:integer);
    var
      a,b:integer; t:char;
    begin
      for a:=1 to n-1 do
      begin
        t:=item[a];
        b:=a-1;
        while (b>=0) and (t<item[b]) do
        begin
          item[b+1]:=item[b];
          b:=b-1
        end;
        item[b+1]:=t
      end
    end;

    Процедура сортировки вставками на языках C/C++

    void insert_sort(char* item,int n)
    {
      int a,b;
      char buf;
      for(a=1; a<n; ++a)
      {
        buf=item[a];
        for(b=a-1; b>=0 && buf<item[b]; --b)
          item[b+1]=item[b];
        item[b+1]=buf;
      }
    }


    В отличии от предыдущих алгоритмов, число сравнений зависит от исходной упорядоченности массива. Если массив уже отсортирован в требуемом порядке, то за всё время работы процедуры выполняется N − 1 сравнений, если не отсортирован, то (N2 + N)/2 сравнений.




    В исходном массиве данный алгоритм произведет следующие перестановки:




    Этот алгоритм в среднем лишь немного лучше предыдущих (также за счёт разнесения операций присваивания, выполняющих обмен, по разным циклам), но обладает несколькими преимуществами:
    − Его поведение естественно: если массив уже отсортирован в нужном порядке, алгоритм проводит минимальное количество вычислений, и максимальное, если массив отсортирован в порядке, обратном требуемому. Происходит быстрая обработка почти упорядоченных массивов;
    − порядок следования одинаковых ключей не изменяется. Если список отсортирован по двум ключам, то после сортировки вставками он остается отсортированным по обоим ключам;
    − одна из самых коротких процедур.


    Недостаток: при каждой вставке производится сдвиг массива, следовательно даже при относительно малом числе сравнений число перестановок может быть довольно значительным.


    Существуют варианты: бинарные вставки, двухпутевые вставки.


    < Назад | Вперед >

    Хостинг от uCoz