Counting sort: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Counting sort

New		Line
1	+	The counting sort is an [[Integer\|integer]] [[sorting algorithm]].
2	+
3	+	## Features
4	+
5	+	- Very fast
6	+	- Only small integers
7	+
8	+	## unit UCountingSortExtra.pas
9	+
10	+	``` pascal
11	+	unit UCountingSortExtra;
12	+
13	+	interface
14	+
15	+	type
16	+	// data type
17	+	TItemCountingSort=integer;
18	+
19	+	// sort order
20	+	function IsAscendingCountingSort: boolean; inline;
21	+
22	+	implementation
23	+
24	+	// sort order
25	+	function IsAscendingCountingSort: boolean; inline;
26	+	begin
27	+	result := true;
28	+	end;
29	+
30	+	end.
31	+	```
32	+
33	+	## unit UCountingSort.pas
34	+
35	+	``` pascal
36	+	unit UCountingSort;
37	+
38	+	interface
39	+
40	+	uses
41	+	UCountingSortExtra;
42	+
43	+	// sorting function
44	+	procedure CountingSort( var a: array of TItemCountingSort );
45	+
46	+	implementation
47	+
48	+	procedure CountingSort( var a: array of TItemCountingSort );
49	+	var
50	+	min, max : TItemCountingSort;
51	+	count_a : array of integer;
52	+	i, j, z : integer;
53	+	begin
54	+	min := high( a );
55	+	max := min;
56	+	for i := low( a ) to high( a ) do
57	+	begin
58	+	if a[ i ] < min then min := a[ i ];
59	+	if a[ i ] > max then max := a[ i ];
60	+	end;
61	+	SetLength( count_a, max - min + 1);
62	+	for i := 0 to ( max - min ) do count_a[ i ] := 0;
63	+	for i := low( a ) to high( a ) do
64	+	count_a[ a[ i ] - min ] := count_a[ a[ i ] - min ] + 1;
65	+	if IsAscendingCountingSort then z:= low( a ) else z := high( a );
66	+	for i := min to max do
67	+	for j := 0 to ( count_a[ i - min ] - 1 ) do
68	+	begin
69	+	a[ z ] := i;
70	+	if IsAscendingCountingSort then inc( z ) else dec( z );
71	+	end;
72	+	end;
73	+
74	+	end.
75	+	```
76	+
77	+	## Example of the use
78	+
79	+	``` pascal
80	+
81	+	uses
82	+	UCountingSort
83	+
84	+	...
85	+
86	+	var
87	+
88	+	a: array[0..100] of integer;
89	+
90	+	begin
91	+
92	+	...
93	+
94	+	CountingSort( a );
95	+	```
96	+
97	+	---
98	+	From the Free Pascal wiki, page "Counting sort", as it stood on 2019-07-07 after a change by Djzepi, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).

Back to history