Sorting algorithms/Gnome sort: Difference between revisions

{{trans|Python}}

 

V i = 1

V j = 2

R a

 

 

{{out}}

 

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

GNOME CSECT

USING GNOME,R13 base register

PG DC CL125' ' buffer

REGEQU

{{out}}

<pre>

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program gnomeSort64.s */

.include "../includeARM64.inc"

 

 

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

INT i

 

Test(c,8)

Test(d,12)

{{out}}

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

 

=={{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|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386}}

 

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

 

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

Output:

<pre>

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

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program gnomeSort.s */

.include "../affichage.inc"

 

 

=={{header|Arturo}}==

 

i: 1

j: 2

]

 

 

{{out}}

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

 

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

I%=2

J%=2

ENDIF

UNTIL I%>Size%

 

=={{header|BCPL}}==

 

let gnomesort(A, len) be

gnomesort(array, length)

writes("Output: ") ; writearray(array, length) ; wrch('*N')

{{out}}

<pre>Input: 52 -5 -20 199 65 -3 190 25 9999 -5342

 

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

 

=={{header|Eiffel}}==

 

class

GNOME_SORT [G -> COMPARABLE]

end

 

Test:

class

APPLICATION

end

 

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

!

 

=={{header|FreeBASIC}}==

Used the task pseudo code as a base

' 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>unsort 4 -5 5 1 -3 -1 -2 -6 0 7 -4 6 2 -7 3

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=d91a871bd9f43cd9644c89baa3ee861a Click this link to run this code]'''

Dim siCount As Short

Dim siCounti As Short = 1

Return

 

Output:

<pre>

 

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

100 PROGRAM "GnomeSrt.bas"

110 RANDOMIZE

370 END IF

380 LOOP

 

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

 

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

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

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

<span style="color: #0000FF;">?</span><span style="color: #000000;">gnomeSort</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>

 

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

The [[#BASIC|BASIC]] example will work as-is if the array is declared in the same function as the sort. This example doesn't require that, but forces you to know your data type beforehand.

 

DIM i AS LONG, j AS LONG

i = 1

NEXT

CLOSE 1

 

Sample output:

 

=={{header|PowerShell}}==

function gnomesort($a) {

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

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

"$(gnomesort $array)"

<b>Output:</b>

<pre>

 

=={{header|PureBasic}}==

Protected Size = ArraySize(a()) + 1

Protected i = 1, j = 2

EndIf

Wend

 

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

 

=={{header|Quackery}}==

 

[ i^ 0 > if

[ dup i^ 1 - peek

swap i^ 1 - poke

-1 step ]

 

=={{header|R}}==

===Starting from 1===

{

i <- 1

x

}

 

===Starting from 2===

 

As R is 1-indexed, we need to make some minor adjustments to the given pseudo-code. To give some variety and to remove the previous solution's potentially redundant first run, we have chosen a different adjustment to the previous solution's. We have otherwise aimed to be faithful to the pseudo-code.

{

i <- 2

ints <- c(1, 10, 2, 5, -1, 5, -19, 4, 23, 0)

numerics <- c(1, -3.2, 5.2, 10.8, -5.7, 7.3, 3.5, 0, -4.1, -9.5)

 

{{out}}

 

=={{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.*/

end /*j*/; return

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

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

Implementation of the Gnome sort. Note this is an overengineered approach that performs many checks the real world would need but might obfuscate intent. As such the actual implementation is carefully labelled and the rest can be ignored except as interest dictates.

 

* GNOME(V) -- gnome sort of the numerical vector V.

*** HELPER FUNCTIONS ***********************************************************

prototype(v) ',' :S(FRETURN)F(RETURN)

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

 

The test script looks like this:

 

GNOME.TEST output = 'valid values...'

output = 'PASSED!'

 

 

=={{header|Swift}}==

var i = 1

var j = 2

print("before: \(array)")

gnomeSort(&array)

 

{{out}}

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}

 

 

=={{header|TI-83 BASIC}}==

=={{header|True BASIC}}==

{{trans|IS-BASIC}}

RANDOMIZE !RAMDOMZE TIMER en QBASIC

DIM array(-5 TO 12)

NEXT i

END SUB

 

 

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

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

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

 

=={{header|VBA}}==

Dim i As Integer: i = 1

Dim j As Integer: j = 2

Public Sub main()

Debug.Print Join(gnomeSort([{5, 3, 1, 7, 4, 1, 1, 20}]), ", ")

<pre>1, 1, 1, 3, 4, 5, 7, 20</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|Vlang}}==

{{trans|go}}

mut a := [170, 45, 75, -90, -802, 24, 2, 66]

println("before: $a")

j++

}

{{out}}

<pre>before: [170, 45, 75, -90, -802, 24, 2, 66]

 

=={{header|Wren}}==

var size = a.count

var i = 1

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>