Sorting algorithms/Shell sort: Difference between revisions

 

;Task:

Other good sequences are found at the [https://oeis.org/search?q=shell+sort On-Line Encyclopedia of Integer Sequences].

<br><br>

=={{header|360 Assembly}}==

{{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>

-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782

</pre>

 

=={{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>

abcdefghiijklmnopqrstuvwxyz

</pre>

 

=={{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>

4 65 2 -31 0 99 2 83 782 1

-31 0 1 2 2 4 65 83 99 782

</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|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|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.

on string : "qwerty"

with op = &null: "eqrtwy" (0 ms)</pre>

 

=={{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|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>

 

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:

h = h div 2

let k = a[i]

var j = i

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

 

{{out}}

<pre>

</pre>

 

=={{header|PHP}}==

function shellSort($arr)

{

return $arr;

}

 

=={{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:

while i >= inc and seq[i - inc] > el:

seq[i] = seq[i - inc]

i -= inc

seq[i] = el

 

 

=={{header|Racket}}==

#lang racket

(define (shell-sort! xs)

(loop (new Δ))))

xs)

 

=={{header|REXX}}==

Historical data note: &nbsp; the three-character abbreviations were (and probably still are) the

<br>official three-character abbreviations for the states of the USA before the advent of ZIP codes.

call gen /*generate the array elements. */

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

call shellSort # /*invoke the shell sort. */

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

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

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

return

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

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

element 1 before sort: 3 character abbreviations for states of the USA

element 2 before sort: ===============================================

 

=={{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}}==

dim a(siz)

for i = 1 to siz

next i

incr = int(incr / 2.2)

 

=={{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|Whitespace}}==

 

[[/Whitespace|Implementation in Whitespace]].

 

=={{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}}

" .Pabcdeefghiiijklmnoooqrstuuvwxyz"

</pre>

 

=={{header|zkl}}==

// Requires mutiable list

fcn shellSort(sequence){

}

return(sequence);

 

{{omit from|GUISS}}