Difference between revisions of "Shell sort"

From Lazarus wiki
Jump to navigationJump to search
(Creating first version)
 
Line 1: Line 1:
 +
{{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]].  
  

Revision as of 22:01, 28 January 2021

English (en)

The shell sort algorithm (aka shellsort or Shell's sort) is an integer sorting algorithm.

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);