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

            

12                              18 

    44             12               18                67 

     44      55     12      42     94     18                 67

РИСУНОК 2.3. ЗАПОЛНЕНИЕ  ДЫРОК.

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

 

                                                                  a[1]

            

             a[2]                                 a[3]

 

  a[4]               a[5]              a[6]                 a[7]

                

   a[8]      a[9] a[10]    a[11] a[12]  a[13] a[14]   a[15]   

РИСУНОК 2.4.МАССИВ, ПРЕДСТАВЛЕННЫЙ  В  ВИДЕ  ДВОИЧНОГО  ДЕРЕВА.

ПРОГРАММА 2.7. HEARSORT.

PROGRAM HS;

VAR

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

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

PROCEDURE SIFT(L,R: INTEGER);

VAR

     I,J,X: INTEGER;

BEGIN

     I:=L;

     J:=2*L;

     X:=A[L];

     IF (J<R)AND(A[J]<A[J+1]) THEN INC(J);

     WHILE (J<=R)AND(X<A[J]) DO

          BEGIN

               A[I]:=A[J];

               A[J]:=X;

               I:=J;

               J:=2*J;

               IF (J<R)AND(A[J]<A[J+1]) THEN INC(J);

         END;

 END;

BEGIN

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

     READ(N);

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

     FOR I:=1 TO N DO

     READ(A[I]);

     L:=(N DIV 2)+1;

     R:=N;

     WHILE L>1 DO

         BEGIN

              DEC(L);

              SIFT(L,N)

         END;

      WHILE R>1 DO

            BEGIN

                X:=A[1];

                A[1]:=A[R];

                A[R]:=X;

                DEC(R);

                SIFT(1,R);

            END;

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

         FOR I:=1 TO N DO

         WRITE(A[I],' ')

END.

Анализ  Heapsort. Heapsort  очень эффективна  для большого  числа элементов n; чем больше  n, тем лучше она работает.

В  худшем  случае  нужно  n/2  сдвигающих  шагов, они сдвигают элементы  на  log(n/2), log(n/2 – 1), … ,log(n – 1)  позиций (логарифм по [основанию 2]  «обрубается»  до  следующего  меньшего  целого). Следовательно фаза  сортировки  будет n – 1  сдвигов с самое большое log(n-1), log(n-2), … , 1  перемещениями. Можно  сделать  вывод, что  даже  в  самом  плохом  из  возможных  случаев Heapsort  потребуется n*log n  шагов. Великолепная производительность в таких случаях – одно  из  привлекательных свойств Heapsort.

2.2.3. Сортировка с помощью разделения.

Этот  улучшенный  метод  сортировки  основан  на  обмене. Это  самый  лучший  из  всех  известных  на  данный  момент  методов сортировки  массивов. Его  производительность  столь  впечатляюща, что  изобретатель  Ч. Хоар  назвал этот  метод  быстрой   сортировкой  (Quicksort) . В Quicksort   исходят из  того  соображения, что  для  достижения  наилучшей эффективности сначала лучше производить перестановки  на  большие расстояния. Предположим, что у нас есть  n  элементов, расположенных по  ключам  в обратном  порядке. Их можно отсортировать за  n/2  обменов, сначала поменять  местами  самый  левый  с  самым  правым, а  затем  последовательно  сдвигаться  с  двух  сторон. Это возможно  в  том  случае, когда  мы знаем, что  порядок  действительно  обратный.  Однако  полученный  при  этом  алгоритм  может оказаться  и  не удачным, что, например,    происходит  в  случае   n  идентичных  ключей: для разделения  нужно n/2  обменов. Этих  необязательных  обменов можно избежать, если  операторы просмотра заменить  на  такие:

                       WHILE  a[i] <= x  DO  i := i + 1  END;

                       WHILE  x <=  a[i] DO  j := j – 1  END

В  этом  случае  x  не  работает  как барьер  для двух  просмотров. В результате  просмотры массива со  всеми идентичными ключами приведут  к переходу  через границы массива.

Наша  цель – не только провести разделение на части  исходного  массива элементов, но и отсортировать его. Будем  применять  процесс  разделения  к получившимся  двум  частям, до  тех  пор, пока  каждая из частей  не будет состоять из одного-единственного  элемента. Эти  действия  описываются  в  программе 2.8.

ПРОГРАММА 2.8. QUICKSORT.

PROGRAM QS;

VAR

     N,I:INTEGER;

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

PROCEDURE SORT(L,R: INTEGER);

VAR

     I,J,X,W: INTEGER;

BEGIN

      I:=L;

      J:=R;

      X:=A[(L+R) DIV 2];

          REPEAT

               WHILE A[I]<X DO INC(I);

               WHILE X<A[J] DO DEC(J);

               IF I<=J THEN

                      BEGIN

                            W:=A[I];

                            A[I]:=A[J];

                            A[J]:=W;

                            INC(I);

                            DEC(J);

                      END;

          UNTIL I>J;

         IF L<J THEN SORT(L,J);

         IF I<R THEN SORT(I,R);

END;

BEGIN

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

      READ(N);

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

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

       SORT(1, N);

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

       FOR I:=1 TO N DO

            WRITE(A[I],' ')

END.

Анализ  Quicksort. Процесс разделения  идет  следующим образом: выбрав  некоторое  граничное  значение  x, мы  затем проходим целиком по всему массиву. При этом  выполняется точно n  сравнений. Ожидаемое число обменов есть  среднее этих  ожидаемых значений  для всех  возможных границ x.

             M = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n 

                  = [Su:0 <= u <= n-1: u*(n-u)]/n2

                  = n*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6      (2.20.)

В том  случае, если  бы  нам  всегда  удавалось  выбирать  в  качестве границы  медиану, то  каждый  процесс  разделения  расщеплял  бы  массив  на  две  половинки, и  для  сортировки  требовалось  бы  всего  n*log n подходов. В результате  общее число сравнений было  бы  равно n*log n, а общее число обменов – n*log(n) /6. Но  вероятность этого составляет  только  1/n.

Главный  из  недостатков  Quicksort – недостаточно  высокая производительность  при небольших n, впрочем этим  грешат  все усовершенствованные методы, одним из  достоинств  является  то, что для обработки небольших частей  в него  можно легко включить  какой-либо  из прямых  методов сортировки.

Тесты.

1. Идея сортировки массива прямым включением заключается в том, что
1. в сортируемой последовательности masi длиной n (i = 0..n - 1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.
2. в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со первого (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.
3. в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в не отсортированной левой части последовательности.
4. в сортируемой последовательности masi длиной n-1 (i=0..n-1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.
2. При сортировке массива прямым включением поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:
1. найден элемент последовательности mas, для которого masi>x; достигнут левый конец отсортированной слева последовательности.
2. найден элемент последовательности mas, для которого masi<x; достигнут левый конец отсортированной слева последовательности.
3. найден элемент последовательности mas, для которого masi<x; достигнут правый конец отсортированной слева последовательности.
4. найден элемент последовательности mas, для которого masi<x; достигнут левый конец не отсортированной слева последовательности.
3. При сортировке массива прямым включением для отслеживания условия окончания просмотра влево отсортированной последовательности используется прием «барьера». Суть его в том, что
1. к исходной последовательности справа добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
2. к исходной последовательности слева добавляется фиктивный элемент X. В конце каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
3. к исходной последовательности слева добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого не будет осуществляться поиск места вставки.
4. к исходной последовательности слева добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
4. Сортировка массива прямым включением требует в среднем
1. N^2/2 перемещений.
2. N^2/4 перемещений.
3. N^2 перемещений.
4. N/4 перемещений.
5. Выберите правильный вариант для вставки вместо знака «вопрос» во фрагмент кода сортировки массива прямым включением:

      For i:=2 to Сount do

          Begin

            Tmp:=Arr[i];

            j:=i-1;

            ?

              Begin

                Arr[j+1]:=Arr[j];

                j:=j-1;

              End;

            Arr[j+1]:=Tmp;

          End;

1. While (j<0) and (Arr[j]<Tmp) do
2. While (j>0) and (Arr[j]>Tmp) do
3. While (j>0) and (Arr[j]<Tmp) do
4. While (j=0) and (Arr[j]=Tmp) do
6. Алгоритм сортировки массива бинарными включениями
1. вставляет i-й элемент в готовую последовательность, которая пока не отсортирована, для нахождения места для i-го элемента используется метод бинарного поиска элемента.
2. вставляет i-й элемент в готовую последовательность, которая уже отсортирована,  для нахождения места для i-го элемента используется метод  бинарного  поиска  элемента.
3. вставляет i-й элемент в готовую последовательность, которая уже отсортирована, для нахождения места для i-го элемента используется метод Шелла поиска элемента.
4. вставляет i-й элемент в пока готовую последовательность, которая пока не отсортирована, для нахождения места для i-го элемента используется метод Шелла поиска элемента.
7. При сортировке массива бинарными включениями всего будет произведено
1. N×log₂N сравнений.
2. ×log₂N сравнений.
3. log₂(N/2) сравнений.
4. N/2*log₂N сравнений.
8. Изменится ли количество пересылок в сортировке массива бинарными включениями по отношению к количеству сравнений
1. станет больше
2. станет меньше
3. не изменится.
9. При сортировке массива методом бинарного включения внутренний цикл поиска с одновременным сдвигом следует разделить:
1. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются вправо.
2. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются влево.
3. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются вправо.
4. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются влево.
10. В чем состоит идея сортировки массива методом Шелла?
1. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии большем h.
2. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии меньшем h.
3. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h.
4. сортировке подвергаются не все подряд элементы последовательности, а только h элементов.
11. При сортировке массива методом Шелла на каждом шаге значение h изменяется, пока не станет (обязательно) равно
1. 3
2. 2
3. 0
4. 1.
12. Если h=1, то алгоритм сортировки массива методом Шелла вырождается в
1. пирамидальную сортировку.
2. сортировку прямыми включениями.
3. сортировку слиянием.
4. сортировку бинарного включения.
13. При сортировке массива методом Шелла расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что
1. последний шаг должен равняться единице.
2. последний шаг должен равняться нулю.
3. первый элемент равен последнему элементу.
4. первый элемент равен предпоследнему элементу.
14. Эффективность сортировки массива методом Шелла объясняется тем, что
1. при каждом проходе используется очень большое число элементов, упорядоченность увеличивается при каждом новом просмотре данных.
2. при каждом проходе элементы массива не упорядочены, а упорядоченность увеличивается при каждом новом просмотре данных.
3. при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
4. при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
15. Идея алгоритма сортировки массива прямым выбором заключается в том, что
1. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной максимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
2. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он не найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
3. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего правого элемента несортированной левой части массива.
4. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
16. Если сортировку выбором применить для массива "bdac", то будут получены следующие проходы
1. первый проход: c d b a; второй проход: a b b c; третий проход: a b c d.
2. первый проход: a d b c; второй проход: a b d c; третий проход: a b c d.
3. первый проход: a d b c; второй проход: a c d b; третий проход: a b c d.
4. первый проход: a d b c; второй проход: a b d c; третий проход: d b c a.
17. Как и в сортировке массива  пузырьковым методом в сортировке массива прямым выбором внешний цикл
1. выполняется n раз, а внутренний цикл выполняется n/2 раз.
2. выполняется n-1 раз,  а внутренний цикл выполняется n раз.
3. выполняется n-1 раз,  а внутренний цикл выполняется n/2 раз.
4. выполняется n раз, а внутренний цикл выполняется n раз.
18. Вставить во фрагмент кода сортировки массива прямым выбором, вместо знака «вопроса», верное неравенство: