Методы сортировки массивов

            FOR J:=I+1 TO N DO IF A[J]<X THEN

               BEGIN

                     R:=J;

                     X:=A[R]

               END;

            A[R]:=A[I];

            A[I]:=X

        END;

    WRITELN('Результат:');

    FOR I:=1 TO N DO WRITE(A[I],' ')

END.

Анализ  прямого  выбора. Число  сравнений  ключей  (С), очевидно  не зависит  от  начального  порядка  ключей. Для  С  мы  имеем C = (n2 – n)/2 (2.10.).

Число  перестановок  минимально: Mmin = 3*(n-1) (2.11.).

В  случае  изначально  упорядоченных  ключей  и  максимально                  Mmax = n2/4 + 3*(n-1) (2.12.)

Определим  Мavg . Для достаточно  больших n  мы  можем игнорировать дробные составляющие  и поэтому аппроксимировать  среднее число присваиваний   на  i-м просмотре выражением  Fi = ln i + g + 1 (2.13.), где  g = 0.577216… - константа Эйлера.

Среднее  число  пересылок  Mavg в сортировке   с выбором есть  сумма Fi с  i  от  1  до  n

         Mavg = n*(g + 1) + (Si: 1<=i<=n: ln i)      (2.14.)

Вновь  аппроксимируя  эту  сумму дискретных  членов  интегралом

         Integral (1:n) ln x dx = x*(ln x – 1) = n*ln (n) – n + 1        (2.15.)

Получаем  приблизительное  значение               

        Mavg = n*(ln (n) + g) .   (2.16.)

2.1.3. Сортировка  с  помощью  прямого  обмена.

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

ПРОГРАММА 2.4. ПУЗЫРЬКОВАЯ  СОРТИРОВКА.

PROGRAM BS;

VAR

     I,J,X,N:INTEGER;

    A:ARRAY[0..50] OF INTEGER;

BEGIN

   WRITELN('Введи длину массива');

    READ(N);

    WRITELN('Введи массив');

    FOR I:=1 TO N DO READ(A[I]);

    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;

     WRITELN('Результат:');

      FOR I:=1 TO N DO

          WRITE(A[I],' ')

END.                                      

Улучшения  этого  алгоритма  напрашиваются  сами  собой:

1. Запоминать, были  или  не  были  перестановки  в  процессе

некоторого  прохода.

2. Запоминать   не  только  сам  факт, что  обмен  имел  место, но  и

положение  (индекс)  последнего  обмена.

3. Чередовать  направление  последовательных  просмотров.                     

Получающийся  при  этом  алгоритм  мы  назовем  “шейкерной”  сортировкой (ShakerSoft).

Анализ  пузырьковой  и  шейкерной  сортировок. Число  сравнений  в строго  обменном  алгоритме C = (n2 – n)/2, (2.17.), а  минимальное, среднее  и  максимальное  число  перемещений  элементов  (присваиваний)  равно  соответственно M = 0,   Mavg = 3*(n2 – n)/2,   Mmax = 3*(n2 – n)/4      (2.18.)

Анализ  же  улучшенных  методов, особенно  шейкерной   сортировки  довольно сложен. Минимальное  число  сравнений Cmin = n – 1. Кнут  считает, что улучшенной  пузырьковой  сортировки  среднее число проходов  пропорционально   n – k1n1/2,  а среднее число сравнений пропорционально &#189;(n2 – n(k2 +ln n)). 

ПРОГРАММА 2.5. ШЕЙКЕРНАЯ  СОРТИРОВКА.

PROGRAM SS;

VAR

     J,L,K,R,X,N,I:INTEGER;

     A:ARRAY[0..50] OF INTEGER;

BEGIN

    WRITELN('Введи длину массива’);

    READ(N);

    WRITELN('Введи массив');

    FOR I:=1 TO N DO

        READ(A[I]);

     L:=2;

     R:=N;

     K:=N;

        REPEAT

             FOR J:=R DOWNTO L DO

            IF A[J-1]>A[J] THEN

                  BEGIN

                  X:=A[J-1];

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

                  A[J]:=X;

                  K:=J

                 END;

             L:=K+1;

             FOR J:=L TO R DO

             IF A[J-1]>A[J] THEN

                 BEGIN

                      X:=A[J-1];

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

                      A[J]:=X;

                      K:=J

                 END;

             R:=K-1

         UNTIL L>R;

             WRITELN('Результат:');

             FOR I:=1 TO N DO

                 WRITE(A[I],' ')

END.

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

2.2. Улучшенные методы  сортировки массивов.

2.2.1.Метод  Шелла.

В  1959  году  Д. Шеллом  было  предложено  усовершенствование  сортировки  с  помощью  прямого  включения. Сначала  отдельно  сортируются  и группируются  элементы, отстоящие  друг  от  друга  на  расстояние  4. Такой процесс  называется  четверной  сортировкой. В нашем  примере  восемь  элементов и  каждая  группа  состоит  из  двух  элементов. После  первого  прохода  элементы  перегруппировываются – теперь  каждый  элемент  группы отстоит  от другого  на  две  позиции – и  вновь  сортируются. Это  называется  двойной сортировкой. На  третьем  подходе  идет  обычная  или  одинарная  сортировка. На  каждом  этапе  либо  сортируется  относительно  мало  элементов, либо  элементы  уже  довольно  хорошо  упорядочены  и  требуют  сравнительно  немного  перестановок.    

ПРОГРАММА 2.6. СОРТИРОВКА  ШЕЛЛА..

PROGRAM SHELLS;

CONST  T=4;

H: ARRAY[1..4] OF INTEGER = (15,7,3,1);

VAR

      I,J,K,S,X,N,M:INTEGER;

      A:ARRAY[-16..50] OF INTEGER;

BEGIN

     WRITELN('Введи длину массива');

      READ(N);

      WRITELN('Введи массив');

      FOR I:=1 TO N DO

          READ(A[I]);

      FOR M:=1 TO T DO

         BEGIN

                K:=H[M];

                S:=-K;

                FOR I:=K+1 TO N DO

                     BEGIN

                         X:=A[I];

                         J:=I-K;

                         IF S=0 THEN S:=-K;

                         INC(S);

                         A[S]:=X;

                         WHILE X<A[J] DO

                              BEGIN

                                  A[J+K]:=A[J];

                                  J:=J-K

                              END;

                         A[J+K]:=X;

                     END;

          END;

      WRITELN('Результат:');

      FOR I:=1 TO N DO

      WRITE(A[I],' ')

END.

Анализ  сортировки  Шелла. Нам не  известно,  какие  расстояния  дают  наилучший  результат. Но  они  не  должны  быть  множителями  один  другого. Справедлива  такая  теорема: если  k-отсортированную последовательность i-отсортировать, то  она остается  k-отсортированной. Кнут показывает, что имеет смысл использовать  такую последовательность, в которой   hk-1 = 3hk + 1,  ht = 1  и t = [log2 n] – 1.       (2.19.)         

2.2.2.Сортировка  с  помощью  дерева.

Метод  сортировки  с  помощью  прямого  выбора  основан  на повторяющихся  поисках  наименьшего  ключа  среди  n  элементов, среди n-1 оставшихся  элементов  и т. д. Как же  усовершенствовать упомянутый  метод сортировки? Этого можно добиться, действуя  согласно  следующим этапам сортировки:

1. Оставлять  после каждого  прохода больше  информации, чем просто  идентификация  единственного  минимального  элемента. Проделав  n-1 сравнений, мы  можем построить дерево  выбора  вроде представленного на  рисунке 2.1.

   

                                                              06

            

12                                                                              

                       06

 

    44             12               18                06

 

     44      55     12      42     94     18      06       67

РИСУНОК 2.1. ПОВТОРЯЮЩИЙСЯ  ВЫБОР  СРЕДИ  ДВУХ  КЛЮЧЕЙ.

2. Спуск вдоль пути, отмеченного  наименьшим  элементом, и исключение  его  из  дерева  путем  замены  либо  на  пустой  элемент   в  самом  низу, либо  на  элемент  из  соседний  ветви  в  промежуточных  вершинах (см. рисунки  2.2 и 2.3.).

Д. Уилльямсом  был  изобретен  метод   Heapsort, в котором было получено  существенное  улучшение традиционных  сортировок  с помощью деревьев. Пирамида  определяется  как последовательность  ключей a[L], a[L+1], … , a[R],  такая, что a[i] <= a[2i]  и a[i] <= a[2i+1]  для i=L…R/2.               

Р. Флойдом  был  предложен  некий  “лаконичный”  способ  построения пирамиды  на  ”том  же  месте”. Здесь  a[1] … a[n] – некий массив, причем a[m]…a[n] (m = [n DIV 2] + 1 )  уже образуют  пирамиду, поскольку индексов  i и j, удовлетворяющих соотношению  j = 2i (или j = 2i + 1), просто  не  существует.

         

12 

    44             12               18                 

     44      55     12      42     94     18                  67

РИСУНОК 2.2.ВЫБОР  НАИМЕНЬШЕГО  КЛЮЧА.

                                                                            06