Sorting algorithms/Gnome sort: Difference between revisions
m
→{{header|RPL}}: improved code
No edit summary |
m (→{{header|RPL}}: improved code) |
||
| (144 intermediate revisions by 67 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
[[Category:Sorting]]
{{Wikipedia|Gnome sort}}
Gnome sort is a sorting algorithm which is similar to [[Insertion sort]], except that moving an element to its proper place is accomplished by a series of swaps, as in [[Bubble Sort]].
Line 23 ⟶ 26:
'''done'''
;Task:
Implement the Gnome sort in your language to sort an array (or list) of numbers.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F gnomesort(&a)
V i = 1
V j = 2
L i < a.len
I a[i - 1] <= a[i]
i = j
j++
E
swap(&a[i - 1], &a[i])
i--
I i == 0
i = j
j++
R a
print(gnomesort(&[3, 4, 2, 5, 1, 6]))</syntaxhighlight>
{{out}}
<pre>
[1, 2, 3, 4, 5, 6]
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Gnome sort - Array base 0 - 15/04/2020
GNOME CSECT
USING GNOME,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R6,1 i=1
LA R7,2 j=2
DO WHILE=(C,R6,LT,NN) while i<nn
LR R1,R6 i
SLA R1,2 ~
LA R8,TT-4(R1) @tt(i-1)
LA R9,TT(R1) @tt(i)
L R2,0(R8) tt(i-1)
IF C,R2,LE,0(R9) THEN if tt(i-1)<=tt(i) then
LR R6,R7 i=j
LA R7,1(R7) j=j+1
ELSE , else
L R4,0(R8) t=tt(i-1)
L R3,0(R9) tt(i)
ST R3,0(R8) tt(i-1)=tt(i)
ST R4,0(R9) tt(i)=t
BCTR R6,0 i=i-1
IF LTR,R6,Z,R6 THEN if i=0 then
LR R6,R7 i=j
LA R7,1(R7) j=j+1
ENDIF , endif
ENDIF , endif
ENDDO , endwhile
LA R10,PG @buffer
LA R7,TT @tt
LA R6,1 i=1
DO WHILE=(C,R6,LE,NN) do i=1 to nn
L R2,0(R7) tt(i)
XDECO R2,XDEC edit tt(i)
MVC 0(5,R10),XDEC+7 output tt(i)
LA R10,5(R10) @buffer
LA R7,4(R7) @tt++
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
TT DC F'557',F'5143',F'5432',F'6798',F'2874'
DC F'3499',F'6949',F'4992',F'2555',F'4175'
DC F'8264',F'3522',F'2045',F'2963',F'2625'
DC F'-764',F'1845',F'1485',F'5792',F'7562'
DC F'5044',F'3598',F'6817',F'4891',F'4350'
NN DC A((NN-TT)/L'TT) number of items of tt
XDEC DS CL12 temp for xdeco
PG DC CL125' ' buffer
REGEQU
END GNOME</syntaxhighlight>
{{out}}
<pre>
-764 557 1485 1845 2045 2555 2625 2874 2963 3499 3522 3598 4175 4350 4891 4992 5044 5143 5432 5792 6798 6817 6949 7562 8264
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program gnomeSort64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
TableNumber: .quad 1,3,6,2,5,9,10,8,4,7
#TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableNumber // address number table
mov x1,0 // first element
mov x2,NBELEMENTS // number of élements
bl gnomeSort
ldr x0,qAdrTableNumber // address number table
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,1 // sorted ?
beq 1f
ldr x0,qAdrszMessSortNok // no !! error sort
bl affichageMess
b 100f
1: // yes
ldr x0,qAdrszMessSortOk
bl affichageMess
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
qAdrszMessSortOk: .quad szMessSortOk
qAdrszMessSortNok: .quad szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,0
ldr x4,[x0,x2,lsl 3]
1:
add x2,x2,1
cmp x2,x1
bge 99f
ldr x3,[x0,x2, lsl 3]
cmp x3,x4
blt 98f
mov x4,x3
b 1b
98:
mov x0,0 // not sorted
b 100f
99:
mov x0,1 // sorted
100:
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* gnome sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
gnomeSort:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
sub x2,x2,1 // compute end index n - 1
add x3,x1,1 // index i
add x7,x1,2 // index j
1: // start loop 1
cmp x3,x2
bgt 100f
sub x4,x3,1 //
ldr x5,[x0,x3,lsl 3] // load value A[j]
ldr x6,[x0,x4,lsl 3] // load value A[j+1]
cmp x5,x6 // compare value
bge 2f
str x6,[x0,x3,lsl 3] // if smaller inversion
str x5,[x0,x4,lsl 3]
sub x3,x3,1 // i = i - 1
cmp x3,x1
bne 1b // loop 1
2:
mov x3,x7 // i = j
add x7,x7,1 // j = j + 1
b 1b // loop 1
100:
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
ldr x0,[x2,x3,lsl 3]
ldr x1,qAdrsZoneConv
bl conversion10S // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
add x3,x3,1
cmp x3,NBELEMENTS - 1
ble 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
mov x0,x2
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC GnomeSort(INT ARRAY a INT size)
INT i,j,tmp
i=1 j=2
WHILE i<size
DO
IF a(i-1)<=a(i) THEN
i=j j==+1
ELSE
tmp=a(i-1) a(i-1)=a(i) a(i)=tmp
i==-1
IF i=0 THEN
i=j j==+1
FI
FI
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
GnomeSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Gnome_sort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ActionScript}}==
<
{
var pos:uint = 0;
Line 41 ⟶ 384:
}
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 Gnome_Sort(Item : in out Collection);</
<
procedure Swap(Left, Right : in out Element_Type) is
Temp : Element_Type := Left;
Line 76 ⟶ 419:
end if;
end loop;
end Gnome_Sort;</
Usage example:
<
with Ada.Text_Io; use Ada.Text_Io;
Line 96 ⟶ 439:
end loop;
New_Line;
end Gnome_Sort_Test;</
=={{header|ALGOL 68}}==
Line 103 ⟶ 446:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards
<
PROC inplace gnome sort = (REF[]SORTSTRUCT list)REF[]SORTSTRUCT:
Line 124 ⟶ 467:
in place gnome sort(LOC[LWB seq: UPB seq]SORTSTRUCT:=seq);
[]SORTSTRUCT
print((gnome sort(
</syntaxhighlight>
Output:
<pre>
-40 +0 +0 +1 +2 +9 +77 +1701
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">
begin % gnome sort %
% gnome sorts in-place a, a must have bounds 1 :: size %
procedure gnomeSort( integer array a ( * ); integer value size ) ;
begin
integer i, j;
i := 2;
j := 3;
while i <= size do begin
if a( i - 1 ) <= a( i ) then begin
i := j;
j := j + 1
end
else begin
integer swap;
swap := a( i - 1 );
a( i - 1 ) := a( i );
a( i ) := swap;
i := i - 1;
if i = 1 then begin
i := j;
j := j + 1
end if_i_eq_1
end if_a_i_minus_1_le_a_i__
end while_i_lt_size
end gnomeSort ;
begin % test gnomeSort %
integer array numbers ( 1 :: 11 );
integer nPos;
% constructy an array of integers and sort it %
nPos := 1;
for v := 4, 65, 2, 31, 0, 99, 2, 8, 3, 782, 1 do begin
numbers( nPos ) := v;
nPos := nPos + 1
end for_v ;
gnomeSort( numbers, 11 );
% print the sorted array %
for n := 1 until 11 do writeon( i_w := 1, s_w := 0, " ", numbers( n ) )
end tests
end.
</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 3 4 8 31 65 99 782
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program gnomeSort.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#TableNumber: .int 1,3,6,2,5,9,10,8,4,7
TableNumber: .int 10,9,8,7,6,5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrTableNumber @ address number table
mov r1,#0 @ first element
mov r2,#NBELEMENTS @ number of élements
bl gnomeSort
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 1f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
1: @ yes
ldr r0,iAdrszMessSortOk
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* gnome Sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element */
/* r2 contains the number of element */
gnomeSort:
push {r1-r9,lr} @ save registers
sub r2,r2,#1 @ compute end index = n - 1
add r3,r1,#1 @ index i
add r7,r1,#2 @ j
1: @ start loop 1
cmp r3,r2
bgt 100f
sub r4,r3,#1
ldr r5,[r0,r3,lsl #2] @ load value A[j]
ldr r6,[r0,r4,lsl #2] @ load value A[j-1]
cmp r5,r6 @ compare value
bge 2f
str r6,[r0,r3,lsl #2] @ if smaller inversion
str r5,[r0,r4,lsl #2]
sub r3,r3,#1 @ i = i - 1
cmp r3,r1
moveq r3,r7 @ if i = 0 i = j
addeq r7,r7,#1 @ if i = 0 j = j+1
b 1b @ loop 1
2:
mov r3,r7 @ i = j
add r7,r7,#1 @ j = j + 1
b 1b @ loop 1
100:
pop {r1-r9,lr}
bx lr @ return
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsZoneConv @
bl conversion10S @ décimal conversion
ldr r0,iAdrsMessResult
ldr r1,iAdrsZoneConv @ insert conversion
bl strInsertAtCharInc
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
mov r0,r2
100:
pop {r0-r3,lr}
bx lr
iAdrsZoneConv: .int sZoneConv
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">gnomeSort: function [items][
i: 1
j: 2
arr: new items
while [i < size arr][
if? arr\[i-1] =< arr\[i] [
i: j
j: j + 1
]
else [
tmp: arr\[i]
arr\[i]: arr\[i-1]
arr\[i-1]: tmp
i: i-1
if i=0 [
i: j
j: j + 1
]
]
]
return arr
]
print gnomeSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</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")
Line 153 ⟶ 740:
sorted .= "," . a%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}</syntaxhighlight>
=={{header|AWK}}==
AWK arrays can be passed as parameters, but not returned, so they are usually global.
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.
<syntaxhighlight lang="awk">#!/usr/bin/awk -f
BEGIN {
d[1] = 3.0
d[2] = 4.0
d[3] = 1.0
d[4] = -8.4
d[5] = 7.2
d[6] = 4.0
d[7] = 1.0
d[8] = 1.2
showD("Before: ")
gnomeSortD()
showD("Sorted: ")
exit
}
function gnomeSortD( i) {
for (i = 2; i <= length(d); i++) {
if (d[i] < d[i-1]) gnomeSortBackD(i)
}
}
function gnomeSortBackD(i, t) {
for (; i > 1 && d[i] < d[i-1]; i--) {
t = d[i]
d[i] = d[i-1]
d[i-1] = t
}
}
function showD(p, i) {
printf p
for (i = 1; i <= length(d); i++) {
printf d[i] " "
}
print ""
}
</syntaxhighlight>
Example output:
Before: 3 4 1 -8.4 7.2 4 1 1.2
Sorted: -8.4 1 1 1.2 3 4 4 7.2
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="basic">arraybase 1
global array
dim array(15)
a = array[?,]
b = array[?]
for i = a to b
array[i] = int(rand * 100)
next i
print "unsort ";
for i = a to b
print rjust(array[i], 4);
next i
call gnomeSort(array)
print chr(10); " sort ";
for i = a to b
print rjust(array[i], 4);
next i
end
subroutine gnomeSort (array)
i = array[?,] + 1
j = i + 1
while i <= array[?]
if array[i - 1] <= array[i] then
i = j
j += 1
else
temp = array[i - 1]
array[i - 1] = array[i]
array[i] = temp
i -= 1
if i = array[?,] then
i = j
j += 1
end if
end if
end while
end subroutine</syntaxhighlight>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic">DEF PROC_GnomeSort1(Size%)
I%=2
J%=2
REPEAT
IF data%(J%-1) <=data%(J%) THEN
I%+=1
J%=I%
ELSE
SWAP data%(J%-1),data%(J%)
J%-=1
IF J%=1 THEN
I%+=1
J%=I%
ENDIF
ENDIF
UNTIL I%>Size%
ENDPROC</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{works with|QBasic}}
{{trans|IS-BASIC}}
<syntaxhighlight lang="qbasic">100 RANDOMIZE TIMER
110 DIM array(18)
120 ' Init Array
130 FOR i = 0 TO UBOUND(array)
140 array(i) = INT(RND(1)*98)+1
150 NEXT i
160 PRINT "unsort: "; : GOSUB 200
170 GOSUB 260 : ' gnomeSort
180 PRINT " sort: "; : GOSUB 200
190 END
200 ' Write Array
210 FOR i = 0 TO UBOUND(array)
220 PRINT array(i);
230 NEXT i
240 PRINT
250 RETURN
260 ' gnomeSort
270 i = 1
280 j = i+1
290 WHILE i <= UBOUND(array)
300 IF array(i-1) <= array(i) THEN
310 i = j : j = j+1
320 ELSE
330 t = array(i-1) : array(i-1) = array(i) : array(i) = t : ' swap
340 i = i-1
350 IF i = 0 THEN i = j : j = j+1
360 ENDIF
370 WEND
380 RETURN</syntaxhighlight>
==={{header|FreeBASIC}}===
Used the task pseudo code as a base
<syntaxhighlight lang="freebasic">' version 21-10-2016
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Sub gnomesort(gnome() As Long)
' sort from lower bound to the highter bound
' array's can have subscript range from -2147483648 to +2147483647
Dim As Long lb = LBound(gnome)
Dim As Long ub = UBound(gnome)
Dim As Long i = lb +1, j = lb +2
While i < (ub +1)
' replace "<=" with ">=" for downwards sort
If gnome(i -1) <= gnome(i) Then
i = j
j += 1
Else
Swap gnome(i -1), gnome(i)
i -= 1
If i = lb Then
i = j
j += 1
End If
End If
Wend
End Sub
' ------=< MAIN >=------
Dim As Long i, array(-7 To 7)
Dim As Long a = LBound(array), b = UBound(array)
Randomize Timer
For i = a To b : array(i) = i : Next
For i = a To b ' little shuffle
Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
Print "unsort ";
For i = a To b : Print Using "####"; array(i); : Next : Print
gnomesort(array()) ' sort the array
Print " sort ";
For i = a To b : Print Using "####"; array(i); : Next : Print
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>unsort 4 -5 5 1 -3 -1 -2 -6 0 7 -4 6 2 -7 3
sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre>
==={{header|Gambas}}===
'''[https://gambas-playground.proko.eu/?gist=d91a871bd9f43cd9644c89baa3ee861a Click this link to run this code]'''
<syntaxhighlight lang="gambas">Public Sub Main()
Dim siCount As Short
Dim siCounti As Short = 1
Dim siCountj As Short = 2
Dim siToSort As Short[] = [249, 28, 111, 36, 171, 98, 29, 448, 44, 147, 154, 46, 102, 183, 24]
Print "To sort: - ";
GoSub Display
While siCounti < siToSort.Count
If siToSort[siCounti - 1] <= siToSort[siCounti] Then
siCounti = siCountj
Inc siCountj
Else
Swap siToSort[siCounti - 1], siToSort[siCounti]
Dec siCounti
If siCounti = 0 Then
siCounti = siCountj
Inc siCountj
Endif
Endif
Wend
Print "Sorted: - ";
GoSub Display
Return
'--------------------------------------------
Display:
For siCount = 0 To siToSort.Max
Print Format(Str(siToSort[siCount]), "####");
If siCount <> siToSort.max Then Print ",";
Next
Print
Return
End</syntaxhighlight>
Output:
<pre>To sort: - 249, 28, 111, 36, 171, 98, 29, 448, 44, 147, 154, 46, 102, 183, 24
Sorted: - 24, 28, 29, 36, 44, 46, 98, 102, 111, 147, 154, 171, 183, 249, 448</pre>
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
{{works with|Just BASIC}}
<syntaxhighlight lang="qbasic">100 REM GnomeSrt.bas
110 RANDOMIZE TIMER 'remove it for Just BASIC
120 DIM ARRAY(18)
130 ' Init Array
140 FOR I = 0 TO 18
150 LET ARRAY(I) = INT(RND(1)*98)+1
160 NEXT I
170 PRINT "unsort: "; : GOSUB 210
180 GOSUB 270 : REM gnomeSort
190 PRINT " sort: "; : GOSUB 210
200 END
210 ' Write Array
220 FOR I = 0 TO 18
230 PRINT ARRAY(I);
240 NEXT I
250 PRINT
260 RETURN
270 ' gnomeSort
280 LET I = 1
290 LET J = I+1
300 WHILE I <= 18
310 IF ARRAY(I-1) <= ARRAY(I) THEN LET I = J : LET J = J+1 : GOTO 330
320 IF ARRAY(I-1) > ARRAY(I) THEN LET T = ARRAY(I-1) : LET ARRAY(I-1) = ARRAY(I) : LET ARRAY(I) = T : LET I = I-1 : IF I = 0 THEN LET I = J : LET J = J+1
330 WEND
340 RETURN</syntaxhighlight>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">
100 PROGRAM "GnomeSrt.bas"
110 RANDOMIZE
120 NUMERIC ARRAY(-5 TO 12)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL GNOMESORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180 FOR I=LBOUND(A) TO UBOUND(A)
190 LET A(I)=RND(98)+1
200 NEXT
210 END DEF
220 DEF WRITE(REF A)
230 FOR I=LBOUND(A) TO UBOUND(A)
240 PRINT A(I);
250 NEXT
260 PRINT
270 END DEF
280 DEF GNOMESORT(REF A)
290 LET I=LBOUND(A)+1:LET J=I+1
300 DO WHILE I<=UBOUND(A)
310 IF A(I-1)<=A(I) THEN
320 LET I=J:LET J=J+1
330 ELSE
340 LET T=A(I-1):LET A(I-1)=A(I):LET A(I)=T
350 LET I=I-1
360 IF I=LBOUND(A) THEN LET I=J:LET J=J+1
370 END IF
380 LOOP
390 END DEF</syntaxhighlight>
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
{{works with|QBasic}}
{{trans|GW-BASIC}}
<syntaxhighlight lang="qbasic">100 CLS
110 U = 8
120 DIM A(U+1)
130 FOR I = 0 TO U
140 A(I) = INT(RND(1)*98)
150 NEXT I
160 PRINT "unsort: "; : GOSUB 200
170 GOSUB 260 : REM gnomeSort
180 PRINT " sort: "; : GOSUB 200
190 END
200 REM Write Array
210 FOR I = 0 TO U
220 PRINT A(I);
230 NEXT I
240 PRINT
250 RETURN
260 REM gnomeSort
270 I = 1
280 J = I+1
290 IF I <= U THEN IF A(I-1) <= A(I) THEN I = J : J = J+1 : GOTO 290
300 IF I > U THEN RETURN
310 IF A(I-1) > A(I) THEN T = A(I-1) : A(I-1) = A(I) : A(I) = T : I = I-1 : IF I = 0 THEN I = J : J = J+1
320 GOTO 290</syntaxhighlight>
==={{header|Minimal BASIC}}===
<syntaxhighlight lang="qbasic">10 REM Rosetta Code problem: https://rosettacode.org/wiki/Sorting_algorithms/Gnome_sort
20 REM by Jjuanhdez, 10/2023
100 RANDOMIZE
110 LET U = 8
120 DIM A(9)
130 FOR I = 0 TO U
140 LET A(I) = INT(RND*98)
150 NEXT I
160 PRINT "UNSORT: ";
170 GOSUB 220
180 GOSUB 280
190 PRINT " SORT: ";
200 GOSUB 220
210 STOP
220 REM WRITE ARRAY
230 FOR I = 0 TO U
240 PRINT A(I);
250 NEXT I
260 PRINT
270 RETURN
280 REM GNOMESORT
290 LET I = 1
300 LET J = I+1
310 IF I <= U THEN 350
320 IF I > U THEN 190
330 IF A(I-1) > A(I) THEN 400
340 GOTO 310
350 IF A(I-1) <= A(I) THEN 370
360 GOTO 320
370 LET I = J
380 LET J = J+1
390 GOTO 310
400 LET T = A(I-1)
410 LET A(I-1) = A(I)
420 LET A(I) = T
430 LET I = I-1
440 IF I = 0 THEN 460
450 GOTO 310
460 LET I = J
470 LET J = J+1
480 GOTO 310
490 END</syntaxhighlight>
{{out}}
<pre>UNSORT: 9 86 63 25 19 57 3 39 75
SORT: 3 9 19 25 39 57 63 75 86</pre>
==={{header|PowerBASIC}}===
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.
<syntaxhighlight lang="powerbasic">SUB gnomeSort (a() AS LONG)
DIM i AS LONG, j AS LONG
i = 1
j = 2
WHILE (i < UBOUND(a) + 1)
IF (a(i - 1) <= a(i)) THEN
i = j
INCR j
ELSE
SWAP a(i - 1), a(i)
DECR i
IF 0 = i THEN
i = j
INCR j
END IF
END IF
WEND
END SUB
FUNCTION PBMAIN () AS LONG
DIM n(9) AS LONG, x AS LONG
RANDOMIZE TIMER
OPEN "output.txt" FOR OUTPUT AS 1
FOR x = 0 TO 9
n(x) = INT(RND * 9999)
PRINT #1, n(x); ",";
NEXT
PRINT #1,
gnomeSort n()
FOR x = 0 TO 9
PRINT #1, n(x); ",";
NEXT
CLOSE 1
END FUNCTION</syntaxhighlight>
Sample output:
7426 , 7887 , 8297 , 2671 , 7586 , 7160 , 1195 , 665 , 9352 , 6199 ,
665 , 1195 , 2671 , 6199 , 7160 , 7426 , 7586 , 7887 , 8297 , 9352 ,
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure GnomeSort(Array a(1))
Protected Size = ArraySize(a()) + 1
Protected i = 1, j = 2
While i < Size
If a(i - 1) <= a(i)
;for descending SORT, use >= for comparison
i = j
j + 1
Else
Swap a(i - 1), a(i)
i - 1
If i = 0
i = j
j + 1
EndIf
EndIf
Wend
EndProcedure</syntaxhighlight>
==={{header|QBasic}}===
{{trans|IS-BASIC}}
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
{{works with|VB-DOS|1.0}}
{{works with|QB64|1.1}}
{{works with|PDS|7.1}}
{{works with|True BASIC}}
<syntaxhighlight lang="qbasic">RANDOMIZE TIMER 'RANDOMIZE for True BASIC
DIM array(-5 TO 12)
CALL iniciarray(array())
PRINT "unsort: ";
CALL escritura(array())
CALL gnomeSort(array())
PRINT
PRINT " sort: ";
CALL escritura(array())
END
SUB escritura (array())
FOR i = LBOUND(array) TO UBOUND(array)
PRINT array(i);
NEXT i
PRINT
END SUB
SUB gnomeSort (array())
LET i = LBOUND(array) + 1
LET j = i + 1
DO WHILE i <= UBOUND(array)
IF array(i - 1) <= array(i) THEN
LET i = j
LET j = j + 1
ELSE
LET T = array(i - 1)
LET array(i - 1) = array(i)
LET array(i) = T
LET i = i - 1
IF i = LBOUND(array) THEN
LET i = j
LET j = j + 1
END IF
END IF
LOOP
END SUB
SUB iniciarray (array())
FOR i = LBOUND(array) TO UBOUND(array)
LET array(i) = (RND * 98) + 1
NEXT i
END SUB</syntaxhighlight>
==={{header|QuickBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
{{trans|C}}
<
'...more code...
sort:
Line 177 ⟶ 1,270:
end if
end if
wend</
==={{header|
{{trans|Minimal BASIC}}
<syntaxhighlight lang="qbasic">100 CLS
110 LET U = 8
120 ARRAY A
130 FOR I = 0 TO U
140 LET A(I
150 NEXT I
160 PRINT "UNSORT: ";
170 GOSUB 220
180 GOSUB 280
190 PRINT " SORT: ";
200 GOSUB 220
210 STOP
220 REM WRITE ARRAY
230 FOR I = 0 TO U
240 PRINT A(I); " ";
250 NEXT I
260 PRINT
270 RETURN
280 REM GNOMESORT
290 LET I = 1
300 LET J = I+1
310 IF I <= U THEN 350
320 IF I > U THEN 190
330 IF A(I-1) > A(I) THEN 400
340 GOTO 310
350 IF A(I-1) <= A(I) THEN 370
360 GOTO 320
370 LET I = J
380 LET J = J+1
390 GOTO 310
400 LET T = A(I-1)
410 LET A(I-1) = A(I)
420 LET A(I) = T
430 LET I = I-1
440 IF I = 0 THEN 460
450 GOTO 310
460 LET I = J
470 LET J = J+1
480 GOTO 310
490 END</syntaxhighlight>
{{out}}
<pre>Same as Minimal BASIC entry.</pre>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
<syntaxhighlight lang="vb"> dim A(18)
[initArray]
for i = 0 to 18
A(i) = int(rnd(1)*98)+1
next i
print "unsort: ";
gosub [writeArray]
gosub [gnomeSort]
print " sort: ";
gosub [writeArray]
end
[writeArray]
for i = 0 to 18
print A(i); " ";
next i
print
return
[gnomeSort]
i = 1
j = i+1
while i <= 18
if A(i-1) <= A(i) then
i = j
j = j+1
else
t = A(i-1) : A(i-1) = A(i) : A(i) = t
i = i-1
if i = 0 then i = j : j = j+1
end if
wend
return</syntaxhighlight>
==={{header|TI-83 BASIC}}===
Store input into L<sub>1</sub>, run prgmSORTGNOM, output will be in L<sub>2</sub>.
:1→P
:L<sub>1</sub>→L<sub>2</sub>
:While P<dim(L<sub>2</sub>)
:If PP=1
:Then
:P+1→P
:Else
:If L<sub>2</sub>(P)≥L<sub>2</sub>(P-1)
:Then
:P+1→P
:Else
:L<sub>2</sub>(P)→Q
:L<sub>2</sub>(P-1)→L<sub>2</sub>(P)
:Q→L<sub>2</sub>(P-1)
:P-1→P
:End
:End
:End
:If L<sub>2</sub>(dim(L<sub>2</sub>))<L<sub>2</sub>(dim(L<sub>2</sub>)-1)
:Then
:L<sub>2</sub>(dim(L<sub>2</sub>))→Q
:L<sub>2</sub>(dim(L<sub>2</sub>)-1)→L<sub>2</sub>(dim(L<sub>2</sub>))
:Q→L<sub>2</sub>(dim(L<sub>2</sub>)-1)
:End
:DelVar P
:DelVar Q
:Return
==={{header|True BASIC}}===
{{trans|IS-BASIC}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">RANDOMIZE !RAMDOMIZE TIMER en QBASIC
DIM array(-5 TO 12)
CALL iniciarray(array())
PRINT "unsort: ";
CALL escritura(array())
CALL gnomeSort(array())
PRINT
PRINT " sort: ";
CALL escritura(array())
END
SUB escritura (array())
FOR i = LBOUND(array) TO UBOUND(array)
PRINT array(i);
NEXT i
PRINT
END SUB
SUB gnomeSort (array())
LET i = LBOUND(array) + 1
LET j = i + 1
DO WHILE i <= UBOUND(array)
IF array(i - 1) <= array(i) THEN
LET i = j
LET j = j + 1
ELSE
LET T = array(i - 1)
LET array(i - 1) = array(i)
LET array(i) = T
LET i = i - 1
IF i = LBOUND(array) THEN
LET i = j
LET j = j + 1
END IF
END IF
LOOP
END SUB
SUB iniciarray (array())
FOR i = LBOUND(array) TO UBOUND(array)
LET array(i) = (RND * 98) + 1
NEXT i
END SUB</syntaxhighlight>
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="text">PRINT "Gnome sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
PROC _Gnomesort (n)
PROC _ShowArray (n)
PRINT
END
_Gnomesort PARAM (1) ' Gnome sort
LOCAL (2)
b@=1
c@=2
DO WHILE b@ < a@
IF @(b@-1) > @(b@) THEN
PROC _Swap (b@, b@-1)
b@ = b@ - 1
IF b@ THEN
CONTINUE
ENDIF
ENDIF
b@ = c@
c@ = c@ + 1
LOOP
RETURN
_Swap PARAM(2) ' Swap two array elements
PUSH @(a@)
@(a@) = @(b@)
@(b@) = POP()
RETURN
_InitArray ' Init example array
PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
FOR i = 0 TO 9
@(i) = POP()
NEXT
RETURN (i)
_ShowArray PARAM (1) ' Show array subroutine
FOR i = 0 TO a@-1
PRINT @(i),
NEXT
PRINT
RETURN</syntaxhighlight>
==={{header|VBA}}===
{{trans|Phix}}<syntaxhighlight lang="vb">Private Function gnomeSort(s As Variant) As Variant
Dim i As Integer: i = 1
Dim j As Integer: j = 2
Dim tmp As Integer
Do While i < UBound(s)
If s(i) <= s(i + 1) Then
i = j
j = j + 1
Else
tmp = s(i)
s(i) = s(i + 1)
s(i + 1) = tmp
i = i - 1
If i = 0 Then
i = j
j = j + 1
End If
End If
Loop
gnomeSort = s
End Function
Public Sub main()
Debug.Print Join(gnomeSort([{5, 3, 1, 7, 4, 1, 1, 20}]), ", ")
End Sub</syntaxhighlight>{{out}}
<pre>1, 1, 1, 3, 4, 5, 7, 20</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="vb">dim array(15)
a = 0
b = arraysize(array(),1)
print "unsort: ";
for i = a to b
array(i) = int(ran(98))+1
print array(i), " ";
next i
print "\n sort: ";
gnomeSort(array())
for i = a to b
print array(i), " ";
next i
print "\n"
end
sub gnomeSort(array())
local ub, ul, i, j, temp
lb = 0 : ub = arraysize(array(),1)
i = lb +1 : j = lb +2
while i <= ub
// replace "<=" with ">=" for downwards sort
if array(i -1) <= array(i) then
i = j
j = j + 1
else
temp = array(i -1)
array(i -1) = array(i)
array(i) = temp
i = i - 1
if i = lb then
i = j
j = j + 1
fi
fi
wend
end sub</syntaxhighlight>
=={{header|Batch File}}==
{{works with|Windows NT}}
<syntaxhighlight lang="dos">@ECHO OFF
SETLOCAL EnableExtensions EnableDelayedExpansion
:: GnomeSort.cmd in WinNT Batch using pseudo array.
:: Set the number of random elements to sort.
SET numElements=100
:: Decrement numElements for use in zero-based loops as in (0, 1, %numElements% - 1).
SET /A tmpElements=%numElements% - 1
:: Create array of random numbers and output to file.
ECHO GnomeSort Random Input 0 to %tmpElements%:>%~n0.txt
FOR /L %%X IN (0, 1, %tmpElements%) DO (
SET array[%%X]=!RANDOM!
ECHO !array[%%X]!>>%~n0.txt
)
:GnomeSort
:: Initialize the pointers i-1, i, and j.
SET gs1=0
SET gs2=1
SET gs3=2
:GS_Loop
:: Implementing a WHILE loop in WinNT batch using GOTO. It only executes
:: if the condition is true and continues until the condition is false.
:: First, display [i-1][j - 2] to the Title Bar.
SET /A gsTmp=%gs3% - 2
TITLE GnomeSort:[%gs1%][%gsTmp%] of %tmpElements%
:: ...then start Main Loop. It's a direct implementation of the
:: pseudo code supplied by Rosetta Code. I had to add an additional
:: pointer to represent i-1, because of limitations in WinNT Batch.
IF %gs2% LSS %numElements% (
REM if i-1 <= i advance pointers to next unchecked element, then loop.
IF !array[%gs1%]! LEQ !array[%gs2%]! (
SET /A gs1=%gs3% - 1
SET /A gs2=%gs3%
SET /A gs3=%gs3% + 1
) ELSE (
REM ... else swap i-1 and i, decrement pointers to check previous element, then loop.
SET gsTmp=!array[%gs1%]!
SET array[%gs1%]=!array[%gs2%]!
SET array[%gs2%]=!gsTmp!
SET /A gs1-=1
SET /A gs2-=1
REM if first element has been reached, set pointers to next unchecked element.
IF !gs2! EQU 0 (
SET /A gs1=%gs3% - 1
SET /A gs2=%gs3%
SET /A gs3=%gs3% + 1
)
)
GOTO :GS_Loop
)
TITLE GnomeSort:[%gs1%][%gsTmp%] - Done!
:: write sorted elements out to file
ECHO.>>%~n0.txt
ECHO GnomeSort Sorted Output 0 to %tmpElements%:>>%~n0.txt
FOR /L %%X IN (0, 1, %tmpElements%) DO ECHO !array[%%X]!>>%~n0.txt
ENDLOCAL
EXIT /B 0</syntaxhighlight>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
let gnomesort(A, len) be
$( let i=1 and j=2 and t=?
while i < len
test A!(i-1) <= A!i
$( i := j
j := j + 1
$)
or
$( t := A!(i-1)
A!(i-1) := a!i
A!i := t
i := i - 1
if i = 0
$( i := j
j := j + 1
$)
$)
$)
let writearray(A, len) be
for i=0 to len-1 do
writed(A!i, 6)
let start() be
$( let array = table 52, -5, -20, 199, 65, -3, 190, 25, 9999, -5342
let length = 10
writes("Input: ") ; writearray(array, length) ; wrch('*N')
gnomesort(array, length)
writes("Output: ") ; writearray(array, length) ; wrch('*N')
$)</syntaxhighlight>
{{out}}
<pre>Input: 52 -5 -20 199 65 -3 190 25 9999 -5342
Output: -5342 -20 -5 -3 25 52 65 190 199 9999</pre>
=={{header|C}}==
This algorithm sorts in place modifying the passed ''array'' (of <code>n</code> integer numbers).
<
{
int i=1, j=2, t;
Line 213 ⟶ 1,675:
}
# undef swap
}</
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">
public static void gnomeSort(int[] anArray)
{
while (first < anArray.Length)
{
if (anArray[first - 1] <= anArray[first])
{
first = second;
second++;
}
else
{
int tmp = anArray[first - 1];
anArray[first - 1] = anArray[first];
anArray[first] = tmp;
first -= 1;
if (first == 0)
{
first = 1;
second = 2;
}
}
}
}
</syntaxhighlight>
=={{header|C++}}==
Uses C++11. Compile with
g++ -std=c++11 gnome.cpp
<
#include <iterator>
#include <iostream>
template<typename RandomAccessIterator>
void
while (i < end) {
if (!(*i < *(i - 1)
i = j;
++j;
Line 257 ⟶ 1,728:
std::iter_swap(i - 1, i);
--i;
if (i == begin) {
i = j;
++j;
Line 263 ⟶ 1,734:
}
}
}
int main() {
int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
gnome_sort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}</syntaxhighlight>
Output:
<pre>
-199 -52 2 3 33 56 99 100 177 200
</pre>
=={{header|Clojure}}==
{{trans|Haskell}}
<
([c] (gnomesort c <))
([c pred]
Line 278 ⟶ 1,760:
(recur (concat x (list y1)) ys)))))))
(println (gnomesort [3 1 4 1 5 9 2 6 5]))</
=={{header|COBOL}}==
Procedure division stuff only.
<
C-000.
DISPLAY "SORT STARTING".
Line 311 ⟶ 1,793:
E-999.
EXIT.</
=={{header|Common Lisp}}==
<
(do ((position (min 1 length)))
((eql length position) array)
Line 326 ⟶ 1,808:
(aref array (1- position)))
(decf position))
(t (incf position)))))</
=={{header|D}}==
<
void gnomeSort(T)(T arr) {
Line 347 ⟶ 1,829:
}
}
void main() {
Line 353 ⟶ 1,834:
gnomeSort(a);
writeln(a);
}</
=={{header|Delphi}}==
Line 359 ⟶ 1,840:
Static array is an arbitrary-based array of fixed length
<
{$APPTYPE CONSOLE}
Line 417 ⟶ 1,898:
Writeln;
Readln;
end.</
Output:
<pre>
Line 425 ⟶ 1,906:
=={{header|DWScript}}==
<
var
i, j : Integer;
Line 462 ⟶ 1,943:
Print(Format('%3d ', [a[i]]));
PrintLn('}');
</syntaxhighlight>
Ouput :
<pre>
Line 471 ⟶ 1,952:
=={{header|E}}==
<
var size := array.size()
var i := 1
Line 490 ⟶ 1,971:
}
}
}</
<
# value: [7, 9, 4, 2, 1, 3, 6, 5, 0, 8].diverge()
? gnomeSort(a)
? a
# value: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].diverge()</
=={{header|
{{trans|Lua}}
<syntaxhighlight>
proc sort . d[] .
i = 2
j = 3
while i <= len d[]
if d[i - 1] <= d[i]
i = j
j += 1
else
swap d[i - 1] d[i]
i -= 1
if i = 1
i = j
j += 1
.
.
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
sort data[]
print data[]
</syntaxhighlight>
=={{header|EDSAC order code}}==
This code conforms to the original description of gnome sort, in which it's assumed that the gnome can't remember anything and has to move one step at a time (cf. the alternative name "stupid sort"). As pointed out on the Discussion page, the RC task description introduces an optimization that credits the gnome with a memory. The sample array is copied from the Scheme solution.
<syntaxhighlight lang="edsac">
[Gnome sort - Rosetta Code
EDSAC program (Initial Orders 2) to read and sort an array
of 17-bit integers, using gnome sort.
Values are read from tape, preceded by an integer count.]
[Arrange the storage]
T45K P100F [H parameter: library subroutine R4 to read integer]
T46K P200F [N parameter: modified library s/r P7 to print integer]
T47K P300F [M parameter: main routine]
T51K P500F [G parameter: subroutine for gnome sort]
T55K P700F [V parameter: storage for values]
[Library subroutine M3, runs at load time and is then overwritten.
Prints header; here, last character sets teleprinter to figures.]
PF GK IF AF RD LF UF OF E@ A6F G@ E8F EZ PF
*BEFORE!AND!AFTER@&#..PZ
[======== G parameter: Subroutine to sort an array by gnome sort ========]
[Input: 0F = A order for array{0}
1F = length of array, in address field
Output: Array is sorted]
[This code conforms to the original description of gnome sort, in which it's
assumed that the gnome can't remember anything and has to move one step
at a time (cf. the alternative name "stupid sort").
The gnome's position is defined by an A order which refers to that position,
and which is indicated below by an arrow.
The code could easily be modified to use 35-bit integers.]
E25K TG GK
A3F T41@ [plant return link as usual]
AF U21@ [initialize gnome's position to start of array]
A1F T44@ [store A order for exclusive end of array]
[Here the gnome moves one step forward]
[6] T45@ [clear acc]
A21@ A2F T21@ [inc address in the defining A order]
[Loop. Assume here with acc = 0.]
[The gnome considers his position]
[10] A21@ [acc := A order for position]
S44@ [is he at the end?]
E41@ [if so, jump to exit with acc = 0]
T45@ [clear acc]
AF [load A order for start]
S21@ [is he at the start?]
E6@ [if so, jump to move 1 step forward]
[Gnome isn't at start or end, so he has to compare values]
T45@ [clear acc]
A21@ [load A order for gnome's psotion]
A42@ [convert to S order for previous position]
T22@ [plant S order]
[21] AF [<============ this planted A order defines the gnome's position]
[22] SF [(planted) acc := (current value) - (previous value)]
E6@ [if current >= previous then jump to move 1 step forward]
[Here the gnome must swap the values and move 1 step backward]
T45@ [clear acc]
A21@ U34@ [plant copy of defining A order]
S2F U36@ [plant A order for gnome's new position]
U21@ [also update defining A order]
A43@ U39@ [plant T order for new position]
A2F T37@ [plant T order for old position]
[34] AF [(planted) acc := array{i}]
T45@ [copy array{i} to temp store]
[36] AF [(planted) acc := array{i-1}]
[37] TF [(planted) copy to array{i}]
A45@ [acc := old array{i}]
[39] TF [(planted) copy to array{i-1}]
E10@ [loop back (always, since acc = 0)]
[41] ZF [(planted) jump back to caller]
[42] K4095F [add to A order to make S order with adderss 1 less]
[43] OF [add to A order to make T order with same address]
[44] AV [A order for exclusive end of array]
[45] PF [(1) dump to clear accumulator (2) temporary for swapping]
[====================== M parameter: Main routine ======================]
E25K TM GK
[0] PF [data count]
[1] PF [negative loop counter]
[2] TV [order to store acc in array{0}]
[3] AV [order to load acc from array{0}]
[4] AV [A order for end of array
[5] !F [space]
[6] @F [carriage return]
[7] &F [linefeed]
[Entry]
[8] A2@ T21@ [initialize order to store value]
A10@ GH [call library subroutine R4, sets 0D := data count N]
[One way of looping a given number of times: use a negative counter]
[(Wilkes, Wheeler & Gill, 1951 edition, pp.164-5)]
AF [acc := data count, assumed to fit into 17 bits]
LD T@ [shift count into address field, and store it]
S@ [acc := negative count]
E38@ [exit if count = 0]
[17] T1@ [update negative loop counter]
A18@ GH [call library subroutine R4, 0D := next value]
AF [acc := value. assumed to fit into 17 bits]
[21] TF [store value in array]
A21@ A2F T21@ [increment address in store order]
A1@ A2F [increment negative loop counter]
G17@ [loop back if still < 0]
A28@ G39@ [print values]
A3@ TF [pass A order for array{0} to gnome sort]
A@ T1F [pass count to gnome sort]
A34@ GG [call gnome sort]
A36@ G39@ [print values again]
[38] ZF [halt the machine]
[------ Subroutine of main routine, to print the array -------]
[39] A3F T60@
A3@ U49@ [initialize load order]
[Another way of looping a given number of times: use a variable order]
[as a counter (Wilkes, Wheeler & Gill, 1951 edition, p.166)]
A@ T4@ [make and plant A order for end of array]
E48@ [don't print a space the first time]
[46] O5@ TF [print space, clear acc]
[48] TD [clear whole of 0D including sandwich bit]
[49] AV [(planted) load value from array <------ order used as counter]
TF [to 0F, so 0D = value extended to 35 bits]
A51@ GN [print value]
A49@ A2F U49@ [update load order]
S4@ G46@ [test for done, loop back if not]
O6@ O7@ [print CR, LF]
[60] EF [(planted) jump back to caller woth acc = 0]
[The next 3 lines put the entry address into location 50,
so that it can be accessed via the X parameter (see end of program).]
T50K
P8@
T8Z
[================== H parameter: Library subroutine R4 ==================]
[Input of one signed integer, returned in 0D.
22 locations.]
E25K TH GK
GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF
[================== N parameter: Library subroutine P7 ==================]
[Library subroutine P7: print strictly positive integer in 0D.
Patched to print left-justified (no-op instead of order to print space)
35 locations, even address]
E25K TN GK
GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSF
L4FT4DA1FA27@G11@T28#ZPFT27ZP1024FP610D@524D!FXFSFL8FE22@
[==========================================================================]
[On the original EDSAC, the following (without the whitespace and comments)
might have been input on a separate tape.]
E25K TX GK
EZ [define entry point]
PF [acc = 0 on entry]
[Counts and data values to be read by library subroutine R4.
Note that sign comes *after* value.]
16+ 98+36+2+78+5+81+32+90+73+21+94+28+53+25+10+99+
</syntaxhighlight>
{{out}}
<pre>
BEFORE AND AFTER
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
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
GNOME_SORT [G -> COMPARABLE]
feature
sort (ar: ARRAY [G]): ARRAY [G]
-- Sorted array in ascending order.
require
array_not_void: ar /= Void
local
i, j: INTEGER
ith: G
do
create Result.make_empty
Result.deep_copy (ar)
from
i := 2
j := 3
until
i > Result.count
loop
if Result [i - 1] <= Result [i] then
i := j
j := j + 1
else
ith := Result [i - 1]
Result [i - 1] := Result [i]
Result [i] := ith
i := i - 1
if i = 1 then
i := j
j := j + 1
end
end
end
ensure
Same_length: ar.count = Result.count
Result_is_sorted: is_sorted (Result)
end
feature {NONE}
is_sorted (ar: ARRAY [G]): BOOLEAN
--- Is 'ar' sorted in ascending order?
require
ar_not_empty: ar.is_empty = False
local
i: INTEGER
do
Result := True
from
i := ar.lower
until
i = ar.upper
loop
if ar [i] > ar [i + 1] then
Result := False
end
i := i + 1
end
end
end</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
create
make
feature
make
do
test := <<7, 99, -7, 1, 0, 25, -10>>
io.put_string ("unsorted:%N")
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
io.new_line
io.put_string ("sorted:%N")
create gnome
test := gnome.sort (test)
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
end
test: ARRAY [INTEGER]
gnome: GNOME_SORT [INTEGER]
end</syntaxhighlight>
{{out}}
<pre>
Unsorted:
7 99 -7 1 0 25 -10
Sorted:
-7 -10 0 1 7 25 99
</pre>
=={{header|Elena}}==
ELENA 5.0 :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
extension op
{
gnomeSort()
{
var list := self.clone();
int i := 1;
int j := 2;
while (i < list.Length)
{
if (list[i-1]<=list[i])
{
i := j;
j += 1
}
else
{
list.exchange(i-1,i);
i -= 1;
if (i==0)
{
i := 1;
j := 2
}
}
};
^ list
}
}
public program()
{
var list := new int[]{3, 9, 4, 6, 8, 1, 7, 2, 5};
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.gnomeSort().asEnumerable())
}</syntaxhighlight>
{{out}}
<pre>
before:3,9,4,6,8,1,7,2,5
after :1,2,3,4,5,6,7,8,9
</pre>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule Sort do
def gnome_sort([]), do: []
def gnome_sort([h|t]), do: gnome_sort([h], t)
defp gnome_sort(list, []), do: list
defp gnome_sort([prev|p], [next|n]) when next > prev, do: gnome_sort(p, [next,prev|n])
defp gnome_sort(p, [next|n]), do: gnome_sort([next|p], n)
end
IO.inspect Sort.gnome_sort([8,3,9,1,3,2,6])</syntaxhighlight>
{{out}}
<pre>
[1, 2, 3, 3, 6, 8, 9]
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">-module(gnome_sort).
-export([gnome/1]).
Line 509 ⟶ 2,352:
gnome(P, [Next|N]) ->
gnome([Next|P], N).
gnome([H|T]) -> gnome([H], T).</
<
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]
3> </
=={{header|Euphoria}}==
<
integer i,j
object temp
Line 539 ⟶ 2,382:
end while
return s
end function</
=={{header|F Sharp|F#}}==
<
let rec loop i j =
if i < a.Length then
Line 550 ⟶ 2,393:
a.[i] <- t
if i=1 then loop j (j+1) else loop (i-1) j
loop 1 2</
=={{header|Factor}}==
USING: kernel math sequences ;
IN: rosetta-code.gnome-sort
: inc-pos ( pos seq -- pos' seq )
[ 1 + ] dip ; inline
: dec-pos ( pos seq -- pos' seq )
[ 1 - ] dip ; inline
: take-two ( pos seq -- elt-at-pos-1 elt-at-pos )
[ dec-pos nth ] [ nth ] 2bi ; inline
: need-swap? ( pos seq -- pos seq ? )
over 1 < [ f ] [ 2dup take-two > ] if ;
: swap-back ( pos seq -- pos seq' )
[ take-two ] 2keep
[ dec-pos set-nth ] 2keep
[ set-nth ] 2keep ;
: gnome-sort ( seq -- sorted-seq )
1 swap [ 2dup length < ] [
2dup [ need-swap? ] [ swap-back dec-pos ] while
2drop inc-pos
] while nip ;
Example:
IN: scratchpad '''USE: rosetta-code.gnome-sort'''
Loading resource:extra/rosetta-code/gnome-sort/gnome-sort.factor
IN: scratchpad '''V{ 10 9 5 7 4 3 6 8 1 2 } gnome-sort .'''
V{ 1 2 3 4 5 6 7 8 9 10 }
=={{header|Fantom}}==
<syntaxhighlight lang="fantom">
class Main
{
Int[] gnomesort (Int[] list)
{
i := 1
j := 2
while (i < list.size)
{
if (list[i-1] <= list[i])
{
i = j
j += 1
}
else
{
list.swap(i-1, i)
i -= 1
if (i == 0)
{
i = j
j += 1
}
}
}
return list
}
Void main ()
{
list := [4,1,5,8,2,1,5,7]
echo ("" + list + " sorted is " + gnomesort (list))
}
}
</syntaxhighlight>
Output:
<pre>
[4, 1, 5, 8, 2, 1, 5, 7] sorted is [1, 1, 2, 4, 5, 5, 7, 8]
</pre>
=={{header|Forth}}==
<
defer exchange
Line 576 ⟶ 2,494:
: .array 10 0 do example i cells + ? loop cr ;
.array example 10 gnomesort .array</
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)
Line 588 ⟶ 2,506:
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
Line 627 ⟶ 2,545:
end subroutine Gnomesort
Optimized Version
SUBROUTINE OPTIMIZEDGNOMESORT(A) ! Nice
IMPLICIT NONE
!
! Dummy arguments
!
REAL , DIMENSION(0:) :: A
INTENT (INOUT) A
!
! Local variables
!
INTEGER :: posy
!
DO posy = 1 , UBOUND(A , 1) !size(a)-1
CALL GNOMESORT(A , posy)
END DO
RETURN
CONTAINS
SUBROUTINE GNOMESORT(A , Upperbound)
IMPLICIT NONE
!
! Dummy arguments
!
INTEGER :: Upperbound
REAL , DIMENSION(0:) :: A
INTENT (IN) Upperbound
INTENT (INOUT) A
!
! Local variables
!
LOGICAL :: eval
INTEGER :: posy
REAL :: t
!
eval = .FALSE.
posy = Upperbound
eval = (posy>0) .AND. (A(posy - 1)>A(posy))
! do while ((posy > 0) .and. (a(posy-1) > a(posy)))
DO WHILE ( eval )
t = A(posy)
A(posy) = A(posy - 1)
A(posy - 1) = t
!
posy = posy - 1
eval = (posy>0)
IF( eval )THEN ! Have to use as a guard condition
eval = (A(posy - 1)>A(posy))
ELSE
eval = .FALSE.
END IF
END DO
RETURN
END SUBROUTINE GNOMESORT
END SUBROUTINE OPTIMIZEDGNOMESORT
!
end program example</
=={{header|Go}}==
<
import "fmt"
Line 653 ⟶ 2,631:
j++
}
}</
More generic version that sorts anything that implements <code>sort.Interface</code>:
<
import (
Line 682 ⟶ 2,660:
j++
}
}</
=={{header|Groovy}}==
Solution:
<
def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
Line 697 ⟶ 2,675:
}
input
}</
Test:
<
println (gnomeSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</
Output:
Line 708 ⟶ 2,686:
=={{header|Haskell}}==
<
gnomeSort (x:xs) = gs [x] xs
where
Line 716 ⟶ 2,694:
gs [] (y:ys) = gs [y] ys
gs xs [] = reverse xs
-- keeping the first argument of gs in reverse order avoids the deterioration into cubic behaviour </
=={{header|Haxe}}==
<syntaxhighlight lang="haxe">class GnomeSort {
@:generic
public static function sort<T>(arr:Array<T>) {
var i = 1;
var j = 2;
while (i < arr.length) {
if (Reflect.compare(arr[i - 1], arr[i]) <= 0) {
i = j++;
} else {
var temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
if (--i == 0) {
i = j++;
}
}
}
}
}
class Main {
static function main() {
var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3,
3.5, 0.0, -4.1, -9.5];
var stringArray = ['We', 'hold', 'these', 'truths', 'to',
'be', 'self-evident', 'that', 'all',
'men', 'are', 'created', 'equal'];
Sys.println('Unsorted Integers: ' + integerArray);
GnomeSort.sort(integerArray);
Sys.println('Sorted Integers: ' + integerArray);
Sys.println('Unsorted Floats: ' + floatArray);
GnomeSort.sort(floatArray);
Sys.println('Sorted Floats: ' + floatArray);
Sys.println('Unsorted Strings: ' + stringArray);
GnomeSort.sort(stringArray);
Sys.println('Sorted Strings: ' + stringArray);
}
}</syntaxhighlight>
{{out}}
<pre>
Unsorted Integers: [1,10,2,5,-1,5,-19,4,23,0]
Sorted Integers: [-19,-1,0,1,2,4,5,5,10,23]
Unsorted Floats: [1,-3.2,5.2,10.8,-5.7,7.3,3.5,0,-4.1,-9.5]
Sorted Floats: [-9.5,-5.7,-4.1,-3.2,0,1,3.5,5.2,7.3,10.8]
Unsorted Strings: [We,hold,these,truths,to,be,self-evident,that,all,men,are,created,equal]
Sorted Strings: [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths]
</pre>
=={{header|Icon}} and {{header|Unicon}}==
<syntaxhighlight lang="icon">procedure main() #: demonstrate various ways to sort a list and string
demosort(gnomesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
procedure gnomesort(X,op) #: return sorted list
local i,j
op := sortop(op,X) # select how and what we sort
j := (i := 2) + 1 # translation of pseudo code
while i <= *X do {
if op(X[i],X[i-1]) then {
X[i] :=: X[i -:= 1]
if i > 1 then next
}
j := (i := j) + 1
}
return X
end</syntaxhighlight>
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.
Abbreviated sample output:<pre>Sorting Demo using procedure gnomesort
on list : [ 3 14 1 5 9 2 6 3 ]
with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)
...
on string : "qwerty"
with op = &null: "eqrtwy" (0 ms)</pre>
=={{header|Io}}==
Naive version:
<
gnomeSortInPlace := method(
idx := 1
Line 735 ⟶ 2,794:
lst := list(5, -1, -4, 2, 9)
lst gnomeSortInPlace println # ==> list(-4, -1, 2, 5, 9)</
Optimized version, storing the position before traversing back towards the begining of the list ([[wp:Gnome_sort#Optimization|Wikipedia]])
<
gnomeSortInPlace := method(
idx1 := 1
Line 756 ⟶ 2,815:
lst := list(5, -1, -4, 2, 9)
lst gnomeSortInPlace println # ==> list(-4, -1, 2, 5, 9)</
=={{header|J}}==
{{eff note|J|/:~}}
<
swap=: ] A.~ *@position * #@[ !@- <:@position
gnome=: swap~ 2 >/\ ]
gnomes=: gnome^:_</
Note 1: this implementation of swap is actually rather silly, and will not work on long lists. A better implementation would be:<
Note 2: this implementation only works for domains where > is defined (in J, "greater than" only works on numbers). To work around this issue, you could define:<
gnome=: swap~ 2 gt/\ ]</
Note 3: this implementation does not return intermediate results. If you want them, you could use<
Note 4: gnomeps just shows intermediate results and does not show the gnome's position. You can extract the gnome's position using an expression such as<syntaxhighlight lang
=={{header|Java}}==
{{trans|C}}
<
{
int i=1;
Line 821 ⟶ 2,850:
}
}
}</
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">function gnomeSort(a) {
function moveBack(i) {
for( ; i > 0 && a[i-1] > a[i]; i--) {
var t = a[i];
a[i] = a[i-1];
a[i-1] = t;
}
}
for (var i = 1; i < a.length; i++) {
if (a[i-1] > a[i]) moveBack(i);
}
return a;
}</syntaxhighlight>
=={{header|jq}}==
{{works with | jq|1.4}}
This implementation adheres to the specification.
The array to be sorted, however, can be any JSON array.
<syntaxhighlight lang="jq"># As soon as "condition" is true, then emit . and stop:
def do_until(condition; next):
def u: if condition then . else (next|u) end;
u;
# input: an array
def gnomeSort:
def swap(i;j): .[i] as $x | .[i]=.[j] | .[j]=$x;
length as $length
# state: [i, j, ary]
| [1, 2, .]
| do_until( .[0] >= $length;
.[0] as $i | .[1] as $j
| .[2]
# for descending sort, use >= for comparison
| if .[$i-1] <= .[$i] then [$j, $j + 1, .]
else swap( $i-1; $i)
| ($i - 1) as $i
| if $i == 0 then [$j, $j + 1, .]
else [$i, $j, .]
end
end )
| .[2];</syntaxhighlight>
'''Example''':
<syntaxhighlight lang="jq">[(2|sqrt), [1], null, 1, 0.5, 2, 1, -3, {"a": "A"}] | gnomeSort</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="sh">$ jq -M -n -f Gnome_sort.jq
[
null,
-3,
0.5,
1,
1,
1.4142135623730951,
2,
[
1
],
{
"a": "A"
}
]</syntaxhighlight>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">function gnomesort!(arr::Vector)
i, j = 1, 2
while i < length(arr)
if arr[i] ≤ arr[i+1]
i = j
j += 1
else
arr[i], arr[i+1] = arr[i+1], arr[i]
i -= 1
if i == 0
i = j
j += 1
end
end
end
return arr
end
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", gnomesort!(v))</syntaxhighlight>
{{out}}
<pre># unordered: [9, -8, 0, 3, 2, 10, 5, 4, 5, 5]
-> ordered: [-8, 0, 2, 3, 4, 5, 5, 5, 9, 10]</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.0
fun <T: Comparable<T>> gnomeSort(a: Array<T>, ascending: Boolean = true) {
var i = 1
var j = 2
while (i < a.size)
if (ascending && (a[i - 1] <= a[i]) ||
!ascending && (a[i - 1] >= a[i]))
i = j++
else {
val temp = a[i - 1]
a[i - 1] = a[i]
a[i--] = temp
if (i == 0) i = j++
}
}
fun main(args: Array<String>) {
val array = arrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199)
println("Original : ${array.asList()}")
gnomeSort(array)
println("Sorted (asc) : ${array.asList()}")
gnomeSort(array, false)
println("Sorted (desc) : ${array.asList()}")
}</syntaxhighlight>
{{out}}
<pre>
Original : [100, 2, 56, 200, -52, 3, 99, 33, 177, -199]
Sorted (asc) : [-199, -52, 2, 3, 33, 56, 99, 100, 177, 200]
Sorted (desc) : [200, 177, 100, 99, 56, 33, 3, 2, -52, -199]
</pre>
=={{header|Lua}}==
Keep in mind that Lua arrays initial index is 1.
<
local i, j = 2, 3
while i <= #a do
if a[i-1] <= a[i] then
i = j
Line 841 ⟶ 2,995:
end
end
end</
Example:
<
gnomeSort(list)
for i, j in pairs(list) do
print(j)
end</
=={{header|
<syntaxhighlight lang="maple">arr := Array([17,3,72,0,36,2,3,8,40,0]):
len := numelems(arr):
i := 2:
while (i <= len) do
if (i=1 or arr[i] >= arr[i-1]) then
i++:
else
temp:= arr[i]:
arr[i] := arr[i-1]:
arr[i-1] := temp:
i--:
end if:
end do:
arr;</syntaxhighlight>
{{Out|Output}}
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">gnomeSort[list_]:=Module[{i=2,j=3},
While[ i<=Length[[list]],
If[ list[[i-1]]<=list[[i]],
i=j; j++;,
list[[i-1;;i]]=list[[i;;i-1]];i--;];
If[i==1,i=j;j++;]
]]</syntaxhighlight>
=={{header|MATLAB}} / {{header|Octave}}==
<syntaxhighlight lang="matlab">function list = gnomeSort(list)
i = 2;
Line 870 ⟶ 3,051:
end %while
end %gnomeSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">fn gnomeSort arr =
(
local i = 2
local j = 3
while i <= arr.count do
(
if arr[i-1] <= arr[i] then
(
i = j
j += 1
)
else
(
swap arr[i-1] arr[i]
i -= 1
if i == 1 then
(
i = j
j += 1
)
)
)
return arr
)</syntaxhighlight>
Output:
<syntaxhighlight lang="maxscript">
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)
</syntaxhighlight>
=={{header|Metafont}}==
<
begingroup save i, j, t;
i := 1; j := 2;
Line 894 ⟶ 3,108:
fi
endfor
endgroup enddef;</
<
for i = 0 upto 9: a[i] := uniformdeviate(40); message decimal a[i]; endfor
message char10;
Line 902 ⟶ 3,116:
gnomesort(a, 10);
for i = 0 upto 9: message decimal a[i]; endfor
end</
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">
gnomesort = function(a)
i = 1
j = 2
while i < a.len
if a[i-1] <= a[i] then
i = j
j = j + 1
else
k = a[i-1]
a[i-1] = a[i]
a[i] = k
i = i - 1
if i == 0 then
i = j
j = j + 1
end if
end if
end while
end function
a = [3, 7, 4, 2, 5, 1, 6]
gnomesort(a)
print a
</syntaxhighlight>
{{out}}
<pre>[1, 2, 3, 4, 5, 6, 7]
</pre>
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 955 ⟶ 3,198:
return ra
</syntaxhighlight>
;Output
<pre>
Line 961 ⟶ 3,204:
[1, 2, 3, 3, 3, 4, 5, 6]
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">proc gnomeSort[T](a: var openarray[T]) =
var
n = a.len
i = 1
j = 2
while i < n:
if a[i-1] > a[i]:
swap a[i-1], a[i]
dec i
if i > 0: continue
i = j
inc j
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
gnomeSort a
echo a</syntaxhighlight>
Output:
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Objeck}}==
{{trans|C}}
<
function : GnomeSort(a : Int[]) {
i := 1;
Line 986 ⟶ 3,249:
};
}
</syntaxhighlight>
=={{header|OCaml}}==
from the toplevel:
<
let i = ref 1
and j = ref 2 in
Line 1,017 ⟶ 3,280:
# a ;;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]</
=={{header|Octave}}==
<
i = 2; j = 3;
while ( i <= length(v) )
Line 1,038 ⟶ 3,301:
endwhile
s = v;
endfunction</
<
disp(gnomesort(v));</
=={{header|ooRexx}}==
===version 1===
{{Trans|NetRexx}}
<syntaxhighlight lang="oorexx">/* Rexx */
call demo
return
exit
-- -----------------------------------------------------------------------------
-- Gnome sort implementation
-- -----------------------------------------------------------------------------
::routine gnomeSort
use arg ra, sAsc = ''
if sAsc = '' then sAsc = isTrue()
sDsc = \sAsc -- Ascending/descending switches
i_ = 1
j_ = 2
loop label i_ while i_ < ra~items()
ctx = (ra~get(i_ - 1))~compareTo(ra~get(i_))
if (sAsc & ctx <= 0) | (sDsc & ctx >= 0) then do
i_ = j_
j_ = j_ + 1
end
else do
swap = ra~get(i_)
ra~set(i_, ra~get(i_ - 1))
ra~set(i_ - 1, swap)
i_ = i_ - 1
if i_ = 0 then do
i_ = j_
j_ = j_ + 1
end
end
end i_
return ra
-- -----------------------------------------------------------------------------
-- Demonstrate the implementation
-- -----------------------------------------------------------------------------
::routine demo
placesList = .nlist~of( -
"UK London", "US New York", "US Boston", "US Washington" -
, "UK Washington", "US Birmingham", "UK Birmingham", "UK Boston" -
)
lists = .nlist~of( -
placesList -
, gnomeSort(placesList~copy()) -
)
loop ln = 0 to lists~items() - 1
cl = lists[ln]
loop ct = 0 to cl~items() - 1
say right(ct + 1, 3)':' cl[ct]
end ct
say
end ln
i_.0 = 3
i_.1 = .nlist~of(3, 3, 1, 2, 4, 3, 5, 6)
i_.2 = gnomeSort(i_.1~copy(), isTrue())
i_.3 = gnomeSort(i_.1~copy(), isFalse())
loop s_ = 1 to i_.0
ss = ''
loop x_ = 0 to i_.s_~items() - 1
ss ||= right(i_.s_~get(x_), 3)' '
end x_
say strip(ss, 'T')
end s_
return
-- -----------------------------------------------------------------------------
::routine isTrue
return 1 == 1
-- -----------------------------------------------------------------------------
::routine isFalse
return \isTrue()
-- -----------------------------------------------------------------------------
-- Helper class. Map get and set methods for easier conversion from java.util.List
-- -----------------------------------------------------------------------------
::class NList mixinclass List public
-- Map get() to at()
::method get
use arg ix
return self~at(ix)
-- Map set() to put()
::method set
use arg ix, item
self~put(item, ix)
return
</syntaxhighlight>
'''Output:
<pre>
1: UK London
2: US New York
3: US Boston
4: US Washington
5: UK Washington
6: US Birmingham
7: UK Birmingham
8: UK Boston
1: UK Birmingham
2: UK Boston
3: UK London
4: UK Washington
5: US Birmingham
6: US Boston
7: US New York
8: US Washington
3 3 1 2 4 3 5 6
1 2 3 3 3 4 5 6
6 5 4 3 3 3 2 1
</pre>
===version 2===
{{trans|REXX}}
<syntaxhighlight lang="oorexx">/* REXX ---------------------------------------------------------------
* 28.06.2014 Walter Pachl
* 30.06.2014 corrected in sync with REXX version 2
*--------------------------------------------------------------------*/
Call gen /* generate the array elements. */
Call show 'before sort' /* show "before" array elements.*/
Call gnomeSort x /* invoke the infamous gnome sort.*/
Call show ' after sort' /* show "after" array elements.*/
Exit /* done. */
gnomesort: Procedure
Use Arg x
n=x~items
k=2
Do j=3 While k<=n
km=k-1
If x[km]<=x[k] Then
k=j
Else Do
t=x[km]; x[km]=x[k]; x[k]=t /* swap two entries in the array. */
k=k-1
If k==1 Then
k=j
Else
j=j-1
End
End
Return
gen:
x=.array~of('---the seven virtues---','=======================',,
'Faith','Hope','Charity [Love]','Fortitude',' Justice',,
'Prudence','Temperance')
Return
show:
Say arg(1)
Do i=1 To x~items
Say 'element' right(i,2) x[i]
End
Return</syntaxhighlight>
'''output'''
Similar to REXX version 2
=={{header|Oz}}==
{{trans|Haskell}}
<
fun {GnomeSort Xs}
case Xs of nil then nil
Line 1,061 ⟶ 3,493:
end
in
{Show {GnomeSort [3 1 4 1 5 9 2 6 5]}}</
=={{header|PARI/GP}}==
<
my(i=2,j=3,n=#v,t);
while(i<=n,
Line 1,078 ⟶ 3,510:
);
v
};</
=={{header|Pascal}}==
<
var
i, j, t : Integer;
Line 1,104 ⟶ 3,536:
end
end;
end;</
=={{header|Perl}}==
<
sub gnome_sort
Line 1,130 ⟶ 3,562:
}
return @a;
}</
<
print "$_\n" foreach gnome_sort( @arr );</
=={{header|
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">gnomeSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">sn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">sn</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sn</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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>
<!--</syntaxhighlight>-->
=={{header|PHP}}==
<
$i = 1;
$j = 2;
Line 1,171 ⟶ 3,615:
}
$arr = array(3,1,6,2,9,4,7,8,5);
echo implode(',',gnomeSort($arr));</
<pre>1,2,3,4,5,6,7,8,9</pre>
=={{header|PicoLisp}}==
<
(let J (cdr Lst)
(for (I Lst (cdr I))
Line 1,184 ⟶ 3,628:
(setq I J J (cdr J))
(setq I (prior I Lst)) ) ) ) )
Lst )</
=={{header|
<syntaxhighlight lang="pl/i">SORT: PROCEDURE OPTIONS (MAIN);
DECLARE A(0:9) FIXED STATIC INITIAL (5, 2, 7, 1, 9, 8, 6, 3, 4, 0);
CALL GNOME_SORT (A);
put skip edit (A) (f(7));
GNOME_SORT: PROCEDURE (A) OPTIONS (REORDER); /* 9 September 2015 */
declare A(*) fixed;
declare
declare
i = 1; j = 2;
do
if a(i-1) <= a(i) then
t = a(i-1); a(i-1) = a(i); a(i) = t;
i = i - 1;
if i = 0 then do; i = j; j = j + 1; end;
END GNOME_SORT;
END SORT;</syntaxhighlight>
Results:
<pre>
0 1 2 3 4 5 6 7 8 9
</pre>
=={{header|PL/M}}==
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
Note that integers in 8080 PL/M are unsigned.
<syntaxhighlight lang="plm">
100H: /* GNOME SORT */
/* IN-PLACE GNOME SORT THE FIRST SIZE ELEMENTS OF THE */
/* ARRAY POINTED TO BY A$PTR */
GNOME$SORT: PROCEDURE( A$PTR, SIZE );
DECLARE (
DECLARE A
DECLARE ( I, J ) ADDRESS;
J = 2;
DO WHILE I < SIZE;
IF A( I - 1 ) <= A( I ) THEN DO;
I = J;
J = J + 1;
END;
ELSE DO;
DECLARE SWAP ADDRESS;
SWAP = A( I - 1 );
A( I - 1 ) = A( I );
A( I ) = SWAP;
I = I - 1;
IF I = 0 THEN DO;
I = J;
J = J + 1;
END;
END;
END;
END GNOME$SORT ;
/* CP/M BDOS SYSTEM CALLS AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$STRING( .( 0DH, 0AH, '$' ) ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
DO; /* TEST GNOME$SORT */
DECLARE N ( 11 )ADDRESS, N$POS BYTE;
N( 0 ) = 4; N( 1 ) = 65; N( 2 ) = 2; N( 3 ) = 31; N( 4 ) = 0;
N( 5 ) = 99; N( 6 ) = 2; N( 7 ) = 8; N( 8 ) = 3; N( 9 ) = 783;
N( 10 ) = 1;
CALL GNOME$SORT( .N, 11 );
DO N$POS = 0 TO 10;
CALL PR$CHAR( ' ' );
CALL PR$NUMBER( N( N$POS ) );
END;
END;
EOF
</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 3 4 8 31 65 99 783
</pre>
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">function gnomesort($a) {
$size, $i, $j = $a.Count, 1, 2
while($i -lt $size) {
if ($a[$i-1] -le $a[$i]) {
$i = $j
$j++
}
else {
$a[$i-1], $a[$i] = $a[$i], $a[$i-1]
$i--
if($i -eq 0) {
$i = $j
$j++
}
}
}
$a
}
$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)
"$(gnomesort $array)"</syntaxhighlight>
<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:
Line 1,264 ⟶ 3,775:
>>> gnomesort([3,4,2,5,1,6])
[1, 2, 3, 4, 5, 6]
>>></
=={{header|
<syntaxhighlight lang="quackery">[ dup size times
[ i^ 0 > if
[ dup i^ 1 - peek
over i^ peek
2dup > iff
[ dip [ swap i^ poke ]
swap i^ 1 - poke
-1 step ]
else 2drop ] ] ] is gnomesort ( [ --> [ )</syntaxhighlight>
=={{header|R}}==
===Starting from 1===
<syntaxhighlight lang="rsplus">gnomesort <- function(x)
{
i <- 1
Line 1,292 ⟶ 3,816:
x
}
gnomesort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</
===Starting from 2===
The previously solution misses out on a cool R trick for swapping items.
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.
<syntaxhighlight lang="rsplus">gnomeSort <- function(a)
{
i <- 2
j <- 3
while(i <= length(a))
{
if(a[i - 1] <= a[i])
{
i <- j
j <- j + 1
}
else
{
a[c(i - 1, i)] <- a[c(i, i - 1)]#The cool trick mentioned above.
i <- i - 1
if(i == 1)
{
i <- j
j <- j + 1
}
}
}
a
}
#Examples taken from the Haxe solution.
#Note that R can use <= to compare strings.
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)
strings <- c("We", "hold", "these", "truths", "to", "be", "self-evident", "that", "all", "men", "are", "created", "equal")</syntaxhighlight>
{{out}}
<pre>> gnomeSort(ints)
> gnomeSort(numerics)
[1] -9.5 -5.7 -4.1 -3.2 0.0 1.0 3.5 5.2 7.3 10.8
> gnomeSort(strings)
[1] "all" "are" "be" "created" "equal" "hold" "men"
[8] "self-evident" "that" "these" "to" "truths" "We"</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
;; Translation of the pseudo code
(define (gnome-sort1 a <=?)
(define size (vector-length a))
(define (swap i j)
(define t (vector-ref a i))
(vector-set! a i (vector-ref a j))
(vector-set! a j t))
(let loop ([i 1] [j 2])
(when (< i size)
(if (<=? (vector-ref a (sub1 i)) (vector-ref a i))
(loop j (add1 j))
(begin (swap (sub1 i) i)
(let ([i (sub1 i)])
(if (zero? i)
(loop j (add1 j))
(loop i j)))))))
a)
(gnome-sort1 (vector 3 2 1 4 5 6) <=)
;; a functional version, roughly like the Scheme entry
(define (gnome-sort2 l <=?)
(match l
[(list) l]
[(list x xs
(let loop ([x `((,x) .
(match
[`(,ps)
[`((,p . ,ps) ,n .
(loop (cond [(<=? n p) `((,n ,p . ,ps) .
[(null? ps) `((,n) ,p . ,ns)]
[else `(,ps ,n ,p . ,ns)]))]))]))
(gnome-sort2 '(3 2 1 4 5 6) <=)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2016.03}}
<syntaxhighlight lang="raku" line>sub gnome_sort (@a) {
my ($i, $j) = 1, 2;
while $i < @a {
if @a[$i - 1] <= @a[$i] {
($i, $j) = $j, $j + 1;
}
else {
(@a[$i - 1], @a[$i]) = @a[$i], @a[$i - 1];
$i--;
($i, $j) = $j, $j + 1 if $i == 0;
}
}
}
my @n = (1..10).roll(20);
say @n.&gnome_sort ~~ @n.sort ?? 'ok' !! 'not ok';</syntaxhighlight>
=={{header|Rascal}}==
<syntaxhighlight lang="rascal">import List;
public list[int] gnomeSort(a){
i =
j = 2;
while(i < size(a)){
if(a[i-1] <= a[i]){
i = j;
j += 1;}
else{
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
i = i - 1;
if(i == 0){
i = j;
j += 1;}}}
return a;
}</syntaxhighlight>
An example output:
<syntaxhighlight lang="rascal">gnomeSort([4, 65, 2, -31, 0, 99, 83, 782, 1])
list[int]: [-31,0,1,2,4,65,83,99,782]</syntaxhighlight>
=={{header|REXX}}==
===version 1===
This REXX version uses an unity-based array (instead of a zero-based array).
<syntaxhighlight lang="rexx">/*REXX program sorts an array using the gnome sort algorithm (elements contain blanks). */
call gen /*generate the @ stemmed array. */
call show 'before sort' /*display the before array elements.*/
say copies('▒', 60) /*show a separator line between sorts. */
call gnomeSort # /*invoke the well─known gnome sort. */
call show ' after sort' /*display the after array elements.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen: @.=; @.1= '---the seven virtues---'; @.4= "Hope" ; @.7= 'Justice'
@.2= '======================='; @.5= "Charity [Love]"; @.8= 'Prudence'
@.3= 'Faith' ; @.6= "Fortitude" ; @.9= 'Temperance'
do #=1 while @.#\==''; end; #= #-1; w= length(#); return /*get #items*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
gnomeSort: procedure expose @.; parse arg n; k= 2 /*N: is number items. */
do j=3 while k<=n; p= k - 1 /*P: is previous item.*/
if @.p<<=@.k then do; k= j; iterate; end /*order is OK so far. */
_= @.p; @.p= @.k; @.k= _ /*swap two @ entries. */
k= k - 1; if k==1 then k= j; else j= j-1 /*test for 1st index. */
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do j=1 for #; say ' element' right(j, w) arg(1)":" @.j; end; return</syntaxhighlight>
{{out|output|:}}
(Shown at three-quarter size.)
<pre style="font-size:75%">
element 1 before sort: ---the seven virtues---
element 2 before sort: =======================
element 3 before sort: Faith
element 4 before sort: Hope
element 5 before sort: Charity [Love]
element 6 before sort: Fortitude
element 7 before sort: Justice
element 8 before sort: Prudence
element 9 before sort: Temperance
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: ---the seven virtues---
element 2 after sort: =======================
element 3 after sort: Charity [Love]
element 4 after sort: Faith
element 5 after sort: Fortitude
element 6 after sort: Hope
element 7 after sort: Justice
element 8 after sort: Prudence
element 9 after sort: Temperance
</pre>
===version 2===
<syntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* 28.06.2014 Walter Pachl cf ooRexx version 2
* only style changes (reformatting) and adapt for ooRexx compatibility
* NOTE that leading blanks are ignored in the comparison (' Justice')
* unless strict comparison is used (i.e., 'If x.km<<=x.k Then')
* 30.06.2014 WP added the missing else clause
*--------------------------------------------------------------------*/
/* generate the array elements. */
Call gen '---the seven virtues---','=======================',,
'Faith','Hope','Charity [Love]','Fortitude',' Justice',,
'Prudence','Temperance'
Call show 'before sort' /* show "before" array elements.*/
Call gnomeSort /* invoke the infamous gnome sort.*/
Call show ' after sort' /* show "after" array elements.*/
Exit /* done. */
gnomesort: Procedure Expose x.
k=2
Do j=3 While k<=x.0
km=k-1
If x.km<=x.k Then
k=j
Else Do
t=x.km; x.km=x.k; x.k=t /* swap two entries in the array. */
k=k-1
If k==1 Then
k=j
Else
j=j-1
End
End
Return
gen: Procedure Expose x.
Do i=1 To arg()
x.i=arg(i)
End
x.0=arg()
Return
show: Procedure Expose x.
Say arg(1)
Do i=1 To x.0
Say 'element' right(i,2) x.i
End
Return
</syntaxhighlight>
'''output'''
<pre>before sort
element 1 ---the seven virtues---
element 2 =======================
element 3 Faith
element 4 Hope
element 5 Charity [Love]
element 6 Fortitude
element 7 Justice
element 8 Prudence
element 9 Temperance
after sort
element 1 ---the seven virtues---
element 2 =======================
element 3 Charity [Love]
element 4 Faith
element 5 Fortitude
element 6 Hope
element 7 Justice
element 8 Prudence
element 9 Temperance</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
aList = [ 5, 6, 1, 2, 9, 14, 15, 7, 8, 97]
gnomeSort(aList)
for i=1 to len(aList)
see "" + aList[i] + " "
next
func gnomeSort a
i = 2
j = 3
while i < len(a)
if a[i-1] <= a[i]
i = j
j = j + 1
else
temp = a[i-1]
a[i-1] = a[i]
a[i] = temp
i = i - 1
if i = 1
i = j
j = j + 1 ok ok end
</syntaxhighlight>
=={{header|RPL}}==
{{works with|RPL|HP-49C}}
« DUP SIZE 1 → s h
« 2
'''WHILE''' h s < '''REPEAT'''
'''IF''' OVER h DUP 1 + SUB EVAL ≤ '''THEN'''
'h' ▶ 1 +
'''ELSE'''
SWAP h DUP2 DUP 1 + SUB REVLIST REPL SWAP
'''IF''' 'h' DECR NOT '''THEN''' 'h' ▶ 1 + '''END'''
'''END'''
'''END''' DROP
» » '<span style="color:blue">GNOMESORT</span>' STO
{ 7 6 5 9 8 4 3 1 2 0 } <span style="color:blue">GNOMESORT</span>
{{out}}
<pre>
1: { 0 1 2 3 4 5 6 7 8 9 }
</pre>
This implementation of gnome sort is 30 times slower than the <code>SORT</code> built-in function on a HP-50g.
=={{header|Ruby}}==
<
def gnomesort!
i, j = 1, 2
Line 1,400 ⟶ 4,131:
ary = [7,6,5,9,8,4,3,1,2,0]
ary.gnomesort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn gnome_sort<T: PartialOrd>(a: &mut [T]) {
let len = a.len();
let mut i: usize = 1;
let mut j: usize = 2;
while i < len {
if a[i - 1] <= a[i] {
// for descending sort, use >= for comparison
i = j;
j += 1;
} else {
a.swap(i - 1, i);
i -= 1;
if i == 0 {
i = j;
j += 1;
}
}
}
}
fn main() {
let mut v = vec![10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6];
println!("before: {:?}", v);
gnome_sort(&mut v);
println!("after: {:?}", v);
}</syntaxhighlight>
{{out}}
<pre>
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="scala">object GnomeSort {
def gnomeSort(a: Array[Int]): Unit = {
var (i, j) = (1, 2)
while ( i < a.length)
if (a(i - 1) <= a(i)) { i = j; j += 1 }
else {
val tmp = a(i - 1)
a(i - 1) = a(i)
a({i -= 1; i + 1}) = tmp
i = if (i == 0) {j += 1; j - 1} else i
}
}
}</syntaxhighlight>
=={{header|Scheme}}==
<syntaxhighlight lang="scheme">; supply comparison function, which returns true if first and second
; arguments are in order or equal.
(define (gnome-sort-compar in-order input-list)
Line 1,424 ⟶ 4,203:
(gnome
(cdr p) ; Prev list shorter by one
(cons next-pot (cons prev-pot (cdr n))))))))))</syntaxhighlight>
#;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|
<syntaxhighlight lang="ruby">class Array {
method gnomesort {
var (i=1, j=2);
var len = self.len;
while (i < len) {
if (self[i-1] <= self[i]) {
(i, j) = (j, j+1);
}
else {
self[i-1, i] = self[i, i-1];
if (--i == 0) {
(i, j) = (j, j+1);
}
}
}
return self;
}
}
var ary = [7,6,5,9,8,4,3,1,2,0];
say ary.gnomesort;</syntaxhighlight>
{{out}}
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>
=={{header|Smalltalk}}==
<syntaxhighlight lang="smalltalk">Smalltalk at: #gnomesort put: nil.
"Utility"
Line 1,465 ⟶ 4,265:
]
]
].</
'''Testing'''
<
r := Random new.
o := OrderedCollection new.
Line 1,477 ⟶ 4,277:
gnomesort value: o.
1 to: 10 do: [ :i | (o at: i) displayNl ].</
=={{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.
<syntaxhighlight lang="snobol4">*** GNOME SORT *****************************************************************
* GNOME(V) -- gnome sort of the numerical vector V.
*** HELPER FUNCTIONS ***********************************************************
* IDXMAX(V) -- highest index of vector V.
* IDXMIN(V) -- lowest index of vector V.
* NUMBER(V) -- succeeds if V is some form of numerical data, fails otherwise.
* NUMBERS(V) -- succeeds iff all elements of vector V are numerical
* SWAP(A,B) -- swaps the values of two variables (named with .var).
* VECTOR(V) -- succeeds iff V is a vector.
********************************************************************************
define('GNOME(V)I,J,K,L,H,T')
*
define('IDXMAX(V)')
define('IDXMIN(V)')
define('NUMBER(V)')
define('NUMBERS(V)I,M')
define('SWAP(SWAP_PARAMETER_VAR_A,SWAP_PARAMETER_VAR_B)')
define('VECTOR(V)')
:(GNOME.END)
****************************************
* GNOME FUNCTION *
****************************************
GNOME numbers(v) :F(FRETURN)
gnome = copy(v)
l = idxmin(v) ; h = idxmax(v) ; i = l + 1
GNOME.LOOP j = i - 1
le(i, l) :S(GNOME.FORWARD)
gt(i,h) :S(RETURN)
le(gnome<j>, gnome<i>) :S(GNOME.FORWARD)
swap(.gnome<j>, .gnome<i>)
i = i - 1 :(GNOME.LOOP)
GNOME.FORWARD i = i + 1 :(GNOME.LOOP)
****************************************
* HELPER FUNCTIONS *
****************************************
IDXMAX vector(v) :F(FRETURN)
prototype(v) ':' span('-' &digits) . idxmax :S(RETURN)F(IDXMAX.NORM)
IDXMAX.NORM idxmax = prototype(v) :(RETURN)
****************************************
IDXMIN vector(v) :F(FRETURN)
prototype(v) span('-' &digits) . idxmin ':' :S(RETURN)F(IDXMIN.NORM)
IDXMIN.NORM idxmin = 1 :(RETURN)
****************************************
NUMBER ident(datatype(v), 'INTEGER') :S(RETURN)
ident(datatype(v), 'REAL') :S(RETURN)F(FRETURN)
****************************************
NUMBERS vector(v) :F(FRETURN)
i = idxmin(v) ; m = idxmax(v)
NUMBERS.LOOP le(i,m) :F(RETURN)
number(v<i>) :F(FRETURN)
i = i + 1 :(NUMBERS.LOOP)
****************************************
SWAP SWAP = $SWAP_PARAMETER_VAR_A
$SWAP_PARAMETER_VAR_A = $SWAP_PARAMETER_VAR_B
$SWAP_PARAMETER_VAR_B = SWAP
SWAP = :(RETURN)
****************************************
VECTOR ident(v) :S(FRETURN)
prototype(v) ',' :S(FRETURN)F(RETURN)
****************************************
GNOME.END</syntaxhighlight>
The test script looks like this:
<syntaxhighlight lang="snobol4">-INCLUDE 'gnome_sort.sno'
GNOME.TEST output = 'valid values...'
a = array(5)
a<1> = 50 ; a<2> = 40 ; a<3> = 10
a<4> = 30 ; a<5> = 20
b = gnome(a) :F(ERROR)
eq(b<1>,10) ; eq(b<2>,20) ; eq(b<3>,30) :F(ERROR)
eq(b<4>,40) ; eq(b<5>,50) :F(ERROR)
a = array('-2:2')
a<-2> = 50 ; a<-1> = 40 ; a<0> = 10
a<1> = 30 ; a<2> = 20
b = gnome(a) :F(ERROR)
eq(b<-2>,10) ; eq(b<-1>,20) ; eq(b<0>,30) :F(ERROR)
eq(b<1>,40) ; eq(b<2>,50) :F(ERROR)
a = array(5)
a<1> = 5.5 ; a<2> = 4.4 ; a<3> = 1.1
a<4> = 3.3 ; a<5> = 2.2
b = gnome(a) :F(ERROR)
eq(b<1>,1.1) ; eq(b<2>,2.2) ; eq(b<3>,3.3) :F(ERROR)
eq(b<4>,4.4) ; eq(b<5>,5.5) :F(ERROR)
output = 'invalid values...'
a = array(5, "five")
b = gnome(a) :S(ERROR)
a = array(5)
b = gnome(a) :S(ERROR)
output = 'PASSED!'
END</syntaxhighlight>
=={{header|Swift}}==
<syntaxhighlight lang="swift">func gnomeSort<T: Comparable>(_ a: inout [T]) {
var i = 1
var j = 2
while i < a.count {
if a[i - 1] <= a[i] {
i = j
j += 1
} else {
a.swapAt(i - 1, i)
i -= 1
if i == 0 {
i = j
j += 1
}
}
}
}
var array = [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
print("before: \(array)")
gnomeSort(&array)
print(" after: \(array)")</syntaxhighlight>
{{out}}
<pre>
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
</pre>
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
package require struct::list
Line 1,504 ⟶ 4,432:
}
puts [gnomesort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
=={{header|
The function is parameterized by a relational predicate and
operates on a list. The algorithm is to scan forward until
finding an item out of order, bubble it backwards to its
proper position and resume scanning forward from where it was.
<syntaxhighlight lang="ursala">gnome_sort "p" =
@NiX ^=lx -+ # iteration
~&r?\~& @lNXrX ->llx2rhPlrPCTxPrtPX~&lltPlhPrCXPrX ~&ll&& @llPrXh not "p", # backward bubble
->~&rhPlCrtPX ~&r&& ~&lZ!| @bh "p"+- # forward scan</syntaxhighlight>
Most of the code is wasted on dull but unavoidable stack manipulations.
Here is a test program using the lexical partial order relation.
<syntaxhighlight lang="ursala">#import std
#cast %s
t = gnome_sort(lleq) 'dfijhkwlawfkjnksdjnoqwjefgflkdsgioi'</syntaxhighlight>
output:
<pre>
'adddeffffgghiiijjjjkkkkllnnooqsswww'
</pre>
=={{header|VBScript}}==
====Implementation====
<
dim i
dim j
Line 1,564 ⟶ 4,483:
x = y
y = temp
end sub</
====Invocation====
<
dim b
Line 1,587 ⟶ 4,506:
a = array( now(), now()-1,now()+2)
b = gnomeSort( a )
wscript.echo join(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
2/02/2010 10:19:51 AM, 3/02/2010 10:19:51 AM, 5/02/2010 10:19:51 AM</
Note: All data in VBScript is of type Variant. Thus the code can sort many different types of data without code modification.
=={{header|
{{trans|go}}
<syntaxhighlight lang="v (vlang)">fn main() {
mut a := [170, 45, 75, -90, -802, 24, 2, 66]
println("before: $a")
gnome_sort(mut a)
println("after: $a")
}
fn gnome_sort(mut a []int) {
for i, j := 1, 2; i < a.len; {
if a[i-1] > a[i] {
a[i-1], a[i] = a[i], a[i-1]
i--
if i > 0 {
continue
}
}
i = j
j++
}
}</syntaxhighlight>
{{out}}
<pre>before: [170, 45, 75, -90, -802, 24, 2, 66]
after: [-802, -90, 2, 24, 45, 66, 75, 170]
</pre>
=={{header|Wren}}==
<syntaxhighlight lang="wren">var gnomeSort = Fn.new { |a, asc|
var size = a.count
var i = 1
var j = 2
while (i < size) {
if ((asc && a[i-1] <= a[i]) || (!asc && a[i-1] >= a[i])) {
i = j
j = j + 1
} else {
var t = a[i-1]
a[i-1] = a[i]
a[i] = t
i = i - 1
if (i == 0) {
i = j
j = j + 1
}
}
}
}
var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (asc in [true, false]) {
System.print("Sorting in %(asc ? "ascending" : "descending") order:\n")
for (a in array) {
var b = (asc) ? a : a.toList
System.print("Before: %(b)")
gnomeSort.call(b, asc)
System.print("After : %(b)")
System.print()
}
}</syntaxhighlight>
{{out}}
<pre>
Sorting in ascending order:
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
Before: [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
Sorting in descending order:
Before: [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
After : [782, 99, 83, 65, 4, 2, 2, 1, 0, -31]
Before: [1, 2, 2, 3, 4, 5, 6, 6, 7]
After : [7, 6, 6, 5, 4, 3, 2, 2, 1]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">code ChOut=8, IntOut=11;
proc GnomeSort(A(0..Size-1)); \Sort array A
int A, Size;
int I, J, T;
[I:= 1;
J:= 2;
while I < Size do
if A(I-1) <= A(I) then
[\ for descending sort, use >= for comparison
I:= J;
J:= J+1;
]
else
[T:= A(I-1); A(I-1):= A(I); A(I):= T; \swap
I:= I-1;
if I = 0 then
[I:= J;
J:= J+1;
];
];
];
int A, I;
[A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4];
GnomeSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</syntaxhighlight>
{{out}}
<pre>
-5 1 1 2 3 4 4 5 6 9
</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">fcn gnomeSort(a){
i,j,size := 1,2,a.len();
while(i < size){
if(a[i-1] > a[i]){ // for descending sort, use < for comparison
a.swap(i-1,i);
i = i - 1;
if(i) continue;
}
i = j;
j = j + 1;
}//while
a
}</syntaxhighlight>
<syntaxhighlight lang="zkl">gnomeSort("This is a test".split("")).println();</syntaxhighlight>
{{out}}
<pre>L(" "," "," ","T","a","e","h","i","i","s","s","s","t","t")</pre>
{{omit from|GUISS}}
| |||