Алгоритм 7. Сортировка подсчетом.

Previous  Top  Next

    
 

Алгоритм 7. Сортировка подсчетом.

 

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

Code:

Program CountingSort;

Var A,B   : array[1..1000] of byte;

   C     : array[byte] of integer;

   N,i    : integer;

Begin

{Определение размера массива A (N) и его заполнение}

{сортировка данных}

for i:=0 to 255 do

C[i]:=0;

for i:=1 to N do

C[A[i]]:=C[A[i]]+1;

for i:=1 to 255 do

C[i]:=C[i-1]+C[i];

for i:=N downto 1 do

begin

B[C[A[i]]]:=A[i];

C[A[i]]:=C[A[i]]-1; {здесь мы избегаем возможности записи двух одинаковых чисел в одну ячейку}

end;

{Вывод массива B}

End.

 

 

 

Этот простой метод не использует вложенных циклов и, учитывая небольшой диапазон значений, время его работы есть O(n).

 

Рассмотрев такое количество сортировок, можно задуматься: а будет ли результат их работы одинаковым? Странный вопрос, ведь все сортировки правильно сортируют данные, так почему же результат работы может быть разным? Хорошо, объясню: меньшие элементы всегда расположены перед большими, но порядок одинаковых элементов может быть нарушен. Если мы сортируем данные, которые состоят из одного ключа, то мы, конечно, не заметим разницы. Но если к ключу прилагается дополнительная информация, то одна сортировка может вернуть нам 1977 "Иванов" и 1977 "Сидоров", а другая 1977 "Сидоров" и 1977 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.

©Drkb::04149