Difference between revisions of "Shell sort"

From Lazarus wiki
(Creating first version)
 
(Fixing typo)
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
The shell sort algorithm (aka shellsort or Shell's sort) is an [[Integer|integer]] [[sorting algorithm]].  
+
{{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. Shell in 1959.
  
 
== Features ==
 
== Features ==
Line 77: Line 79:
  
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
== 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].

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