12. Цифровая ср (ср "вычерпыванием"). Сортировка записей методом MathSort. Временная сложность алгоритмов.

 

Это единственный вид сортировки, при котором не требуется сравнивать сортируемые элементы. Начнем рассмотрение сортировки распределением с ее простейшей разновидности - цифровой сортировки (сортировки вычерпыванием).

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

.

Если m не слишком велико (m=O(n)), то массив А можно упорядочить следующим образом:

            1. Организовать m пустых  очередей по одной для каждого натурального числа от 1 до m. Каждую такую очередь называют черпаком.

            2. Просмотреть последовательность А слева направо, помещая элемент  ai в очередь с номером ai.

                3. Сцепить эти очереди, т.е. содержимое (i+1)-й очереди приписать к концу i-й очереди (i=1,2,... m-1), получив тем самым упорядоченную последовательность.

            Так как каждый элемент можно вставить в i-ю очередь за постоянное время, то n элементов можно вставить в очереди за время O(n). Конкатенация (сцепление) m очередей требует времени O(m). Если m=O(n), то этот алгоритм сортирует n натуральных чисел за время T(n)=O(n).

            Можно существенно облегчить реализацию этого алгоритма, если вместо m очередей организовать m счетчиков: count[1..m]. Первоначально значение каждого счетчика равно 0. Тогда при просмотре последовательности А вместо добавления элемента ai в очередь с номером ai  надо просто увеличить count[ai] на единицу, а вместо сцепления очередей распечатать элемент ai в точности count[ai] раз.

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

            Познакомимся с эффективной разновидностью сортировки распределением, называемой МАТСОРТ (MathSort). Пусть, по-прежнему, ключи представляют собой натуральные числа и известно, что максимальный ключ не превосходит некоторое натуральное m:

,

причем m и n одного порядка.

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

            1. Организовать m счетчиков: count[1..m]. Первоначально значение каждого счетчика равно 0.

            2. При первом просмотре массива А каждая запись находит “свой” счетчик и он увеличивается:                                               i:=a[j].key; count[i]:=count[i]+1;.

            3. Накапливаем сумму, чтобы найти будущие границы count[i] групп записей с одинаковым значением ключа:     for i:=2 to m do count[i]:=count[i]+count[i-1];.

Если в массиве несколько записей имеют ключ i, то значение count[i] теперь определяет позицию последней такой записи.

            4. При втором просмотре массива А каждая j-я запись находит “свой” элемент count[i] - теперь по нему определяется ее новая позиция: k:=c[i]. Однако эта позиция занята другой записью, если только k и j не оказались равны. k-я и j-я записи меняются местами, а счетчик

 count[i] уменьшается на единицу. Обмены записей повторяются до тех пор, пока в j-й позиции не окажется запись, для которой k=j.  Следует отметить, что используются лишь те значения k, которые больше j.

            Рассмотренный процесс может не охватить все записи и тогда он повторяется, начиная с новой j-й записи.

            Если k-я и j-я записи имеют одинаковый ключ, то k-ю запись оставляют на месте и переходят к соседней позиции k:=k-1, выполняя далее те же действия, пока не будет найдена запись с иным ключом. Поиск идет вплоть до j-й позиции. Если запись с другим ключом не найдена, то положение всех записей группы остается неизменным.

            Изменяя номер позиции j, рано или поздно приходим к позиции, куда запись поставлена окончательно. Эти позиции пропускаются без обработки (формальный признак: k<=j).

            Оценка сложности для алгоритма МАТСОРТ сохраняется та же, что и для цифровой сортировки.

            На рис. 3.1 представлена процедура, реализующая метод МАТСОРТ.

 

Procedure Mathsort;

 var i,j,m,k:integer; buf:node; count:array[1..m0] of 0..n0;

 begin

  for i:=1 to m0 do count[i]:=0;

  for j:=1 to n do begin i:= a[j].key; count[i]:=count[i]+1 end;

  for i:=2 to m0 do count[i]:= count[i] + count[i-1];

  for j:= 1 to n do

     begin

         i:=a[j].key; k:= count[i];

         while k>j do 

         begin

             repeat m:=A[k].key; k:= k-1 until (m<>i) or (k=j);

             count[i]:=k;          

             if m<>i then

                begin buf:=a[j]; a[j]:=a[k+1]; a[k+1]:= buf; i:=m; k:=count[i] end

         end

     end

 end; {MathSort}                               Рис. 3.1.