16. Сортировка обменами. Пузырьковая сортировка. Быстрая сортировка. Временная сложность алгоритмов.

 

Сортировка обменами выполняется за несколько просмотров. Каждый раз, когда находятся два элемента a[i] и a[j], такие, что i<j и при этом a[i].key>a[j].key, эти элементы меняются местами. Простейший вид такой сортировки получил название пузырьковая сортировка (BubbleSort). Такое название происходит от образной интерпретации, по которой алгоритм заставляет “легкие” элементы мало-помалу “всплывать” на поверхность.

                        ...

            while l do

             begin

                        l:=false;

                        for i:=1 to n-1 do

                         begin

                                   if a[i].key>a[i+1].key then

                                    begin l:=true; buf:=a[i]; a[i]:=a[i+1]; a[i+1]:=buf end

                         end

             end;

                        ...

            Максимальная сложность пузырьковой сортировки составляет T(n)=O(n^2). Это, пожалуй, наихудший из известных методов сортировки. Как известно, человеческая натура противоречива и, наверное, именно поэтому пузырьковую сортировку программисты используют наиболее часто!

 

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

            Быстрая сортировка является блестящим примером систематического применения принципов разделяй и властвуй и балансировка к сортировке обменами.

            На первом этапе быстрой сортировки упорядочиваемый массив реорганизуется. Для этого в массиве выбирается главный элемент a[p]. Затем все элементы с ключами, меньшими a[p].key, размещаются слева от главного элемента, а элементы с ключами, большими либо равными a[p].key, размещаются справа от него.

            Затем для полной сортировки массива достаточно (второй этап):

            а) больше не трогать главный элемент, который находится на своем месте;

            б) рекурсивно отсортировать подмассив A[1,p-1];

            в) рекурсивно отсортировать подмассив A[p+1,n].

            Реализуя второй этап, на практике обычно не устанавливают на свое место главный элемент, а просто включают его в один из подмассивов, например:

            а) рекурсивно отсортировать подмассив A[1,p];

            б) рекурсивно отсортировать подмассив A[p+1,n].

           

            Алгорит Хоара имеет среднюю сложность O(n logn), тогда как максимальная сложность остается O(n2).

            Остановимся подробнее на важных деталях первого этапа.

 

Выбор главного элемента

            Это очень важный момент в алгоритме быстрой сортировки. Именно неудачный выбор на каждом шаге главного элемента обуславливает плохой показатель максимальной сложности. Пусть на некотором шаге на вход процедуры быстрой сортировки QuickSort поступили элементы массива с индексами от first до last. Тогда лучший способ выбрать главный элемент заключается в использовании генератора случайных чисел для порождения целого числа p, first<=p<=last. Это число и определяет индекс главного элемента.

 

Реорганизация массива относительно главного элемента

            Двигаясь от элемента с индексом first вправо, находят элемент с индексом f, ключ которого не меньше ключа главного элемента. Двигаясь от элемента с индексом last влево, находят элемент с индексом l, ключ которого не больше ключа главного элемента. Если оказалось, что элемент с индексом f расположен левее элемента с индексом l, то их меняют местами. Дальше движение влево продолжают с позиции f+1, движение вправо - с позиции l-1 до тех пор, пока не произойдет встреча.

            Пример. Произвести разбивку массива 26, 49, 34, 1, 12, 37, 1, 38, 23 на два подмассива, приняв в качестве главного элемента a=23.

            Решение.

Шаг 1. f=1, a[f]=26, l=9, a[l]=23;     новый массив: 23, 49, 34, 1, 12, 37, 1, 38, 26.

Шаг 2. f=2, a[f]=49, l=7, a[l]=1;       новый массив: 23, 1, 34, 1, 12, 37, 49, 38, 26.

Шаг 3. f=3, a[f]=34, l=5, a[l]=12;     новый массив: 23, 1, 12, 1, 34, 37, 49, 38, 26.

Шаг 4. f=5, l=4; так как f>l, процесс завершен. Первый подмассив с индексами 1..l: 23, 1, 12, 1. Второй подмассив с индексами f..n: 34, 37, 49, 38, 26.

 

            Парадокс быстрой сортировки заключается в том, что в противоположность сортировке включением и даже пузырьковой сортировке она теряет свои качества на частично упорядоченных массивах.

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

if last-first>порог then быстрая сортировка(...) else сортировка включением(...);.

Значение порога определяется характеристиками конкретной ЭВМ.

            Быстрая сортировка рекомендуется для упорядочения последовательностей с размерностью от 100 и более элементов.

            На рис. 3.5 представлена процедура, реализующая алгоритм быстрой сортировки.

 

procedure QuickSort(first,last: integer);

 var f,l,y,m,i:integer; buf:node;

 begin

    f:=first; l:=last; m:=first+Random(last-first); y:=a[m].key;

    repeat

      while a[f].key < y do Inc(f); while a[l].key > y do Dec(l);

      if f<=l then begin buf :=a[f]; a[f]:=a[l]; a[l]:= buf; Inc(f); Dec(l) end;

    until f>l;

    if l>first then QuickSort(first,l); if f<last  then QuickSort(f,last)

 end;

            Рис. 3.5.