Radix sort/fr

From Free Pascal wiki
Jump to navigationJump to search
The 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 );