Radix sort/fi: what changed

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

Title: Radix sort/fi

New		Line
1	+	Radix sort on [[Integer/fi\|kokonaisluku]] [[sorting algorithm/fi\|lajittelu algoritmi]].
2	+
3	+	## Ominaisuudet
4	+
5	+	- Hyvin nopea
6	+
7	+	## unit URadixSort.pas
8	+
9	+	``` pascal
10	+
11	+	unit URadixSort;
12	+
13	+	{$mode objfpc}{$H+}
14	+
15	+	interface
16	+
17	+	uses
18	+	Classes, SysUtils,
19	+	GQueue ; // packages/fcl-stl/src/gqueue.pp
20	+
21	+	type
22	+	// data type
23	+	TItemRadixSort=integer;
24	+
25	+	// sorting function
26	+	procedure RadixSort( var a: array of TItemRadixSort );
27	+
28	+	implementation
29	+
30	+	procedure RadixSort( var a: array of TItemRadixSort );
31	+
32	+	const
33	+	BASE = 16;
34	+
35	+	type TQueueIRS = specialize TQueue< TItemRadixSort >;
36	+
37	+	var
38	+	jono : array[ 0 .. BASE - 1 ] of TQueueIRS;
39	+	max : TItemRadixSort;
40	+	i ,k : integer;
41	+
42	+	procedure pick;
43	+	var
44	+	i, j: integer;
45	+	begin
46	+	i := 0;
47	+	j := 0;
48	+	while i < high( a ) do
49	+	begin
50	+	while not jono[ j ].IsEmpty do
51	+	begin
52	+	a[ i ] := jono[ j ].Front;
53	+	jono[ j ].Pop;
54	+	inc( i );
55	+	end;
56	+	inc( j );
57	+	end;
58	+	end;
59	+
60	+	begin
61	+	max := high( a );
62	+	for i := 0 to BASE - 1 do
63	+	jono[ i ] := TQueueIRS.Create;
64	+	for i := low( a ) to high( a ) do
65	+	begin
66	+	if a[ i ] > max then max := a[ i ];
67	+	jono[ abs( a[ i ] mod BASE ) ].Push( a[ i ] );
68	+	end;
69	+	pick;
70	+	k := BASE;
71	+	while max > k do
72	+	begin
73	+	for i := low( a ) to high( a ) do
74	+	jono[ abs( a[ i ] div k mod BASE ) ].Push( a[ i ] );
75	+	pick;
76	+	k := k * BASE;
77	+	end;
78	+	for i := 0 to BASE - 1 do
79	+	jono[ i ].Free;
80	+
81	+	end;
82	+
83	+	end.
84	+	```
85	+
86	+	## Käyttö esimerkki
87	+
88	+	``` pascal
89	+
90	+	uses
91	+	URadixSort
92	+
93	+	...
94	+
95	+	var
96	+
97	+	a: array[0..100] of integer;
98	+
99	+	begin
100	+
101	+	...
102	+
103	+	RadixSort( a );
104	+	```
105	+
106	+	---
107	+	From the Free Pascal wiki, page "Radix sort/fi", as it stood on 2019-07-08 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