Difference between revisions of "Shell sort"
From Free Pascal wiki
Jump to navigationJump to searchJwdietrich (talk | contribs) (Adding more information) |
|||
(5 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
{{Shellsort}} | {{Shellsort}} | ||
− | The | + | 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. |
== Features == | == Features == | ||
Line 38: | Line 38: | ||
repeat | repeat | ||
h := h div 3; | h := h div 3; | ||
− | for i := h | + | for i := h to n-1 do |
begin | begin | ||
v := a[i]; | v := a[i]; | ||
j := i; | j := i; | ||
− | while (j > h) AND (a[j-h] > v) do | + | while (j >= h) AND (a[j-h] > v) do |
begin | begin | ||
a[j] := a[j-h]; | a[j] := a[j-h]; | ||
Line 55: | Line 55: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
== Example of the use == | == Example of the use == | ||
Line 81: | Line 79: | ||
== References == | == References == | ||
+ | * Shell, D. L. (1959). [http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf A High-Speed Sorting Procedure] (PDF). Communications of the ACM. 2 (7): 30–32. [https://doi.org/10.1145%2F368370.368387 doi: 10.1145/368370.368387]. | ||
* Karen Van Houten, Shell Sort, University of Idaho. Archived at [https://web.archive.org/web/20060914153030/http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/shell.sort.html Wayback Machine]. | * Karen Van Houten, Shell Sort, University of Idaho. Archived at [https://web.archive.org/web/20060914153030/http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/shell.sort.html Wayback Machine]. |
Latest revision as of 11:57, 24 January 2024
│
English (en) │
The Shell sort algorithm (aka shellsort or Shell's sort) is an 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.
Features
- Very fast
- Doesn't need the call stack
unit UShellSort.pas
unit UShellSort;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils;
type
TShellSortItem = integer;
procedure ShellSort(var a: array of TShellSortItem);
implementation
procedure ShellSort(var a: array of TShellSortItem);
var i, j, h, n, v : integer;
begin
n := length(a);
h := 1;
repeat
h := 3*h + 1
until h > n;
repeat
h := h div 3;
for i := h to n-1 do
begin
v := a[i];
j := i;
while (j >= h) AND (a[j-h] > v) do
begin
a[j] := a[j-h];
j := j - h;
end;
a[j] := v;
end
until h = 1;
end;
end.
Example of the use
uses
UShellSort
...
var
a: array[0..100] of integer;
begin
...
ShellSort(a);
References
- Shell, D. L. (1959). A High-Speed Sorting Procedure (PDF). Communications of the ACM. 2 (7): 30–32. doi: 10.1145/368370.368387.
- Karen Van Houten, Shell Sort, University of Idaho. Archived at Wayback Machine.