Sorting algorithms/Shell sort: Difference between revisions

{{trans|Python}}

 

V inc = seq.len I/ 2

L inc != 0

V data = [22, 7, 2, -5, 8, 4]

shell_sort(&data)

 

{{out}}

{{trans|PL/I}}

The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible.

SHELLSRT CSECT

USING SHELLSRT,R13 base register

RK EQU 8 incr

RT EQU 9 temp

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program shellSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|Action!}}==

INT i

 

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Shell_sort.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

var inc:uint = data.length/2;

return data;

}

 

=={{header|Ada}}==

This is a generic implementation of the shell sort. Ada allows arrays to be indexed by integer or enumeration types starting at any value. This version deals with any kind or value of valid index type.

type Element_Type is digits <>;

type Index_Type is (<>);

package Shell_Sort is

procedure Sort(Item : in out Array_Type);

----------

end Sort;

 

 

=={{header|ALGOL 68}}==

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.8 algol68g-2.8].}}

 

COMMENT

shell sort in place(LOC[LWB seq: UPB seq]SORTELEMENT:=seq, sort cmp rev);

 

# -*- coding: utf-8 -*- #

 

 

[]SORTELEMENT char array data = "big fjords vex quick waltz nymph";

{{out}}

<pre>

=={{header|AppleScript}}==

 

-- Algorithm: Donald Shell, 1959.

on ShellSort(theList, l, r) -- Sort items l thru r of theList.

set aList to {56, 44, 72, 4, 93, 26, 61, 72, 52, 9, 87, 26, 73, 75, 94, 91, 30, 18, 63, 16}

sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.

 

{{output}}

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program shellSort.s */

bx lr @ leave function

iMagicNumber: .int 0xCCCCCCCD

 

=={{header|Arturo}}==

 

a: new items

h: size a

]

 

 

{{out}}

=={{header|ATS}}==

 

 

selected by templates. *)

 

print! (" ", arr[i]);

println! ()

 

{{out}}

===For arrays whose elements must be of non-linear type===

 

 

selected by templates. *)

print! (" ", arr[i]);

println! ()

 

{{out}}

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=131 discussion]

MsgBox % ShellSort("xxx")

MsgBox % ShellSort("3,2,1")

s .= "," . a%A_Index%

Return SubStr(s,2) ; drop leading comma

 

=={{header|AWK}}==

{{trans|Fortran}}

line[NR] = $0

}

print line[i]

}

 

=={{header|BBC BASIC}}==

Note that the array index is assumed to start at zero.

test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCshellsort(test(), 10)

NEXT

ENDWHILE

{{out}}

<pre>

 

=={{header|BCPL}}==

 

LET shellsort(v, upb) BE

{ //FOR i = 1 TO n-1 UNLESS v!i<=v!(i+1) RESULTIS FALSE

RESULTIS TRUE

 

=={{header|C}}==

 

void shell_sort (int *a, int n) {

return 0;

}

{{out}}

<pre>

 

=={{header|C sharp|C#}}==

public static class ShellSorter

{

}

}

{{out}}

<pre>

 

=={{header|C++}}==

#include <time.h>

#include <iostream>

}

//--------------------------------------------------------------------------------------------------

{{out}}

<pre>

Program will sort any array using standard EBCDIC sequence (won't work properly with signed packed variables). In addition to the "usual" array and array lenght parameters, you need to supply an area (initialized to low-values) to detail row-length and up to 10 sort keys defined as follows: start position (1 based), length and sequence (Ascending/Descending).

 

IDENTIFICATION DIVISION.

*******************************************************

IF KEY-RESULT = ' '

MOVE '=' TO KEY-RESULT

 

===Sorting Process===

This excerpt contains just enough of the procedure division to show the workings. See the example for the bubble sort for a more complete program.

C-000.

DISPLAY "SORT STARTING".

 

G-999.

 

=={{header|Common Lisp}}==

 

(let ((length (length array)))

(if (< length 2) array

"Last gap of ~w is not 1." gaps)

(dolist (gap gaps array)

 

=={{header|D}}==

 

void shellSort(T)(T[] seq) pure nothrow {

shellSort(data);

writeln(data);

{{out}}

<pre>[-5, 2, 4, 7, 8, 22]</pre>

=={{header|Dart}}==

 

void main() {

List<int> a = shellSort([1100, 2, 56, 200, -52, 3, 99, 33, 177, -199]);

return array;

}

 

{{out}}

 

=={{header|Delphi}}==

const

gaps:array[0..7] of Integer = (701, 301, 132, 57, 23, 10, 4, 1);

end;

end;

 

=={{header|E}}==

{{trans|Python}}

 

def shellSort(array) {

var inc := array.size() // 2

inc := if (inc <=> 2) { 1 } else { (inc * 5.0 / 11).floor() }

}

 

=={{header|Eiffel}}==

For a more complete explanation of the Eiffel sort examples, see [[Sorting algorithms/Bubble sort#Eiffel|Bubble sort]].

 

MY_SORTED_SET [G -> COMPARABLE]

inherit

end

 

 

=={{header|Elixir}}==

def shell_sort(list) when length(list)<=1, do: list

def shell_sort(list), do: shell_sort(list, div(length(list),2))

 

list = [0, 14, 11, 8, 13, 15, 5, 7, 16, 17, 1, 6, 12, 2, 10, 4, 19, 9, 18, 3]

 

{{out}}

 

=={{header|Euphoria}}==

integer gap,j

object temp

? s

puts(1,"After: ")

 

{{out}}

=={{header|Forth}}==

{{works with|GNU Forth}}

 

: shell { array len -- }

 

array 10 shell

 

A version without local variables:

 

: (shell) ( a n h -- a n h)

array 10 shell

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

CONTAINS

WRITE (*,*) array

 

=={{header|FreeBASIC}}==

modified bubble sort code

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted 1 -4 -1 7 -6 3 6 -7 -5 2 -2 0 5 4 -3

=={{header|Go}}==

Following WP pseudocode:

 

import "fmt"

}

fmt.Println("after: ", a)

{{out}}

<pre>

Adapted version from [http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Shell_sort#Haskell]

 

 

shellSort xs = foldr (invColumnize (map (foldr insert []))) xs gaps

where gaps = takeWhile (< length xs) $ iterate (succ.(3*)) 1

invColumnize f k = concat. transpose. f. transpose

 

=={{header|Haxe}}==

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(shellsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

}

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]]. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

=={{header|Io}}==

Translated from pseudocode at [[wp:Shell_sort#Shell_sort_algorithm_in_pseudocode|Wikipedia]]

shellSortInPlace := method(

gap := (size / 2) round

 

l := list(2, 3, 4, 5, 1)

 

=={{header|IS-BASIC}}==

110 RANDOMIZE

120 LET N=20 ! Number of elements

430 LET D=INT(D/2)

440 LOOP WHILE D>0

 

=={{header|J}}==

 

'''Solution'''

insert =: (I.~ {. ]) , [ , ] }.~ I.~

gapinss =: #@] {. ,@|:@(] insert//.~ #@] $ i.@[)

 

Example:

 

 

=={{header|Java}}==

 

This method will sort in place. If you want to preserve your unsorted array, use a copy of the array as an argument to this method.

int increment = a.length / 2;

while (increment > 0) {

}

}

 

=={{header|JavaScript}}==

for (var h = a.length; h > 0; h = parseInt(h / 2)) {

for (var i = h; i < a.length; i++) {

a.push(parseInt(Math.random() * 100));

shellSort(a);

 

=={{header|jq}}==

 

shellSort as defined here can be used to sort an array of arbitrary JSON entities.

 

# As soon as "condition" is true, then emit . and stop:

)

| [(($h+1)*5/11 | floor), .] )

'''Example''':

[5,null,3,1,2,0,4.4,5]

{{Out}}

[]

 

=={{header|Julia}}==

{{trans|Java}}

 

function shellsort!(a::Array{Int})::Array{Int}

x = rand(1:10, 10)

@show x shellsort!(x)

 

{{out}}

 

=={{header|Kotlin}}==

 

val gaps = listOf(701, 301, 132, 57, 23, 10, 4, 1) // Marcin Ciura's gap sequence

println(a.joinToString(", "))

}

 

{{out}}

 

=={{header|Liberty BASIC}}==

siz = 100

dim a(siz)

print a(i)

next

 

=={{header|Lisaac}}==

 

+ name := SHELL_SORT;

};

};

 

=={{header|Lua}}==

local inc = math.ceil( #a / 2 )

while inc > 0 do

for _, i in pairs(a) do

print(i)

 

=={{header|M2000 Interpreter}}==

A For statement can be as in this example or the faster For { } without Next

 

Module ShellSortExample {

Module shellsort(&a()) {

}

ShellSortExample

 

=={{header|Maple}}==

local n, gap, i, val, j;

n := numelems(arr):

arr := Array([17,3,72,0,36,2,3,8,40,0]);

shellsort(arr);

{{Out|Output}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

incr = Round[Length[list]/2];

While[incr > 0,

If[incr == 2, incr = 1, incr = Round[incr/2.2]]

]; list

 

<pre>shellSort[{2,1,4,6,8}]

=={{header|MATLAB}} / {{header|Octave}}==

This is a translation of the FORTRAN solution into MATLAB.

 

N = numel(list);

end

end %while

 

Sample Usage:

 

ans =

 

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

method isFalse public constant binary returns boolean

return \isTrue

{{out}}

<pre>

 

=={{header|Nim}}==

var h = a.len

while h > 0:

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

shellSort a

 

=={{header|Objeck}}==

{{trans|C sharp}}

bundle Default {

class ShellSort {

}

}

 

=={{header|OCaml}}==

{{trans|C}}

let len = Array.length a in

let incSequence = [| 412771; 165103; 66041; 26417; 10567;

done;

) incSequence;

and the main:

let arraysize = 1000 in (* or whatever *)

Random.self_init();

Array.iter (Printf.printf " %d") intArray;

print_newline();

 

=={{header|ooRexx}}==

{{Trans|NetRexx}}

-- --- Main --------------------------------------------------------------------

call demo

self~put(item, ix)

return

{{out}}

<pre>

 

=={{header|PARI/GP}}==

my(inc=#v\2);

while(inc,

);

v

 

=={{header|Pascal}}==

 

MaxN = 100; { number of elements (my example is 100) }

Type

End;

End;

 

=={{header|Perl}}==

 

my (@a, $h, $i, $j, $k) = @_;

for ($h = @a; $h = int $h / 2;) {

@a = shell_sort @a;

say "@a";

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">shell_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)))</span>

{{out}}

<pre>

 

=={{header|PHP}}==

function shellSort($arr)

{

return $arr;

}

 

=={{header|Picat}}==

Using the algorithm from the Wikipedia page, inline sort.

A = [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78],

println(A),

end,

Inc := round(Inc/2.2)

 

{{out}}

 

=={{header|PicoLisp}}==

(for (Inc (*/ (length A) 2) (gt0 Inc) (*/ Inc 10 22))

(for (I Inc (get A I) (inc I))

(dec 'J Inc) )

(set (nth A J) Tmp) ) ) )

{{out}}

<pre>: (shellSort (make (do 9 (link (rand 1 999)))))

 

=={{header|PL/I}}==

/* Based on Rosetta Fortran */

Shell_Sort: PROCEDURE (A);

END;

END SHELL_SORT;

 

=={{header|PowerShell}}==

{

# http://oeis.org/A108870

}

 

 

=={{header|PureBasic}}==

{{trans|Fortran}}

 

Procedure Shell_sort(Array A(1))

EndIf

Wend

 

=={{header|Python}}==

This method sorts in place.

If you want to preserve your unsorted list, copy it first.

inc = len(seq) // 2

while inc:

i -= inc

seq[i] = el

 

{{output}}

 

=={{header|Racket}}==

#lang racket

(define (shell-sort! xs)

(loop (new Δ))))

xs)

 

=={{header|Raku}}==

(formerly Perl 6)

loop ( my $gap = (@a/2).round; $gap > 0; $gap = ( $gap * 5 / 11 ).round ) {

for $gap .. @a.end -> $i {

say 'input = ' ~ @data;

say 'output = ' ~ @data.&shell_sort;

 

{{out}}

 

'''ZIP''' = '''Z'''one '''I'''mprovement '''P'''lan. &nbsp; &nbsp; Now-a-days, the USA uses two-character abbreviations.

call gen /*generate the array elements. */

call show 'before sort' /*display the before array elements. */

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the (internal) inputs:}}

<pre style="height:85ex">

 

=={{header|Ring}}==

aList = [-12, 3, 0, 4, 7, 4, 8, -5, 9]

shellSort(aList)

end

return a

 

=={{header|Ruby}}==

 

This method sorts in place. If you want to preserve your unsorted list, copy it first.

def shellsort!

inc = length / 2

data = [22, 7, 2, -5, 8, 4]

data.shellsort!

 

=={{header|Run BASIC}}==

{{works with|QBasic}}

dim a(siz)

for i = 1 to siz

next i

incr = int(incr / 2.2)

 

=={{header|Rust}}==

fn shell_sort<T: Ord + Copy>(v: &mut [T]) {

let mut gap = v.len() / 2;

}

 

{{out}}

<pre>

 

=={{header|Scala}}==

def incSeq(len:Int)=new Iterator[Int]{

private[this] var x:Int=len/2

println(a.mkString(","))

}

{{out}}

<pre>2,5,3,4,3,9,3,2,5,4,1,3,22,7,2,-5,8,4

 

=={{header|Seed7}}==

local

var integer: i is 0;

increment := increment div 2;

end while;

 

Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#shellSort]

=={{header|Sidef}}==

{{trans|Perl}}

var h = a.len;

while (h >>= 1) {

say a;

shell_sort(a);

{{out}}

<pre>[54, 67, 65, 8, 56, 83, 64, 42, 20, 17]

=={{header|Swift}}==

{{works with|Swift|2.1}}

var inc = seq.count / 2

while inc > 0 {

}

}

 

{{in}}

 

=={{header|Tcl}}==

 

proc shellsort {m} {

}

 

 

=={{header|uBasic/4tH}}==

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

=={{header|Visual Basic}}==

Dim lngHold, lngGap As Long

Dim lngCount, lngMin, lngMax As Long

Loop

arrShellSort = arrData

 

mut j := 0

for h := n; h /= 2; {

shell(mut arr, n)

println('Output: ' + arr.str())

{{out}}

<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]

=={{header|Wren}}==

Based on the Wikipedia article pseudo-code.

var n = a.count

var gaps = [701, 301, 132, 57, 23, 10, 4, 1]

}

 

System.print("Before: %(a)")

shellSort.call(a)

System.print("After : %(a)")

System.print()

 

{{out}}

Alternatively we can just call a library method.

{{libheader|Wren-sort}}

 

System.print("Before: %(a)")

Sort.shell(a)

System.print("After : %(a)")

System.print()

 

{{out}}

 

=={{header|XPL0}}==

include c:\cxpl\codes; \intrinsic 'code' declarations

string 0; \use zero-terminated strings

SSort(Str, StrLen(Str));

Text(0, Str); CrLf(0);

 

{{out}}

 

=={{header|Yabasic}}==

// Shell sort based on insertion sort

 

next n

 

 

=={{header|zkl}}==

// Requires mutiable list

fcn shellSort(sequence){

}

return(sequence);

 

{{omit from|GUISS}}