Программирование на ЭВМ

 

    В основе алгоритма лежит цикл, определяющий, для какого элемента ищем место в упорядоченной левой части последовательности.

          Ввод (последовательность А);

1. I:=2;
2. WHILE I ≤ N DO

          BEGIN

1. Найти место A_K+1 для A_I в упорядоченной части последовательности;
2. Сдвинуть элементы A_K+1, …, A_I вправо;
3. Поставить элемент  A[I] на нужное место;
4. I:=I+1;

      END;

    Вывод (последовательность А);

    Детализируем  п. 2.1. Нужно сравнивать A_I последовательно со всеми левыми соседями до элемента A_K ≤ A_I. Если такового не окажется, остановиться на первом элементе. Это циклические действия, причем удобнее оформить цикл по текущему номеру элемента. Тогда получим:

    2.1.1. Инициализация цикла;

    2.1.2. WHILE J>0 DO

                      BEGIN

    2.1.2.1. сравнить элементы A_I и A_J;

                      END;

    При реализации п.2.1.1 мы должны предусмотреть 3 момента:

1. значение A_I нужно запомнить, так как потеряется при сдвиге;
2. нужно зафиксировать номер I-1, т.к. с этого элемента начнется сравнение;
3. если A_I – минимальный элемент из A₁, …, A_I, он должен встать на первое место. Поэтому п. 2.1.1:

    2.1.1. X:=A[I];

                J:=I-1;

                K:=0;

    2.1.2.1. По результатам сравнения нужно сделать вывод: продолжать его или закончить цикл. Закончить цикл можно, положив J = 0.

    2.1.2.1.IF A[J]<=A[I] THEN

                BEGIN

                       K:=J;

                       J:=0;

                END;

               ELSE J:=J-1;

    2.2. Для сдвига последовательности нужно просматривать ее из конца в начало и последовательно сдвигать элементы. Это делается так:

    J:=I;

    WHILE J>K+1 DO

    BEGIN

          A[J]:=A[J-1];

          J:=J-1;

    END;

    2.3. A[K+1]:=X;

    Теперь  запишем  весь алгоритм.

    Ввод (последовательность А);

    I:=2;

    WHILE I ≤ N DO

    BEGIN

          X:=A[I];

          J:=I-1;

          K:=0;

      WHILE J>0 DO

          BEGIN

                IF A[J]<=A[I] THEN 

      BEGIN

                      K:=J;

                      J:=0;

      END

      ELSE J:=J-1;

             END;

      J:=I;

      WHILE J>K+1 DO

      BEGIN

                A[J]:=A[J-1];

                J:=J-1;

      END;

      A[K+1]:=X;

      I:=I+1;

    END;

    Вывод (последовательность А);

    Проведем  анализ трудоемкости простых алгоритмов сортировки на примере алгоритма простых вставок.

    Число сравнений ключей C_i на i-ом просмотре последовательности:

С_{i min} = 1, C_{i max} = i-1, тогда C_{i cp} = .

    Общее число сравнений (по формуле для суммы арифметической прогрессии ) равно

C _min = N-1,

C _cp = ,

C _max = .

    Число же перестановок (присваиваний элементов)    M_i  = C_i +2.

    Поэтому общее число присваиваний равно

M _min = 3(N –1),   (M_{i min} = 3)

M _cp = , (M_{i cp} = ),

M _max = , (M_{i max} = i + 4).

    Аналогично  можно проанализировать и два  других. Самый медленный – пузырек.

    Везде получим, что

          С ~ N ²,  M ~ N ².

    Для больших N это слишком много. Поэтому возникли улучшенные алгоритмы. Один из них – алгоритм Шелла.

    2.2.3. Алгоритм Шелла

    Алгоритм  предложен в 1959 году как усовершенствование метода простых вставок. Является самым простым среди улучшенных алгоритмов сортировки. Может работать и как улучшенный метод простого обмена («пузырька»).

     В «пузырьке» сравниваем соседние элементы. Но если в массиве элементы стоят очень далеко от своего истинного места,   то  придется   совершить   очень

                                                             много перестановок.

    Идея  метода состоит в следующем: сначала переставлять элементы на большие расстояния, а затем расстояния сужать. Расстояние между сравниваемыми элементами задается с помощью вспомогательной величины h – шага перестановки элементов. На каждом этапе рассматриваются a_i и a_i+h.

     При заданных h и начальном значении i все рассматриваемые на данном этапе элементы образуют цепочку. Если изменить i, то получим другие цепочки: 

    При уменьшении шага h количество цепочек уменьшается, а длина их возрастает. На самом последнем этапе h=1 (обязательно!), и весь массив представляет собой одну цепочку. «Пузырек» - частный случай алгоритма Шелла при h=1.

    Для нашего массива получим следующий процесс сортировки (табл.2.7).

Таблица 2.7 – Пример сортировки методом Шелла

Номер элемента	1	2	3	4	5	6	7	8
Исходная  последовательность	72	14	6	98	17	51	25	33
После сортировки при       h=4	17	14	6	33	72	51	25	98
h=2	6	14	17	33	25	51	72	98
h=1	6	14	17	25	33	51	72	98
Упорядоченная последовательность	6	14	17	25	33	51	72	98

    Таким образом, мы видим, что внешне процесс  существенно усложняется: вместо одной сортировки необходимо несколько (при каждом h – несколько цепочек и для каждой нужно провести сортировку). В чем же преимущество?

    Дело  в том, что на каждом шаге либо сортируется  относительно мало элементов (на первых этапах), либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок (на последующих этапах). Это важно, так как перестановки (присваивания) – более медленные операции, чем сравнения. Почему в конце концов массив окажется упорядоченным? Потому что последнее значение шага h=1 и весь массив окончательно упорядочивается как одна цепочка.

    Алгоритм  Шелла запишем теперь в виде процедуры. В ней следует учесть два важных момента.

1. Выбор начального значения h. Это самостоятельная достаточно интересная задача. Исследования показывают, что одно из лучших h_нач = é ù (скобки означают округление результата до целого значения в большую сторону).
2. Выбор формул пересчета для h. В общем случае неизвестно, какие расстояния дают наилучшие результаты. Но был замечен такой факт: значения h не должны быть множителями друг друга. Это связано с тем, что желательно, чтобы различные цепочки как можно чаще пересекались друг с другом. В нашем примере этого не происходит. Кнут показал [5], что целесообразно использовать

    h_j-1 = 2h_j +1  (в обратном порядке: 1, 3, 7, 15, …)

    или

    h_j-1 = 3h_j +1 (1, 4, 13, 40, …)

    Теперь  запишем весь алгоритм.

    CONST N = …;

    TYPE MAS = ARRAY [1..N] OF REAL;

    PROCEDURE SHELL (N: INTEGER; VAR A: MAS);

    VAR H, I: INTEGER;

    BEGIN

          H:=(N+2) DIV 3;

          WHILE H>0 DO

          BEGIN

                FOR I:=1 TO H DO

                BEGIN

                      Упорядочение алгоритма  пузырька с шагом Н, начиная         с i-го элемента

                END;

                IF H>5

       THEN H:= (H-1) DIV 2;

                ELSE IF H=1

                      THEN H:=0

                      ELSE H:=1

          END

    END;

    Алгоритм  Шелла до сих пор полностью  не исследован. Его анализ поставил ряд трудных математических проблем, которые пока так и не решены (как, например, проблема выбора h).

    При надлежащем выборе h трудоемкость алгоритма Шелла в худшем случае ~ n^3/2. В среднем ~ (log₂ n)²n. Это намного лучше, чем n².

    n = 100, n² = 10⁴, n^3/2 = 10³, (log₂ n)²n ~ 49n = 49*10²

    n = 10000, n² = 10⁸, n^3/2 = 10⁶, (log₂ n)²n ~ 14²n = 14²*10⁴

    На  практике   алгоритм   Шелла   целесообразнее   применять,   если

n ≤  (1÷5)10³ элементов. Теоретически показано, что трудоемкость оптимального алгоритма сортировки должна быть ~ n log₂ n.

    Для небольших n нецелесообразно применять сложные алгоритмы. Но при больших n улучшенные алгоритмы имеют преимущества.

    Рассмотрим  алгоритм, который является в среднем  оптимальным. Это алгоритм Хоара.

    2.2.4. Алгоритм Хоара

    Алгоритм  Хоара был разработан в 1961 – 62 гг. Это так называемая быстрая сортировка, представляющая собой улучшенный метод, основанный на обмене. Несмотря на то, что обычный обмен в среднем является самой неэффективной процедурой, его улучшение, о котором будем говорить, приводит к самому лучшему в настоящий момент алгоритму сортировки для массивов. Алгоритм основан на разделении массива опорным элементом.

     Возьмем из массива  какой-либо элемент Z (опорный) и будем сравнивать его поочередно со всеми остальными. Если M_i ≤ Z – переставляем M_i в начало последовательности.

      M_i ≥ Z – в конец. В результате получим:

    

    Z стоит на своем месте. 

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

    Алгоритм  Хоара запишем в виде процедуры.

    PROCEDURE HOARE (A, B: INTEGER; VAR M: MAS);