Sorting algorithms/Shell sort: Difference between revisions
Added Easylang
(Added Easylang) |
|||
(13 intermediate revisions by 6 users not shown) | |||
Line 24:
{{trans|Python}}
<
V inc = seq.len I/ 2
L inc != 0
Line 37:
V data = [22, 7, 2, -5, 8, 4]
shell_sort(&data)
print(data)</
{{out}}
Line 47:
{{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
Line 122:
RK EQU 8 incr
RT EQU 9 temp
END SHELLSRT</
{{out}}
<pre>
Line 130:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program shellSort64.s */
Line 303:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<
INT i
Line 368:
Test(c,8)
Test(d,12)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Shell_sort.png Screenshot from Atari 8-bit computer]
Line 394:
=={{header|ActionScript}}==
<
{
var inc:uint = data.length/2;
Line 412:
return data;
}
</syntaxhighlight>
=={{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 (<>);
Line 422:
package Shell_Sort is
procedure Sort(Item : in out Array_Type);
end Shell_Sort;</
<
----------
Line 452:
end Sort;
end Shell_Sort;</
=={{header|ALGOL 68}}==
Line 459:
{{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].}}
'''File: prelude/sort/shell.a68'''<
COMMENT
Line 519:
shell sort in place(LOC[LWB seq: UPB seq]SORTELEMENT:=seq, sort cmp rev);
SKIP</
# -*- coding: utf-8 -*- #
Line 526:
[]SORTELEMENT char array data = "big fjords vex quick waltz nymph";
print((shell sort(char array data), new line))</
{{out}}
<pre>
Line 534:
=={{header|AppleScript}}==
<
-- Algorithm: Donald Shell, 1959.
on ShellSort(theList, l, r) -- Sort items l thru r of theList.
Line 575:
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.
return aList</
{{output}}
<
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program shellSort.s */
Line 814:
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<
a: new items
h: size a
Line 838:
]
print shellSort [3 1 2 8 5 7 9 4 6]</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|ATS}}==
===For arrays whose elements may be of linear type===
<syntaxhighlight lang="ats">(* Shell sort with both the gap sequence and the order predicate
selected by templates. *)
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
extern fn {a : vt@ype} (* The "less than" template. *)
shell_sort$lt : (&a, &a) -<> bool
extern fn {} (* Maps array size to a gap sequence. *)
shell_sort$gaps : {n : int} size_t n -<> List1 ([i : pos] size_t i)
extern fn {a : vt@ype}
shell_sort {n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
(*------------------------------------------------------------------*)
(* Implementation *)
extern praxi
array_v_takeout2 (* Get views for two distinct array elements.*)
{a : vt@ype}
{p : addr}
{n : int}
{i, j : nat | i < n; j < n; i != j}
(pfarr : array_v (a, p, n))
:<prf> @(a @ p + (i * sizeof a),
a @ p + (j * sizeof a),
(a @ p + (i * sizeof a),
a @ p + (j * sizeof a)) -<prf,lin> array_v (a, p, n))
implement {a}
shell_sort {n} (arr, n) =
let
fun
gapped_sort {gap : pos | gap < n}
{i : int | gap <= i; i <= n}
{p_arr : addr}
.<n - i>.
(pf_arr : !array_v (a, p_arr, n) >> _ |
p_arr : ptr p_arr,
gap : size_t gap,
i : size_t i)
:<!wrt> void =
if i <> n then
let
fun
move_elems {j : nat | j <= i}
.<j>.
(pf_arr : !array_v (a, p_arr, n) >> _ |
j : size_t j)
:<!wrt> void =
(* For simplicity in the safe use of an array, use
interchanges of array elements, instead of a temporary
variable and moves. *)
if gap <= j then
let
stadef k = j - gap
prval () = prop_verify {0 <= k} ()
prval () = prop_verify {k < j} ()
val k : size_t k = j - gap
val pk = ptr_add<a> (p_arr, k)
and pj = ptr_add<a> (p_arr, j)
prval @(pfk, pfj, fpf) =
array_v_takeout2 {a} {p_arr} {n} {k, j} pf_arr
val is_less = shell_sort$lt<a> (!pj, !pk)
prval () = pf_arr := fpf (pfk, pfj)
in
if is_less then
begin
array_interchange (!p_arr, k, j);
move_elems (pf_arr | k)
end
end
in
move_elems (pf_arr | i);
gapped_sort (pf_arr | p_arr, gap, succ i)
end
fun
go_through_gaps
{num_gaps : nat}
.<num_gaps>.
(arr : &array (a, n) >> _,
gaps : list ([i : pos] size_t i, num_gaps))
:<!wrt> void =
case+ gaps of
| list_nil () => ()
| list_cons (gap, more_gaps) =>
if n <= gap then
go_through_gaps (arr, more_gaps)
else
begin
gapped_sort (view@ arr | addr@ arr, gap, gap);
go_through_gaps (arr, more_gaps)
end
in
go_through_gaps (arr, shell_sort$gaps<> n)
end
(*------------------------------------------------------------------*)
implement
shell_sort$lt<int> (x, y) =
x < y
implement
main0 () =
let
(* Gaps by Marcin Ciura. https://oeis.org/A102549 *)
val ciura_gaps =
$list{[i : pos] size_t i}
(i2sz 1750,
i2sz 701, i2sz 301,
i2sz 132, i2sz 57,
i2sz 23, i2sz 10,
i2sz 4, i2sz 1)
implement
shell_sort$gaps<> n =
(* Use Ciura's gaps, regardless of array size. *)
ciura_gaps
#define SIZE 30
var i : [i : nat] int i
var arr : array (int, SIZE)
in
array_initize_elt<int> (arr, i2sz SIZE, 0);
for (i := 0; i < SIZE; i := succ i)
arr[i] := $extfcall (int, "rand") % 10;
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ();
shell_sort<int> (arr, i2sz SIZE);
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ()
end</syntaxhighlight>
{{out}}
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 shell_sort_task.dats -lgc && ./a.out
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 1 8 7 9 2 0 2 3 7 5
0 0 0 1 1 2 2 2 2 2 3 3 3 3 5 5 5 6 6 6 6 6 7 7 7 7 8 9 9 9</pre>
Comments:
Because the value of a[i] ends up in a particular spot earlier in the array, it is common to store that value in a temporary variable, rather than use interchanges (swaps) to move the value through the array. Writing "safe" code to do it with a temporary variable, however, would have been tedious, so I used interchanges. One can always write the implementation "unsafely", however. This will still leave you with about as much "safety" as one would expect from most other languages.
Furthermore, there is no difficulty in using the temporary-variable approach, if the elements of the array are assumed to be non-linear ('''t@ype''' instead of '''vt@ype'''). For example, the element type used in the demonstration ('''int''') is not linear. And so the next version of the sort ...
===For arrays whose elements must be of non-linear type===
The differences from the previous implementation are mainly in the '''gapped_sort''' function. Note that the order predicate now gets its arguments by value instead of by reference.
<syntaxhighlight lang="ats">(* Shell sort with both the gap sequence and the order predicate
selected by templates. *)
(* This version is only for arrays of non-linear elements (whose
values may freely be copied). Thus the code looks more like what
one would write in most other programming languages. *)
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
extern fn {a : t@ype} (* The "less than" template. *)
shell_sort2$lt : (a, a) -<> bool
extern fn {} (* Maps array size to a gap sequence. *)
shell_sort2$gaps : {n : int} size_t n -<> List1 ([i : pos] size_t i)
extern fn {a : t@ype}
shell_sort2 {n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
(*------------------------------------------------------------------*)
(* Implementation *)
implement {a}
shell_sort2 {n} (arr, n) =
let
macdef lt = shell_sort2$lt<a>
fun
gapped_sort {gap : pos | gap < n}
{i : int | gap <= i; i <= n}
.<n - i>.
(arr : &array (a, n) >> _,
gap : size_t gap,
i : size_t i)
:<!wrt> void =
if i <> n then
let
fun
move_elems {j : nat | j <= i}
.<j>.
(arr : &array (a, n) >> _,
temp : a,
j : size_t j)
:<!wrt> void =
if j < gap then
arr[j] := temp
else if ~(temp \lt arr[j - gap]) then
arr[j] := temp
else
begin
arr[j] := arr[j - gap];
move_elems (arr, temp, j - gap)
end
in
move_elems (arr, arr[i], i);
gapped_sort (arr, gap, succ i)
end
fun
go_through_gaps
{num_gaps : nat}
.<num_gaps>.
(arr : &array (a, n) >> _,
gaps : list ([i : pos] size_t i, num_gaps))
:<!wrt> void =
case+ gaps of
| list_nil () => ()
| list_cons (gap, more_gaps) =>
if n <= gap then
go_through_gaps (arr, more_gaps)
else
begin
gapped_sort (arr, gap, gap);
go_through_gaps (arr, more_gaps)
end
in
go_through_gaps (arr, shell_sort2$gaps<> n)
end
(*------------------------------------------------------------------*)
implement
shell_sort2$lt<int> (x, y) =
x < y
implement
main0 () =
let
(* Gaps by Marcin Ciura. https://oeis.org/A102549 *)
val ciura_gaps =
$list{[i : pos] size_t i}
(i2sz 1750,
i2sz 701, i2sz 301,
i2sz 132, i2sz 57,
i2sz 23, i2sz 10,
i2sz 4, i2sz 1)
implement
shell_sort2$gaps<> n =
(* Use Ciura's gaps, regardless of array size. *)
ciura_gaps
#define SIZE 30
var i : [i : nat] int i
var arr : array (int, SIZE)
in
array_initize_elt<int> (arr, i2sz SIZE, 0);
for (i := 0; i < SIZE; i := succ i)
arr[i] := $extfcall (int, "rand") % 10;
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ();
shell_sort2<int> (arr, i2sz SIZE);
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ()
end</syntaxhighlight>
{{out}}
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 shell_sort_task_nonlinear.dats -lgc && ./a.out
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 1 8 7 9 2 0 2 3 7 5
0 0 0 1 1 2 2 2 2 2 3 3 3 3 5 5 5 6 6 6 6 6 7 7 7 7 8 9 9 9</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")
Line 865 ⟶ 1,163:
s .= "," . a%A_Index%
Return SubStr(s,2) ; drop leading comma
}</
=={{header|AWK}}==
{{trans|Fortran}}
<
line[NR] = $0
}
Line 893 ⟶ 1,191:
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)
Line 921 ⟶ 1,219:
NEXT
ENDWHILE
ENDPROC</
{{out}}
<pre>
Line 928 ⟶ 1,226:
=={{header|BCPL}}==
<
LET shellsort(v, upb) BE
Line 976 ⟶ 1,274:
{ //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) {
Line 1,005 ⟶ 1,303:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,013 ⟶ 1,311:
=={{header|C sharp|C#}}==
<
public static class ShellSorter
{
Line 1,043 ⟶ 1,341:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,068 ⟶ 1,366:
=={{header|C++}}==
<
#include <time.h>
#include <iostream>
Line 1,142 ⟶ 1,440:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
{{out}}
<pre>
Line 1,172 ⟶ 1,470:
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.
*******************************************************
Line 1,271 ⟶ 1,569:
IF KEY-RESULT = ' '
MOVE '=' TO KEY-RESULT
END-IF.</
===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".
Line 1,329 ⟶ 1,627:
G-999.
EXIT.</
=={{header|Common Lisp}}==
<
(let ((length (length array)))
(if (< length 2) array
Line 1,352 ⟶ 1,650:
"Last gap of ~w is not 1." gaps)
(dolist (gap gaps array)
(gap-insertion-sort array predicate gap)))</
=={{header|D}}==
<
void shellSort(T)(T[] seq) pure nothrow {
Line 1,375 ⟶ 1,673:
shellSort(data);
writeln(data);
}</
{{out}}
<pre>[-5, 2, 4, 7, 8, 22]</pre>
=={{header|Dart}}==
<syntaxhighlight lang="dart">
void main() {
List<int> a = shellSort([1100, 2, 56, 200, -52, 3, 99, 33, 177, -199]);
print('$a');
}
shellSort(List<int> array) {
int n = array.length;
// Start with a big gap, then reduce the gap
for (int gap = n~/2; gap > 0; gap ~/= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already
// in gapped order keep adding one more element
// until the entire array is gap sorted
for (int i = gap; i < n; i += 1)
{
// add a[i] to the elements that have been gap
// sorted save a[i] in temp and make a hole at
// position i
int temp = array[i];
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
int j;
for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
array[j] = array[j - gap];
// put temp (the original a[i]) in its correct
// location
array[j] = temp;
}
}
return array;
}
</syntaxhighlight>
{{out}}
<pre>[-199, -52, 2, 3, 33, 56, 99, 177, 200, 1100]</pre>
=={{header|Delphi}}==
<
const
gaps:array[0..7] of Integer = (701, 301, 132, 57, 23, 10, 4, 1);
Line 1,402 ⟶ 1,744:
end;
end;
end;</
=={{header|E}}==
Line 1,408 ⟶ 1,750:
{{trans|Python}}
<
def shellSort(array) {
var inc := array.size() // 2
Line 1,421 ⟶ 1,763:
inc := if (inc <=> 2) { 1 } else { (inc * 5.0 / 11).floor() }
}
}</
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight>
proc shellsort . a[] .
inc = len a[] div 2
while inc > 0
for i = inc to len a[]
tmp = a[i]
j = i
while j > inc and a[j - inc] > tmp
a[j] = a[j - inc]
j = j - inc
.
a[j] = tmp
.
inc = floor (0.5 + inc / 2.2)
.
.
a[] = [ -12 3 0 4 7 4 8 -5 9 ]
shellsort a[]
print a[]
</syntaxhighlight>
{{out}}
<pre>
[ -12 -5 0 3 4 4 7 8 9 ]
</pre>
=={{header|Eiffel}}==
Line 1,432 ⟶ 1,801:
For a more complete explanation of the Eiffel sort examples, see [[Sorting algorithms/Bubble sort#Eiffel|Bubble sort]].
<
MY_SORTED_SET [G -> COMPARABLE]
inherit
Line 1,473 ⟶ 1,842:
end
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))
Line 1,512 ⟶ 1,881:
list = [0, 14, 11, 8, 13, 15, 5, 7, 16, 17, 1, 6, 12, 2, 10, 4, 19, 9, 18, 3]
IO.inspect Sort.shell_sort(list)</
{{out}}
Line 1,520 ⟶ 1,889:
=={{header|Euphoria}}==
<
integer gap,j
object temp
Line 1,543 ⟶ 1,912:
? s
puts(1,"After: ")
? shell_sort(s)</
{{out}}
Line 1,552 ⟶ 1,921:
=={{header|Forth}}==
{{works with|GNU Forth}}
<
: shell { array len -- }
Line 1,572 ⟶ 1,941:
array 10 shell
array 10 cells dump</
A version without local variables:
<
: (shell) ( a n h -- a n h)
Line 1,602 ⟶ 1,971:
array 10 shell
array 10 cells dump</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
CONTAINS
Line 1,656 ⟶ 2,025:
WRITE (*,*) array
END PROGRAM Shellsort</
=={{header|FreeBASIC}}==
modified bubble sort code
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 1,712 ⟶ 2,081:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>unsorted 1 -4 -1 7 -6 3 6 -7 -5 2 -2 0 5 4 -3
Line 1,719 ⟶ 2,088:
=={{header|Go}}==
Following WP pseudocode:
<
import "fmt"
Line 1,737 ⟶ 2,106:
}
fmt.Println("after: ", a)
}</
{{out}}
<pre>
Line 1,747 ⟶ 2,116:
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
. takeWhile (not.null). unfoldr (Just. splitAt k)</
=={{header|Haxe}}==
<
@:generic
public static function sort<T>(arr:Array<T>) {
Line 1,792 ⟶ 2,161:
Sys.println('Sorted Strings: ' + stringArray);
}
}</
{{out}}
Line 1,805 ⟶ 2,174:
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(shellsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 1,825 ⟶ 2,194:
}
return X
end</
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.
Line 1,839 ⟶ 2,208:
=={{header|Io}}==
Translated from pseudocode at [[wp:Shell_sort#Shell_sort_algorithm_in_pseudocode|Wikipedia]]
<
shellSortInPlace := method(
gap := (size / 2) round
Line 1,859 ⟶ 2,228:
l := list(2, 3, 4, 5, 1)
l shellSortInPlace println # ==> list(1, 2, 3, 4, 5)</
=={{header|IS-BASIC}}==
<
110 RANDOMIZE
120 LET N=20 ! Number of elements
Line 1,897 ⟶ 2,266:
430 LET D=INT(D/2)
440 LOOP WHILE D>0
450 END DEF</
=={{header|J}}==
Line 1,904 ⟶ 2,273:
'''Solution'''
<
insert =: (I.~ {. ]) , [ , ] }.~ I.~
gapinss =: #@] {. ,@|:@(] insert//.~ #@] $ i.@[)
shellSort =: [: ; gapinss &.>/@(< ,~ ]&.>@gaps)</
Example:
<
1 2 3 4 5 6 7 8 9</
=={{header|Java}}==
Line 1,918 ⟶ 2,287:
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) {
Line 1,936 ⟶ 2,305:
}
}
}</
=={{header|JavaScript}}==
<
for (var h = a.length; h > 0; h = parseInt(h / 2)) {
for (var i = h; i < a.length; i++) {
Line 1,956 ⟶ 2,325:
a.push(parseInt(Math.random() * 100));
shellSort(a);
document.write(a.join(" "));</
=={{header|jq}}==
Line 1,963 ⟶ 2,332:
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:
Line 1,986 ⟶ 2,355:
)
| [(($h+1)*5/11 | floor), .] )
| .[1] ;</
'''Example''':
<
[5,null,3,1,2,0,4.4,5]
) | shellSort</
{{Out}}
<
[]
[null,0,1,2,3,4.4,5,5]</
=={{header|Julia}}==
{{trans|Java}}
<
function shellsort!(a::Array{Int})::Array{Int}
Line 2,023 ⟶ 2,392:
x = rand(1:10, 10)
@show x shellsort!(x)
@assert issorted(x)</
{{out}}
Line 2,030 ⟶ 2,399:
=={{header|Kotlin}}==
<
val gaps = listOf(701, 301, 132, 57, 23, 10, 4, 1) // Marcin Ciura's gap sequence
Line 2,058 ⟶ 2,427:
println(a.joinToString(", "))
}
}</
{{out}}
Line 2,068 ⟶ 2,437:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
siz = 100
dim a(siz)
Line 2,099 ⟶ 2,468:
print a(i)
next
</syntaxhighlight>
=={{header|Lisaac}}==
<
+ name := SHELL_SORT;
Line 2,147 ⟶ 2,516:
};
};
);</
=={{header|Lua}}==
<
local inc = math.ceil( #a / 2 )
while inc > 0 do
Line 2,173 ⟶ 2,542:
for _, i in pairs(a) do
print(i)
end</
=={{header|M2000 Interpreter}}==
Line 2,183 ⟶ 2,552:
A For statement can be as in this example or the faster For { } without Next
<syntaxhighlight lang="m2000 interpreter">
Module ShellSortExample {
Module shellsort(&a()) {
Line 2,209 ⟶ 2,578:
}
ShellSortExample
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="text">shellsort := proc(arr)
local n, gap, i, val, j;
n := numelems(arr):
Line 2,231 ⟶ 2,600:
arr := Array([17,3,72,0,36,2,3,8,40,0]);
shellsort(arr);
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,
Line 2,251 ⟶ 2,620:
If[incr == 2, incr = 1, incr = Round[incr/2.2]]
]; list
]</
<pre>shellSort[{2,1,4,6,8}]
Line 2,258 ⟶ 2,627:
=={{header|MATLAB}} / {{header|Octave}}==
This is a translation of the FORTRAN solution into MATLAB.
<
N = numel(list);
Line 2,283 ⟶ 2,652:
end
end %while
end %shellSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 2,338 ⟶ 2,707:
method isFalse public constant binary returns boolean
return \isTrue
</syntaxhighlight>
{{out}}
<pre>
Line 2,361 ⟶ 2,730:
=={{header|Nim}}==
<
var h = a.len
while h > 0:
Line 2,375 ⟶ 2,744:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
shellSort a
echo a</
=={{header|Objeck}}==
{{trans|C sharp}}
<
bundle Default {
class ShellSort {
Line 2,414 ⟶ 2,783:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
{{trans|C}}
<
let len = Array.length a in
let incSequence = [| 412771; 165103; 66041; 26417; 10567;
Line 2,438 ⟶ 2,807:
done;
) incSequence;
;;</
and the main:
<
let arraysize = 1000 in (* or whatever *)
Random.self_init();
Line 2,449 ⟶ 2,818:
Array.iter (Printf.printf " %d") intArray;
print_newline();
;;</
=={{header|ooRexx}}==
{{Trans|NetRexx}}
<
-- --- Main --------------------------------------------------------------------
call demo
Line 2,530 ⟶ 2,899:
self~put(item, ix)
return
</syntaxhighlight>
{{out}}
<pre>
Line 2,553 ⟶ 2,922:
=={{header|PARI/GP}}==
<
my(inc=#v\2);
while(inc,
Line 2,566 ⟶ 2,935:
);
v
};</
=={{header|Pascal}}==
<
MaxN = 100; { number of elements (my example is 100) }
Type
Line 2,593 ⟶ 2,962:
End;
End;
</syntaxhighlight>
=={{header|Perl}}==
<
my (@a, $h, $i, $j, $k) = @_;
for ($h = @a; $h = int $h / 2;) {
Line 2,615 ⟶ 2,984:
@a = shell_sort @a;
say "@a";
</syntaxhighlight>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,639 ⟶ 3,008:
<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>
Line 2,646 ⟶ 3,015:
=={{header|PHP}}==
<
function shellSort($arr)
{
Line 2,666 ⟶ 3,035:
return $arr;
}
</syntaxhighlight>
=={{header|Picat}}==
Using the algorithm from the Wikipedia page, inline sort.
<syntaxhighlight lang="picat">go =>
A = [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78],
println(A),
shell_sort(A),
println(A),
nl.
% Inline sort
shell_sort(A) =>
Inc = round(A.length/2),
while (Inc > 0)
foreach(I in Inc+1..A.length)
Temp = A[I],
J := I,
while (J > Inc, A[J-Inc] > Temp)
A[J] := A[J-Inc],
J := J - Inc
end,
A[J] := Temp
end,
Inc := round(Inc/2.2)
end.</syntaxhighlight>
{{out}}
<pre>[23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78]
[12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99]</pre>
=={{header|PicoLisp}}==
<
(for (Inc (*/ (length A) 2) (gt0 Inc) (*/ Inc 10 22))
(for (I Inc (get A I) (inc I))
Line 2,677 ⟶ 3,076:
(dec 'J Inc) )
(set (nth A J) Tmp) ) ) )
A )</
{{out}}
<pre>: (shellSort (make (do 9 (link (rand 1 999)))))
Line 2,689 ⟶ 3,088:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* Based on Rosetta Fortran */
Shell_Sort: PROCEDURE (A);
Line 2,713 ⟶ 3,112:
END;
END SHELL_SORT;
</syntaxhighlight>
=={{header|PowerShell}}==
<
{
# http://oeis.org/A108870
Line 2,741 ⟶ 3,140:
}
$l = 10000; ShellSort( ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } ) )</
=={{header|PureBasic}}==
{{trans|Fortran}}
<
Procedure Shell_sort(Array A(1))
Line 2,766 ⟶ 3,165:
EndIf
Wend
EndProcedure</
=={{header|Python}}==
Line 2,773 ⟶ 3,172:
This method sorts in place.
If you want to preserve your unsorted list, copy it first.
<
inc = len(seq) // 2
while inc:
Line 2,781 ⟶ 3,180:
i -= inc
seq[i] = el
inc = 1 if inc == 2 else inc * 5 // 11</
{{output}}
Line 2,792 ⟶ 3,191:
=={{header|Racket}}==
<
#lang racket
(define (shell-sort! xs)
Line 2,807 ⟶ 3,206:
(loop (new Δ))))
xs)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
loop ( my $gap = (@a/2).round; $gap > 0; $gap = ( $gap * 5 / 11 ).round ) {
for $gap .. @a.end -> $i {
Line 2,831 ⟶ 3,230:
say 'input = ' ~ @data;
say 'output = ' ~ @data.&shell_sort;
</syntaxhighlight>
{{out}}
Line 2,844 ⟶ 3,243:
'''ZIP''' = '''Z'''one '''I'''mprovement '''P'''lan. Now-a-days, the USA uses two-character abbreviations.
<
call gen /*generate the array elements. */
call show 'before sort' /*display the before array elements. */
Line 2,889 ⟶ 3,288:
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do j=1 for #; say 'element' right(j, length(#) ) arg(1)": " @.j; end; return</
{{out|output|text= when using the (internal) inputs:}}
<pre style="height:85ex">
Line 3,001 ⟶ 3,400:
=={{header|Ring}}==
<
aList = [-12, 3, 0, 4, 7, 4, 8, -5, 9]
shellSort(aList)
Line 3,023 ⟶ 3,422:
end
return a
</syntaxhighlight>
=={{header|Ruby}}==
Line 3,029 ⟶ 3,428:
This method sorts in place. If you want to preserve your unsorted list, copy it first.
<
def shellsort!
inc = length / 2
Line 3,049 ⟶ 3,448:
data = [22, 7, 2, -5, 8, 4]
data.shellsort!
p data # [-5, 2, 4, 7, 8, 22]</
=={{header|Run BASIC}}==
{{works with|QBasic}}
<
dim a(siz)
for i = 1 to siz
Line 3,074 ⟶ 3,473:
next i
incr = int(incr / 2.2)
WEND</
=={{header|Rust}}==
<
fn shell_sort<T: Ord + Copy>(v: &mut [T]) {
let mut gap = v.len() / 2;
Line 3,102 ⟶ 3,501:
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,110 ⟶ 3,509:
=={{header|Scala}}==
<
def incSeq(len:Int)=new Iterator[Int]{
private[this] var x:Int=len/2
Line 3,136 ⟶ 3,535:
println(a.mkString(","))
}
}</
{{out}}
<pre>2,5,3,4,3,9,3,2,5,4,1,3,22,7,2,-5,8,4
Line 3,142 ⟶ 3,541:
=={{header|Seed7}}==
<
local
var integer: i is 0;
Line 3,162 ⟶ 3,561:
increment := increment div 2;
end while;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#shellSort]
Line 3,168 ⟶ 3,567:
=={{header|Sidef}}==
{{trans|Perl}}
<
var h = a.len;
while (h >>= 1) {
Line 3,185 ⟶ 3,584:
say a;
shell_sort(a);
say a;</
{{out}}
<pre>[54, 67, 65, 8, 56, 83, 64, 42, 20, 17]
Line 3,192 ⟶ 3,591:
=={{header|Swift}}==
{{works with|Swift|2.1}}
<
var inc = seq.count / 2
while inc > 0 {
Line 3,208 ⟶ 3,607:
}
}
}</
{{in}}
Line 3,217 ⟶ 3,616:
=={{header|Tcl}}==
<
proc shellsort {m} {
Line 3,237 ⟶ 3,636:
}
puts [shellsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">PRINT "Shell sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 3,292 ⟶ 3,691:
PRINT
RETURN</
=={{header|Visual Basic}}==
<
Dim lngHold, lngGap As Long
Dim lngCount, lngMin, lngMax As Long
Line 3,320 ⟶ 3,719:
Loop
arrShellSort = arrData
End Sub'</
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn shell(mut arr []int, n int) {
mut j := 0
for h := n; h /= 2; {
Line 3,342 ⟶ 3,741:
shell(mut arr, n)
println('Output: ' + arr.str())
}</
{{out}}
<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Line 3,353 ⟶ 3,752:
=={{header|Wren}}==
Based on the Wikipedia article pseudo-code.
<
var n = a.count
var gaps = [701, 301, 132, 57, 23, 10, 4, 1]
Line 3,371 ⟶ 3,770:
}
var
for (a in
System.print("Before: %(a)")
shellSort.call(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 3,390 ⟶ 3,789:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<
var
for (a in
System.print("Before: %(a)")
Sort.shell(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 3,406 ⟶ 3,805:
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">
include c:\cxpl\codes; \intrinsic 'code' declarations
string 0; \use zero-terminated strings
Line 3,442 ⟶ 3,841:
SSort(Str, StrLen(Str));
Text(0, Str); CrLf(0);
]</
{{out}}
Line 3,450 ⟶ 3,849:
=={{header|Yabasic}}==
<
// Shell sort based on insertion sort
Line 3,505 ⟶ 3,904:
next n
end if</
=={{header|zkl}}==
<
// Requires mutiable list
fcn shellSort(sequence){
Line 3,526 ⟶ 3,925:
}
return(sequence);
}</
{{omit from|GUISS}}
|