Counting sort/fr

From Free Pascal wiki
Jump to: navigation, search

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 );