Главная Статьи Сортировка Алгоритм 8. Цифровая сортировка

Алгоритм 8. Цифровая сортировка

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

Алгоритм 8. Цифровая сортировка

Этой сортировкой можно сортировать целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы. Реализация такова:

Program RadixSort;   
Var A,B   : array[1..1000] of word;   
   N,i    : integer;   
   t      : longint;   
Procedure Sort; {сортировка подсчетом}  
Var C    : array[0..9] of integer;   
    j     : integer;   
Begin   
 For j:=0 to 9 do  
 C[j]:=0;   
 For j:=1 to N do  
 C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1;   
 For j:=1 to 9 do  
 C[j]:=C[j-1]+C[j];   
 For j:=N downto 1 do  
 begin  
  B[C[(A[j] mod (t*10)) div t]]:=A[j];   
  C[(A[j] mod (t*10)) div t] := C[(A[j] mod (t*10)) div t]-1;   
 end;   
End;   
Begin   
{Определение размера массива A (N) и его заполнение}  
    
{сортировка данных}  
 t:=1;   
 for i:=1 to 5 do  
 begin  
  Sort;   
  A:=B;   
  t:= t*10;   
 end;   
{Вывод массива A}  
    
End.  
 
Program RadixSort;
Var A,B   : array[1..1000] of word;
   N,i    : integer;
   t      : longint;
Procedure Sort; {сортировка подсчетом}
Var C    : array[0..9] of integer;
    j     : integer;
Begin
 For j:=0 to 9 do
 C[j]:=0;
 For j:=1 to N do
 C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1;
 For j:=1 to 9 do
 C[j]:=C[j-1]+C[j];
 For j:=N downto 1 do
 begin
  B[C[(A[j] mod (t*10)) div t]]:=A[j];
  C[(A[j] mod (t*10)) div t] := C[(A[j] mod (t*10)) div t]-1;
 end;
End;
Begin
{Определение размера массива A (N) и его заполнение}
 
{сортировка данных}
 t:=1;
 for i:=1 to 5 do
 begin
  Sort;
  A:=B;
  t:= t*10;
 end;
{Вывод массива A}
End.

Так как сортировка подсчетом вызывается константное число раз, то время работы всей сортировки есть O(n). Заметим, что таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям.

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

P.S. Все программы рабочие — если, конечно, вам не лень будет заменить три точки на код ввода и вывода массивов :-).

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

Авторизация



Счетчики