Алгоритм 8. Цифровая сортировка.
Falk0ner, вс, 06/07/2008 - 15:35.
Алгоритм 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.
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. Все программы рабочие — если, конечно, вам не лень будет заменить три точки на код ввода и вывода массивов :-).
Отправить комментарий