Counting sort/fr

From Lazarus 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) français (fr)

Le tri par comptage est algorithme de tri sur les entiers.

Propriété

  • Très rapide
  • Seulement avec de petits entiers

unité UCountingSortExtra.pas

unit UCountingSortExtra;


interface

type
  // data type
  TItemCountingSort=integer;

// sort order
function IsAscendingCountingSort: boolean; inline;

implementation

// sort order
function IsAscendingCountingSort: boolean; inline;
begin
   result := true;
end;

end.


unité UCountingSort.pas

unit UCountingSort;


interface

uses
  UCountingSortExtra;

// sorting function
procedure CountingSort( var a: array of TItemCountingSort );

implementation


procedure CountingSort( var a: array of TItemCountingSort );
var
  min, max : TItemCountingSort;
  count_a  : array of integer;
  i, j, z  : integer;
begin
  min := high( a );
  max := min;
  for i := low( a ) to high( a ) do
    begin
      if a[ i ] < min then min := a[ i ];
      if a[ i ] > max then max := a[ i ];
    end;
  SetLength( count_a, max - min + 1);
  for i := 0 to ( max - min ) do count_a[ i ] := 0;
  for i := low( a ) to high( a ) do
    count_a[ a[ i ] - min ] := count_a[ a[ i ] - min ] + 1;
  if IsAscendingCountingSort then z:= low( a ) else z := high( a );
  for i := min to max do
     for j := 0 to ( count_a[ i - min ] - 1 ) do
       begin
         a[ z ] := i;
         if IsAscendingCountingSort then inc( z ) else dec( z );
       end;
end;

end.

Exemple d'emploi

uses
  UCountingSort

  ...

var

  a: array[0..100] of integer; 


begin

  ...

  CountingSort( a );