# Difference between revisions of "Shell sort"

From Lazarus wiki

Jwdietrich (talk | contribs) (More information) |
Jwdietrich (talk | contribs) (Fixing typo) |
||

(One intermediate revision by the same user 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 == |

## Latest revision as of 18:16, 30 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.