Radix sort/fr
From Free Pascal wiki
Jump to navigationJump to searchThe printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
│
English (en) │
suomi (fi) │
français (fr) │
Le tri par radical est un algorithme de tri d'entier.
Propriétés
- Très rapide
Unité URadixSort.pas
unit URadixSort;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils,
GQueue ; // packages/fcl-stl/src/gqueue.pp
type
// data type
TItemRadixSort=integer;
// sorting function
procedure RadixSort( var a: array of TItemRadixSort );
implementation
procedure RadixSort( var a: array of TItemRadixSort );
const
BASE = 16;
type TQueueIRS = specialize TQueue< TItemRadixSort >;
var
jono : array[ 0 .. BASE - 1 ] of TQueueIRS;
max : TItemRadixSort;
i ,k : integer;
procedure pick;
var
i, j: integer;
begin
i := 0;
j := 0;
while i < high( a ) do
begin
while not jono[ j ].IsEmpty do
begin
a[ i ] := jono[ j ].Front;
jono[ j ].Pop;
inc( i );
end;
inc( j );
end;
end;
begin
max := high( a );
for i := 0 to BASE - 1 do
jono[ i ] := TQueueIRS.Create;
for i := low( a ) to high( a ) do
begin
if a[ i ] > max then max := a[ i ];
jono[ abs( a[ i ] mod BASE ) ].Push( a[ i ] );
end;
pick;
k := BASE;
while max > k do
begin
for i := low( a ) to high( a ) do
jono[ abs( a[ i ] div k mod BASE ) ].Push( a[ i ] );
pick;
k := k * BASE;
end;
for i := 0 to BASE - 1 do
jono[ i ].Free;
end;
end.
Exemple d'utilisation
uses
URadixSort
...
var
a: array[0..100] of integer;
begin
...
RadixSort( a );