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
edit- Very fast
- Doesn't need the call stack
unit UShellSort.pas
editunit 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
edituses
UShellSort
...
var
a: array[0..100] of integer;
begin
...
ShellSort(a);
References
edit- 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.