Difference between revisions of "Shell sort"
From Lazarus wiki
Jump to navigationJump to searchJwdietrich (talk | contribs) |
Jwdietrich (talk | contribs) (Adding more information) |
||
Line 1: | Line 1: | ||
{{Shellsort}} | {{Shellsort}} | ||
− | The shell sort algorithm (aka shellsort or Shell's sort) is an [[Integer|integer]] [[sorting algorithm]]. | + | 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. |
== Features == | == Features == | ||
Line 79: | Line 79: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | == References == | ||
+ | * 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]. |
Revision as of 23:09, 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.
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
- Karen Van Houten, Shell Sort, University of Idaho. Archived at Wayback Machine.