Sorting algorithms/Gnome sort: Difference between revisions

Implement the Gnome sort in your language to sort an array (or list) of numbers.

<br><br>

 

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

GNOME CSECT

USING GNOME,R13 base register

PG DC CL125' ' buffer

REGEQU

{{out}}

<pre>

</pre>

 

 

=={{header|ActionScript}}==

{

var pos:uint = 0;

}

return array;

 

=={{header|Ada}}==

This example is a generic procedure for constrained array types.

type Element_Type is private;

type Index is (<>);

type Collection is array(Index) of Element_Type;

with function "<=" (Left, Right : Element_Type) return Boolean is <>;

 

procedure Swap(Left, Right : in out Element_Type) is

Temp : Element_Type := Left;

end if;

end loop;

Usage example:

with Ada.Text_Io; use Ada.Text_Io;

 

end loop;

New_Line;

 

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

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

 

 

PROC inplace gnome sort = (REF[]SORTSTRUCT list)REF[]SORTSTRUCT:

in place gnome sort(LOC[LWB seq: UPB seq]SORTSTRUCT:=seq);

 

Output:

<pre>

</pre>

 

=={{header|AutoHotkey}}==

contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276379.html#276379 forum]

MsgBox % GnomeSort("xxx")

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

sorted .= "," . a%A_Index%

Return SubStr(sorted,2) ; drop leading comma

 

=={{header|AWK}}==

This version includes the mark/resume optimization. It remembers where it was before backing up so that once an item is backed up to its proper place the process resumes from where it was before backing up.

 

 

BEGIN {

print ""

}

 

Example output:

 

=={{header|BASIC}}==

{{works with|QuickBasic|4.5}}

 

{{trans|C}}

'...more code...

sort:

end if

end if

 

=={{header|Batch File}}==

{{works with|Windows NT}}

 

SETLOCAL EnableExtensions EnableDelayedExpansion

:: GnomeSort.cmd in WinNT Batch using pseudo array.

 

ENDLOCAL

 

 

=={{header|C}}==

 

This algorithm sorts in place modifying the passed ''array'' (of <code>n</code> integer numbers).

{

int i=1, j=2, t;

}

# undef swap

 

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

 

public static void gnomeSort(int[] anArray)

{

}

}

 

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

Uses C++11. Compile with

g++ -std=c++11 gnome.cpp

#include <iterator>

#include <iostream>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

Output:

<pre>

=={{header|Clojure}}==

{{trans|Haskell}}

([c] (gnomesort c <))

([c pred]

(recur (concat x (list y1)) ys)))))))

 

 

=={{header|COBOL}}==

Procedure division stuff only.

C-000.

DISPLAY "SORT STARTING".

 

E-999.

 

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

(do ((position (min 1 length)))

((eql length position) array)

(aref array (1- position)))

(decf position))

 

=={{header|D}}==

 

void gnomeSort(T)(T arr) {

gnomeSort(a);

writeln(a);

 

=={{header|Delphi}}==

 

Static array is an arbitrary-based array of fixed length

 

{$APPTYPE CONSOLE}

Writeln;

Readln;

Output:

<pre>

 

=={{header|DWScript}}==

var

i, j : Integer;

Print(Format('%3d ', [a[i]]));

PrintLn('}');

Ouput :

<pre>

=={{header|E}}==

 

var size := array.size()

var i := 1

}

}

 

# value: [7, 9, 4, 2, 1, 3, 6, 5, 0, 8].diverge()

 

? gnomeSort(a)

? a

 

 

class

GNOME_SORT [G -> COMPARABLE]

end

 

Test:

class

APPLICATION

gnome: GNOME_SORT [INTEGER]

 

{{out}}

<pre>

=={{header|Elena}}==

ELENA 5.0 :

import system'routines;

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.gnomeSort().asEnumerable())

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def gnome_sort([]), do: []

def gnome_sort([h|t]), do: gnome_sort([h], t)

end

 

 

{{out}}

 

=={{header|Erlang}}==

-export([gnome/1]).

 

gnome(P, [Next|N]) ->

gnome([Next|P], N).

1> c(gnome_sort).

{ok,gnome_sort}

2> gnome_sort:gnome([8,3,9,1,3,2,6]).

[1,2,3,3,6,8,9]

 

=={{header|Euphoria}}==

integer i,j

object temp

end while

return s

 

=={{header|F Sharp|F#}}==

let rec loop i j =

if i < a.Length then

a.[i] <- t

if i=1 then loop j (j+1) else loop (i-1) j

 

=={{header|Factor}}==

 

=={{header|Fantom}}==

class Main

{

}

}

 

Output:

 

=={{header|Forth}}==

defer exchange

 

: .array 10 0 do example i cells + ? loop cr ;

 

A slightly optimized version is presented below, where Gnome sort keeps track of its previous position. This reduces the number of iterations significantly.

swap >r 2 tuck 1- ( c2 n c1)

begin ( c2 n c1)

else drop >r dup 1+ swap r> swap then

repeat drop drop drop r> drop

 

=={{header|Fortran}}==

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

implicit none

 

end subroutine Gnomesort

 

 

 

=={{header|Go}}==

 

import "fmt"

j++

}

 

More generic version that sorts anything that implements <code>sort.Interface</code>:

 

import (

j++

}

 

=={{header|Groovy}}==

Solution:

 

def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }

}

input

 

Test:

 

Output:

 

=={{header|Haskell}}==

gnomeSort (x:xs) = gs [x] xs

where

gs [] (y:ys) = gs [y] ys

gs xs [] = reverse xs

 

=={{header|Haxe}}==

@:generic

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

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

}

 

{{out}}

 

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

demosort(gnomesort,[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}}==

Naive version:

gnomeSortInPlace := method(

idx := 1

 

lst := list(5, -1, -4, 2, 9)

 

Optimized version, storing the position before traversing back towards the begining of the list ([[wp:Gnome_sort#Optimization|Wikipedia]])

gnomeSortInPlace := method(

idx1 := 1

 

lst := list(5, -1, -4, 2, 9)

 

=={{header|J}}==

{{eff note|J|/:~}}

swap=: ] A.~ *@position * #@[ !@- <:@position

gnome=: swap~ 2 >/\ ]

 

 

 

 

 

=={{header|Java}}==

{{trans|C}}

{

int i=1;

}

}

 

=={{header|JavaScript}}==

function moveBack(i) {

for( ; i > 0 && a[i-1] > a[i]; i--) {

}

return a;

 

=={{header|jq}}==

This implementation adheres to the specification.

The array to be sorted, however, can be any JSON array.

def do_until(condition; next):

def u: if condition then . else (next|u) end;

end

end )

'''Example''':

{{Out}}

[

null,

"a": "A"

}

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

i, j = 1, 2

while i < length(arr)

 

v = rand(-10:10, 10)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun <T: Comparable<T>> gnomeSort(a: Array<T>, ascending: Boolean = true) {

gnomeSort(array, false)

println("Sorted (desc) : ${array.asList()}")

 

{{out}}

=={{header|Lua}}==

Keep in mind that Lua arrays initial index is 1.

local i, j = 2, 3

 

end

end

Example:

gnomeSort(list)

for i, j in pairs(list) do

print(j)

 

=={{header|Maple}}==

len := numelems(arr):

i := 2:

end if:

end do:

{{Out|Output}}

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

 

While[ i<=Length[[list]],

If[ list[[i-1]]<=list[[i]],

list[[i-1;;i]]=list[[i;;i-1]];i--;];

If[i==1,i=j;j++;]

 

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

 

i = 2;

end %while

 

Sample Usage:

 

ans =

 

 

=={{header|MAXScript}}==

(

local i = 2

)

return arr

Output:

a = for i in 1 to 10 collect random 1 20

#(20, 10, 16, 2, 19, 12, 11, 3, 5, 16)

gnomesort a

#(2, 3, 5, 10, 11, 12, 16, 16, 19, 20)

 

=={{header|Metafont}}==

begingroup save i, j, t;

i := 1; j := 2;

fi

endfor

 

for i = 0 upto 9: a[i] := uniformdeviate(40); message decimal a[i]; endfor

message char10;

gnomesort(a, 10);

for i = 0 upto 9: message decimal a[i]; endfor

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return ra

;Output

<pre>

 

=={{header|Nim}}==

var

n = a.len

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

gnomeSort a

Output:

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

=={{header|Objeck}}==

{{trans|C}}

function : GnomeSort(a : Int[]) {

i := 1;

};

}

 

=={{header|OCaml}}==

from the toplevel:

let i = ref 1

and j = ref 2 in

 

# a ;;

 

=={{header|Octave}}==

i = 2; j = 3;

while ( i <= length(v) )

endwhile

s = v;

 

 

=={{header|ooRexx}}==

===version 1===

{{Trans|NetRexx}}

 

call demo

self~put(item, ix)

return

'''Output:

<pre>

===version 2===

{{trans|REXX}}

* 28.06.2014 Walter Pachl

* 30.06.2014 corrected in sync with REXX version 2

Say 'element' right(i,2) x[i]

End

'''output'''

Similar to REXX version 2

=={{header|Oz}}==

{{trans|Haskell}}

fun {GnomeSort Xs}

case Xs of nil then nil

end

in

 

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

my(i=2,j=3,n=#v,t);

while(i<=n,

);

v

 

=={{header|Pascal}}==

var

i, j, t : Integer;

end

end;

 

=={{header|Perl}}==

 

sub gnome_sort

}

return @a;

 

 

=={{header|Phix}}==

 

=={{header|PHP}}==

$i = 1;

$j = 2;

}

$arr = array(3,1,6,2,9,4,7,8,5);

<pre>1,2,3,4,5,6,7,8,9</pre>

 

=={{header|PicoLisp}}==

(let J (cdr Lst)

(for (I Lst (cdr I))

(setq I J J (cdr J))

(setq I (prior I Lst)) ) ) ) )

 

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

DECLARE A(0:9) FIXED STATIC INITIAL (5, 2, 7, 1, 9, 8, 6, 3, 4, 0);

 

END GNOME_SORT;

 

Results:

<pre>

</pre>

 

 

 

 

 

 

=={{header|PowerShell}}==

$size, $i, $j = $a.Count, 1, 2

while($i -lt $size) {

}

$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)

<b>Output:</b>

<pre>

3 8 11 19 21 36 60 63 80 87 100

</pre>

 

=={{header|Python}}==

i,j,size = 1,2,len(a)

while i < size:

>>> gnomesort([3,4,2,5,1,6])

[1, 2, 3, 4, 5, 6]

 

{

i <- 1

x

}

 

=={{header|Racket}}==

#lang racket

 

[else `(,ps ,n ,p . ,ns)]))]))]))

(gnome-sort2 '(3 2 1 4 5 6) <=)

 

=={{header|Raku}}==

{{Works with|rakudo|2016.03}}

 

my ($i, $j) = 1, 2;

while $i < @a {

}

}

 

my @n = (1..10).roll(20);

 

=={{header|Rascal}}==

 

public list[int] gnomeSort(a){

j += 1;}}}

return a;

 

An example output:

 

 

=={{header|REXX}}==

===version 1===

This REXX version uses an unity-based array &nbsp; (instead of a zero-based array).

call gen /*generate the @ stemmed array. */

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

if @.p<<=@.k then do; k= j; iterate; end /*order is OK so far. */

_= @.p; @.p= @.k; @.k= _ /*swap two @ entries. */

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

{{out|output|:}}

 

 

===version 2===

* 28.06.2014 Walter Pachl cf ooRexx version 2

* only style changes (reformatting) and adapt for ooRexx compatibility

End

Return

'''output'''

<pre>before sort

 

=={{header|Ring}}==

aList = [ 5, 6, 1, 2, 9, 14, 15, 7, 8, 97]

gnomeSort(aList)

i = j

j = j + 1 ok ok end

 

=={{header|Ruby}}==

def gnomesort!

i, j = 1, 2

ary = [7,6,5,9,8,4,3,1,2,0]

ary.gnomesort!

 

=={{header|Rust}}==

let len = a.len();

let mut i: usize = 1;

gnome_sort(&mut v);

println!("after: {:?}", v);

 

{{out}}

 

=={{header|Scala}}==

def gnomeSort(a: Array[Int]): Unit = {

var (i, j) = (1, 2)

}

}

 

=={{header|Scheme}}==

; arguments are in order or equal.

(define (gnome-sort-compar in-order input-list)

(gnome

(cdr p) ; Prev list shorter by one

#;1> (gnome-sort-compar <= '(98 36 2 78 5 81 32 90 73 21 94 28 53 25 10 99))

(2 5 10 21 25 28 32 36 53 73 78 81 90 94 98 99)

 

=={{header|Sidef}}==

method gnomesort {

var (i=1, j=2);

 

var ary = [7,6,5,9,8,4,3,1,2,0];

{{out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

 

=={{header|Smalltalk}}==

 

"Utility"

]

]

 

'''Testing'''

 

r := Random new.

o := OrderedCollection new.

gnomesort value: o.

 

 

=={{header|Swift}}==

var i = 1

var j = 2

print("before: \(array)")

gnomeSort(&array)

 

{{out}}

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}

 

 

=={{header|Ursala}}==

finding an item out of order, bubble it backwards to its

proper position and resume scanning forward from where it was.

 

@NiX ^=lx -+ # iteration

~&r?\~& @lNXrX ->llx2rhPlrPCTxPrtPX~&lltPlhPrCXPrX ~&ll&& @llPrXh not "p", # backward bubble

Most of the code is wasted on dull but unavoidable stack manipulations.

Here is a test program using the lexical partial order relation.

#cast %s

 

output:

<pre>

'adddeffffgghiiijjjjkkkkllnnooqsswww'

</pre>

 

=={{header|VBScript}}==

====Implementation====

dim i

dim j

x = y

y = temp

====Invocation====

dim b

 

a = array( now(), now()-1,now()+2)

b = gnomeSort( a )

 

====Output====

23, 89, 234, 345, 456, 456, 547, 567, 567, 568, 649, 2345, 5769

True, True, True, True, False, False, False, False

-45.99, -3, 1, 2, 2, 4, 67789

Note: All data in VBScript is of type Variant. Thus the code can sort many different types of data without code modification.

 

=={{header|Wren}}==

var size = a.count

var i = 1

}

 

 

for (asc in [true, false]) {

System.print("Sorting in %(asc ? "ascending" : "descending") order:\n")

var b = (asc) ? a : a.toList

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

System.print()

}

 

{{out}}

 

=={{header|XPL0}}==

 

proc GnomeSort(A(0..Size-1)); \Sort array A

GnomeSort(A, 10);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

 

=={{header|zkl}}==

i,j,size := 1,2,a.len();

while(i < size){

}//while

a

{{out}}

<pre>L(" "," "," ","T","a","e","h","i","i","s","s","s","t","t")</pre>