Difference between revisions of "Shell sort"
From Free Pascal wiki
Jump to navigationJump to searchJwdietrich (talk | contribs) (More information) |
Jwdietrich (talk | contribs) (Typo) |
||
Line 1: | Line 1: | ||
{{Shellsort}} | {{Shellsort}} | ||
− | 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. | + | 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 == |
Revision as of 23:18, 28 January 2021
│
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 + 1 to n 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.