Difference between revisions of "Counting sort"
From Free Pascal wiki
Jump to navigationJump to search (Created page with "The counting sort is an integer sorting algorithm. == unit UCountingSortExtra.pas == <syntaxhighlight> unit UCountingSortExtra; interface type // data type TItemCou...") |
|||
(7 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | + | {{Counting_sort}} | |
+ | The counting sort is an [[Integer|integer]] [[sorting algorithm]]. | ||
+ | |||
+ | == Features == | ||
+ | |||
+ | * Very fast | ||
+ | * Only small integers | ||
== unit UCountingSortExtra.pas == | == unit UCountingSortExtra.pas == | ||
− | <syntaxhighlight> | + | <syntaxhighlight lang="pascal"> |
− | |||
unit UCountingSortExtra; | unit UCountingSortExtra; | ||
− | |||
interface | interface | ||
Line 26: | Line 30: | ||
end; | end; | ||
− | end. | + | end. |
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Line 33: | Line 36: | ||
== unit UCountingSort.pas == | == unit UCountingSort.pas == | ||
− | <syntaxhighlight> | + | <syntaxhighlight lang="pascal"> |
− | |||
unit UCountingSort; | unit UCountingSort; | ||
− | |||
interface | interface | ||
Line 62: | Line 63: | ||
if a[ i ] > max then max := a[ i ]; | if a[ i ] > max then max := a[ i ]; | ||
end; | end; | ||
− | SetLength( count_a, max - min ); | + | SetLength( count_a, max - min + 1); |
for i := 0 to ( max - min ) do count_a[ i ] := 0; | for i := 0 to ( max - min ) do count_a[ i ] := 0; | ||
for i := low( a ) to high( a ) do | for i := low( a ) to high( a ) do | ||
Line 75: | Line 76: | ||
end; | end; | ||
− | end. | + | end. |
</syntaxhighlight> | </syntaxhighlight> | ||
Line 81: | Line 82: | ||
== Example of the use == | == Example of the use == | ||
− | <syntaxhighlight> | + | <syntaxhighlight lang="pascal"> |
uses | uses | ||
Line 90: | Line 91: | ||
var | var | ||
− | a: array[0..100] of integer; | + | a: array[0..100] of integer; |
Line 100: | Line 101: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− |
Latest revision as of 20:29, 7 July 2019
│
English (en) │
français (fr) │
The counting sort is an integer sorting algorithm.
Features
- Very fast
- Only small integers
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.
Example of the use
uses
UCountingSort
...
var
a: array[0..100] of integer;
begin
...
CountingSort( a );