Delphi-Help

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

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

Оцените материал
(1 Голосовать)


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

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

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.  
 
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 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.

Прочитано 11072 раз

Авторизация



Счетчики