Shell sort: what changed

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

Title: Shell sort

New		Line
1	+	The Shell sort algorithm (aka shellsort or Shell's sort) is an [[Integer\|integer]] [[sorting algorithm]]. It is a fast sorting algorithm (although slower than quicksort) that has the advantage that it is non-recursive, so it doesn't use the call stack. Therefore the method is advantageous on small and embedded systems and for sorting very large arrays. The algorithm was published in assembler code by Donald L. Shell in 1959.
2	+
3	+	## Features
4	+
5	+	- Very fast
6	+	- Doesn't need the call stack
7	+
8	+	## unit UShellSort.pas
9	+
10	+	``` pascal
11	+
12	+	unit UShellSort;
13	+
14	+	{$mode objfpc}{$H+}
15	+
16	+	interface
17	+
18	+	uses
19	+	Classes, SysUtils;
20	+
21	+	type
22	+	TShellSortItem = integer;
23	+
24	+	procedure ShellSort(var a: array of TShellSortItem);
25	+
26	+	implementation
27	+
28	+	procedure ShellSort(var a: array of TShellSortItem);
29	+	var i, j, h, n, v : integer;
30	+	begin
31	+	n := length(a);
32	+	h := 1;
33	+	repeat
34	+	h := 3*h + 1
35	+	until h > n;
36	+	repeat
37	+	h := h div 3;
38	+	for i := h to n-1 do
39	+	begin
40	+	v := a[i];
41	+	j := i;
42	+	while (j >= h) AND (a[j-h] > v) do
43	+	begin
44	+	a[j] := a[j-h];
45	+	j := j - h;
46	+	end;
47	+	a[j] := v;
48	+	end
49	+	until h = 1;
50	+	end;
51	+
52	+	end.
53	+	```
54	+
55	+	## Example of the use
56	+
57	+	``` pascal
58	+
59	+	uses
60	+	UShellSort
61	+
62	+	...
63	+
64	+	var
65	+
66	+	a: array[0..100] of integer;
67	+
68	+	begin
69	+
70	+	...
71	+
72	+	ShellSort(a);
73	+	```
74	+
75	+	## References
76	+
77	+	- Shell, D. L. (1959). [A High-Speed Sorting Procedure](http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf) (PDF). Communications of the ACM. 2 (7): 30–32. [doi: 10.1145/368370.368387](https://doi.org/10.1145%2F368370.368387).
78	+	- Karen Van Houten, Shell Sort, University of Idaho. Archived at [Wayback Machine](https://web.archive.org/web/20060914153030/http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/shell.sort.html).
79	+
80	+	---
81	+	From the Free Pascal wiki, page "Shell sort", as it stood on 2024-01-24 after a change by Kjteng, 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