Sorting algorithms/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.
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
| This page uses content from Wikipedia. The original article was at Gnome sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
The pseudocode for the algorithm is:
function gnomeSort(a[0..size-1])
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
swap a[i-1] and a[i]
i := i - 1
if i = 0 then
i := j
j := j + 1
endif
endif
done
- Task
Implement the Gnome sort in your language to sort an array (or list) of numbers.
11l
<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]))</lang>
- Output:
[1, 2, 3, 4, 5, 6]
360 Assembly
<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</lang>
- Output:
-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
AArch64 Assembly
<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"
</lang>
Action!
<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</lang>
- Output:
Screenshot from Atari 8-bit computer
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]
ActionScript
<lang ActionScript>function gnomeSort(array:Array) { var pos:uint = 0; while(pos < array.length) { if(pos == 0 || array[pos] >= array[pos-1]) pos++; else { var tmp = array[pos]; array[pos] = array[pos-1]; array[pos-1] = tmp; pos--; } } return array; }</lang>
Ada
This example is a generic procedure for constrained array types. <lang Ada>generic
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);</lang>
<lang Ada>procedure Gnome_Sort(Item : in out Collection) is
procedure Swap(Left, Right : in out Element_Type) is
Temp : Element_Type := Left;
begin
Left := Right;
Right := Temp;
end Swap;
I : Integer := Index'Pos(Index'Succ(Index'First));
J : Integer := I + 1;
begin
while I <= Index'Pos(Index'Last) loop
if Item(Index'Val(I - 1)) <= Item(Index'Val(I)) then
I := J;
J := J + 1;
else
Swap(Item(Index'Val(I - 1)), Item(Index'Val(I)));
I := I - 1;
if I = Index'Pos(Index'First) then
I := J;
J := J + 1;
end if;
end if;
end loop;
end Gnome_Sort;</lang> Usage example: <lang Ada>with Gnome_Sort; with Ada.Text_Io; use Ada.Text_Io;
procedure Gnome_Sort_Test is
type Index is range 0..9; type Buf is array(Index) of Integer; procedure Sort is new Gnome_Sort(Integer, Index, Buf); A : Buf := (900, 700, 800, 600, 400, 500, 200, 100, 300, 0);
begin
for I in A'range loop
Put(Integer'Image(A(I)));
end loop;
New_Line;
Sort(A);
for I in A'range loop
Put(Integer'Image(A(I)));
end loop;
New_Line;
end Gnome_Sort_Test;</lang>
ALGOL 68
<lang algol68>MODE SORTSTRUCT = CHAR;
PROC inplace gnome sort = (REF[]SORTSTRUCT list)REF[]SORTSTRUCT: BEGIN
INT i:=LWB list + 1, j:=LWB list + 2;
WHILE i <= UPB list DO
IF list[i-1] <= list[i] THEN
i := j; j+:=1
ELSE
SORTSTRUCT swap = list[i-1]; list[i-1]:= list[i]; list[i]:= swap;
i-:=1;
IF i=LWB list THEN i:=j; j+:=1 FI
FI
OD;
list
END;
PROC gnome sort = ([]SORTSTRUCT seq)[]SORTSTRUCT:
in place gnome sort(LOC[LWB seq: UPB seq]SORTSTRUCT:=seq);
[]SORTSTRUCT char array data = "big fjords vex quick waltz nymph"; print((gnome sort(char array data), new line))</lang> Output:
abcdefghiijklmnopqrstuvwxyz
ARM Assembly
<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"
</lang>
Arturo
<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]</lang>
- Output:
1 2 3 4 5 6 7 8 9
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % GnomeSort("") MsgBox % GnomeSort("xxx") MsgBox % GnomeSort("3,2,1") MsgBox % GnomeSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")
GnomeSort(var) { ; SORT COMMA SEPARATED LIST
StringSplit a, var, `, ; make array, size = a0
i := 2, j := 3
While i <= a0 { ; stop when sorted
u := i-1
If (a%u% < a%i%) ; search for pairs to swap
i := j, j := j+1
Else { ; swap
t := a%u%, a%u% := a%i%, a%i% := t
If (--i = 1) ; restart search
i := j, j++
}
}
Loop % a0 ; construct string from sorted array
sorted .= "," . a%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}</lang>
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.
<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 ""
} </lang>
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
BASIC
<lang qbasic>dim a(0 to n-1) as integer '...more code... sort: i = 1 j = 2
while(i < ubound(a) - lbound(a))
if a(i-1) <= a(i) then
i = j
j = j + 1
else
swap a(i-1), a(i)
i = i - 1
if i = 0 then
i = j
j = j + 1
end if
end if
wend</lang>
Batch File
<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</lang>
BBC BASIC
<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</lang>
BCPL
<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')
$)</lang>
- Output:
Input: 52 -5 -20 199 65 -3 190 25 9999 -5342 Output: -5342 -20 -5 -3 25 52 65 190 199 9999
C
This algorithm sorts in place modifying the passed array (of n integer numbers).
<lang c>void gnome_sort(int *a, int n)
{
int i=1, j=2, t;
- define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; }
while(i < n) {
if (a[i - 1] > a[i]) {
swap(i - 1, i);
if (--i) continue;
}
i = j++;
}
- undef swap
}</lang>
C#
<lang csharp>
public static void gnomeSort(int[] anArray)
{
int first = 1;
int second = 2;
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;
}
}
}
}
</lang>
C++
Uses C++11. Compile with
g++ -std=c++11 gnome.cpp
<lang cpp>#include <algorithm>
- include <iterator>
- include <iostream>
template<typename RandomAccessIterator> void gnome_sort(RandomAccessIterator begin, RandomAccessIterator end) {
auto i = begin + 1;
auto j = begin + 2;
while (i < end) {
if (!(*i < *(i - 1))) {
i = j;
++j;
} else {
std::iter_swap(i - 1, i);
--i;
if (i == begin) {
i = j;
++j;
}
}
}
}
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";
}</lang> Output:
-199 -52 2 3 33 56 99 100 177 200
Clojure
<lang clojure>(defn gnomesort
([c] (gnomesort c <))
([c pred]
(loop [x [] [y1 & ys :as y] (seq c)]
(cond (empty? y) x
(empty? x) (recur (list y1) ys)
true (let [zx (last x)]
(if (pred y1 zx)
(recur (butlast x) (concat (list y1 zx) ys))
(recur (concat x (list y1)) ys)))))))
(println (gnomesort [3 1 4 1 5 9 2 6 5]))</lang>
COBOL
Procedure division stuff only. <lang COBOL> C-SORT SECTION.
C-000.
DISPLAY "SORT STARTING".
SET WB-IX-1 TO 2.
MOVE 1 TO WC-NEXT-POSN.
PERFORM E-GNOME UNTIL WC-NEXT-POSN > WC-SIZE.
DISPLAY "SORT FINISHED".
C-999.
EXIT.
E-GNOME SECTION.
E-000.
IF WB-ENTRY(WB-IX-1 - 1) NOT > WB-ENTRY(WB-IX-1)
ADD 1 TO WC-NEXT-POSN
SET WB-IX-1 TO WC-NEXT-POSN
ELSE
MOVE WB-ENTRY(WB-IX-1 - 1) TO WC-TEMP
MOVE WB-ENTRY(WB-IX-1) TO WB-ENTRY(WB-IX-1 - 1)
MOVE WC-TEMP TO WB-ENTRY(WB-IX-1)
SET WB-IX-1 DOWN BY 1
IF WB-IX-1 = 1
ADD 1 TO WC-NEXT-POSN
SET WB-IX-1 TO WC-NEXT-POSN.
E-999.
EXIT.</lang>
Common Lisp
<lang lisp>(defun gnome-sort (array predicate &aux (length (length array)))
(do ((position (min 1 length)))
((eql length position) array)
(cond
((eql 0 position)
(incf position))
((funcall predicate
(aref array position)
(aref array (1- position)))
(rotatef (aref array position)
(aref array (1- position)))
(decf position))
(t (incf position)))))</lang>
D
<lang d>import std.stdio, std.algorithm;
void gnomeSort(T)(T arr) {
int i = 1, j = 2;
while (i < arr.length) {
if (arr[i-1] <= arr[i]) {
i = j;
j++;
} else {
swap(arr[i-1], arr[i]);
i--;
if (i == 0) {
i = j;
j++;
}
}
}
}
void main() {
auto a = [3,4,2,5,1,6]; gnomeSort(a); writeln(a);
}</lang>
Delphi
Dynamic array is a 0-based array of variable length
Static array is an arbitrary-based array of fixed length <lang Delphi>program TestGnomeSort;
{$APPTYPE CONSOLE}
{.$DEFINE DYNARRAY} // remove '.' to compile with dynamic array
type
TItem = Integer; // declare ordinal type for array item
{$IFDEF DYNARRAY}
TArray = array of TItem; // dynamic array
{$ELSE}
TArray = array[0..15] of TItem; // static array
{$ENDIF}
procedure GnomeSort(var A: TArray); var
Item: TItem; I, J: Integer;
begin
I:= Low(A) + 1;
J:= Low(A) + 2;
while I <= High(A) do begin
if A[I - 1] <= A[I] then begin
I:= J;
J:= J + 1;
end
else begin
Item:= A[I - 1];
A[I - 1]:= A[I];
A[I]:= Item;
I:= I - 1;
if I = Low(A) then begin
I:= J;
J:= J + 1;
end;
end;
end;
end;
var
A: TArray; I: Integer;
begin {$IFDEF DYNARRAY}
SetLength(A, 16);
{$ENDIF}
for I:= Low(A) to High(A) do A[I]:= Random(100); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; GnomeSort(A); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; Readln;
end.</lang> Output:
0 3 86 20 27 67 31 16 37 42 8 47 7 84 5 29 0 3 5 7 8 16 20 27 29 31 37 42 47 67 84 86
DWScript
<lang delphi>procedure GnomeSort(a : array of Integer); var
i, j : Integer;
begin
i := 1;
j := 2;
while i < a.Length do begin
if a[i-1] <= a[i] then begin
i := j;
j := j + 1;
end else begin
a.Swap(i-1, i);
i := i - 1;
if i = 0 then begin
i := j;
j := j + 1;
end;
end;
end;
end;
var i : Integer; var a := new Integer[16];
Print('{'); for i := 0 to a.High do begin
a[i] := i xor 5;
Print(Format('%3d ', [a[i]]));
end; PrintLn('}');
GnomeSort(a);
Print('{'); for i := 0 to a.High do
Print(Format('%3d ', [a[i]]));
PrintLn('}'); </lang> Ouput :
{ 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 }
{ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 }
E
<lang e>def gnomeSort(array) {
var size := array.size()
var i := 1
var j := 2
while (i < size) {
if (array[i-1] <= array[i]) {
i := j
j += 1
} else {
def t := array[i-1]
array[i-1] := array[i]
array[i] := t
i -= 1
if (i <=> 0) {
i := j
j += 1
}
}
}
}</lang>
<lang e>? def a := [7,9,4,2,1,3,6,5,0,8].diverge()
- 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()</lang>
Eiffel
<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
</lang> Test: <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
</lang>
- Output:
Unsorted: 7 99 -7 1 0 25 -10 Sorted: -7 -10 0 1 7 25 99
Elena
ELENA 5.0 : <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())
}</lang>
- Output:
before:3,9,4,6,8,1,7,2,5 after :1,2,3,4,5,6,7,8,9
Elixir
<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])</lang>
- Output:
[1, 2, 3, 3, 6, 8, 9]
Erlang
<lang Erlang>-module(gnome_sort). -export([gnome/1]).
gnome(L, []) -> L; gnome([Prev|P], [Next|N]) when Next > Prev -> gnome(P, [Next|[Prev|N]]); gnome(P, [Next|N]) -> gnome([Next|P], N). gnome([H|T]) -> gnome([H], T).</lang> <lang Erlang>Eshell V5.7.3 (abort with ^G) 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> </lang>
Euphoria
<lang euphoria>function gnomeSort(sequence s)
integer i,j
object temp
i = 1
j = 2
while i < length(s) do
if compare(s[i], s[i+1]) <= 0 then
i = j
j += 1
else
temp = s[i]
s[i] = s[i+1]
s[i+1] = temp
i -= 1
if i = 0 then
i = j
j += 1
end if
end if
end while
return s
end function</lang>
F#
<lang fsharp>let inline gnomeSort (a: _ []) =
let rec loop i j =
if i < a.Length then
if a.[i-1] <= a.[i] then loop j (j+1) else
let t = a.[i-1]
a.[i-1] <- a.[i]
a.[i] <- t
if i=1 then loop j (j+1) else loop (i-1) j
loop 1 2</lang>
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 }
Fantom
<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))
}
} </lang>
Output:
[4, 1, 5, 8, 2, 1, 5, 7] sorted is [1, 1, 2, 4, 5, 5, 7, 8]
Forth
<lang forth>defer precedes defer exchange
- gnomesort ( a n)
swap >r 1 ( n c)
begin ( n c)
over over > ( n c f)
while ( n c)
dup if ( n c)
dup dup 1- over over r@ precedes
if r@ exchange 1- else drop drop 1+ then
else 1+ then ( n c)
repeat drop drop r> drop ( --)
create example
8 93 69 52 50 79 33 52 19 77 , , , , , , , , , ,
- noname >r cells r@ + @ swap cells r> + @ swap < ; is precedes
- noname >r cells r@ + swap cells r> + over @ over @ swap rot ! swap ! ; is exchange
- .array 10 0 do example i cells + ? loop cr ;
.array example 10 gnomesort .array</lang> A slightly optimized version is presented below, where Gnome sort keeps track of its previous position. This reduces the number of iterations significantly. <lang forth>: gnomesort+ ( a n)
swap >r 2 tuck 1- ( c2 n c1)
begin ( c2 n c1)
over over > ( c2 n c1 f)
while ( c2 n c1)
dup if ( c2 n c1)
dup dup 1- over over r@ precedes
if r@ exchange 1- else drop drop drop >r dup 1+ swap r> swap then
else drop >r dup 1+ swap r> swap then
repeat drop drop drop r> drop
- ( --)</lang>
Fortran
<lang fortran>program example
implicit none integer :: array(8) = (/ 2, 8, 6, 1, 3, 5, 4, 7 /)
call Gnomesort(array) write(*,*) array
contains
subroutine Gnomesort(a)
integer, intent(in out) :: a(:) integer :: i, j, temp
i = 2
j = 3
do while (i <= size(a))
if (a(i-1) <= a(i)) then
i = j
j = j + 1
else
temp = a(i-1)
a(i-1) = a(i)
a(i) = temp
i = i - 1
if (i == 1) then
i = j
j = j + 1
end if
end if
end do
end subroutine Gnomesort
end program example</lang>
FreeBASIC
Used the task pseudo code as a base <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</lang>
- Output:
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
Gambas
Click this link to run this code <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</lang> Output:
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
Go
<lang go>package main
import "fmt"
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
gnomeSort(a)
fmt.Println("after: ", a)
}
func gnomeSort(a []int) {
for i, j := 1, 2; i < len(a); {
if a[i-1] > a[i] {
a[i-1], a[i] = a[i], a[i-1]
i--
if i > 0 {
continue
}
}
i = j
j++
}
}</lang>
More generic version that sorts anything that implements sort.Interface:
<lang go>package main
import (
"sort" "fmt"
)
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
fmt.Println("before:", a)
gnomeSort(sort.IntSlice(a))
fmt.Println("after: ", a)
}
func gnomeSort(a sort.Interface) {
for i, j := 1, 2; i < a.Len(); {
if a.Less(i, i-1) {
a.Swap(i-1, i)
i--
if i > 0 {
continue
}
}
i = j
j++
}
}</lang>
Groovy
Solution: <lang groovy>def makeSwap = { a, i, j = i+1 -> print "."; aj,i = ai,j }
def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
def gnomeSort = { input ->
def swap = checkSwap.curry(input)
def index = 1
while (index < input.size()) {
index += (swap(index-1) && index > 1) ? -1 : 1
}
input
}</lang>
Test: <lang groovy>println (gnomeSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])) 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]))</lang>
Output:
..............................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99] .........................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
Haskell
<lang haskell>gnomeSort [] = [] gnomeSort (x:xs) = gs [x] xs
where
gs vv@(v:vs) (w:ws) | v<=w = gs (w:vv) ws | otherwise = gs vs (w:v:ws) 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 </lang>
Haxe
<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);
}
}</lang>
- Output:
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]
Icon and Unicon
<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</lang>
Note: This example relies on 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:
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)
Io
Naive version: <lang io>List do(
gnomeSortInPlace := method(
idx := 1
while(idx <= size,
if(idx == 0 or at(idx) > at(idx - 1)) then(
idx = idx + 1
) else(
swapIndices(idx, idx - 1)
idx = idx - 1
)
)
self)
)
lst := list(5, -1, -4, 2, 9) lst gnomeSortInPlace println # ==> list(-4, -1, 2, 5, 9)</lang>
Optimized version, storing the position before traversing back towards the begining of the list (Wikipedia) <lang io>List do(
gnomeSortInPlace := method(
idx1 := 1
idx2 := 2
while(idx1 <= size,
if(idx1 == 0 or at(idx1) > at(idx1 - 1)) then(
idx1 = idx2
idx2 = idx2 + 1
) else(
swapIndices(idx1, idx1 - 1)
idx1 = idx1 - 1
)
)
self)
)
lst := list(5, -1, -4, 2, 9) lst gnomeSortInPlace println # ==> list(-4, -1, 2, 5, 9)</lang>
IS-BASIC
<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</lang>
J
<lang J>position=: 0 {.@I.@, [ swap=: ] A.~ *@position * #@[ !@- <:@position gnome=: swap~ 2 >/\ ] gnomes=: gnome^:_</lang>
Note 1: this implementation of swap is actually rather silly, and will not work on long lists. A better implementation would be:<lang J>swap=: position (] {~ _1 0 + [)`(0 _1 + [)`]}^:(*@[) ]</lang>
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:<lang J>gt=: -.@(-: /:~)@,&< gnome=: swap~ 2 gt/\ ]</lang>
Note 3: this implementation does not return intermediate results. If you want them, you could use<lang J>gnomeps=: gnome^:a:</lang>
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<lang J>2 ~:/\ gnomeps</lang>.
Java
<lang java>public static void gnomeSort(int[] a) {
int i=1;
int j=2;
while(i < a.length) {
if ( a[i-1] <= a[i] ) {
i = j; j++;
} else {
int tmp = a[i-1];
a[i-1] = a[i];
a[i--] = tmp;
i = (i==0) ? j++ : i;
}
}
}</lang>
JavaScript
<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;
}</lang>
jq
This implementation adheres to the specification. The array to be sorted, however, can be any JSON array. <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];</lang>
Example: <lang jq>[(2|sqrt), [1], null, 1, 0.5, 2, 1, -3, {"a": "A"}] | gnomeSort</lang>
- Output:
<lang sh>$ jq -M -n -f Gnome_sort.jq [
null,
-3,
0.5,
1,
1,
1.4142135623730951,
2,
[
1
],
{
"a": "A"
}
]</lang>
Julia
<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))</lang>
- Output:
# unordered: [9, -8, 0, 3, 2, 10, 5, 4, 5, 5] -> ordered: [-8, 0, 2, 3, 4, 5, 5, 5, 9, 10]
Kotlin
<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()}")
}</lang>
- Output:
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]
Lua
Keep in mind that Lua arrays initial index is 1. <lang lua>function gnomeSort(a)
local i, j = 2, 3
while i <= #a do
if a[i-1] <= a[i] then
i = j
j = j + 1
else
a[i-1], a[i] = a[i], a[i-1] -- swap
i = i - 1
if i == 1 then -- 1 instead of 0
i = j
j = j + 1
end
end
end
end</lang> Example: <lang lua>list = { 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97 } gnomeSort(list) for i, j in pairs(list) do
print(j)
end</lang>
Maple
<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;</lang>
- Output:
[0,0,2,3,3,8,17,36,40,72]
Mathematica/Wolfram Language
<lang Mathematica>gnomeSort[list_]:=Module[{i=2,j=3}, While[ i<=Lengthlist, If[ listi-1<=listi,
i=j; j++;, listi-1;;i=listi;;i-1;i--;];
If[i==1,i=j;j++;] ]]</lang>
MATLAB / Octave
<lang MATLAB>function list = gnomeSort(list)
i = 2;
j = 3;
while i <= numel(list)
if list(i-1) <= list(i)
i = j;
j = j+1;
else
list([i-1 i]) = list([i i-1]); %Swap
i = i-1;
if i == 1
i = j;
j = j+1;
end
end %if
end %while
end %gnomeSort</lang>
Sample Usage: <lang MATLAB>>> gnomeSort([4 3 1 5 6 2])
ans =
1 2 3 4 5 6</lang>
MAXScript
<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 )</lang> Output: <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)
</lang>
Metafont
<lang metafont>def gnomesort(suffix v)(expr n) = begingroup save i, j, t;
i := 1; j := 2;
forever: exitif not (i < n);
if v[i-1] <= v[i]:
i := j; j := j + 1;
else:
t := v[i-1];
v[i-1] := v[i];
v[i] := t;
i := i - 1;
i := if i=0: j; j := j + 1 else: i fi;
fi
endfor
endgroup enddef;</lang>
<lang metafont>numeric a[]; 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 end</lang>
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols binary
import java.util.List
i1 = ArrayList(Arrays.asList([Integer(3), Integer(3), Integer(1), Integer(2), Integer(4), Integer(3), Integer(5), Integer(6)])) say i1.toString say gnomeSort(i1).toString
return
method isTrue public constant binary returns boolean
return 1 == 1
method isFalse public constant binary returns boolean
return \isTrue
method gnomeSort(a = String[], sAsc = isTrue) public constant binary returns String[]
rl = String[a.length] al = List gnomeSort(Arrays.asList(a), sAsc) al.toArray(rl)
return rl
method gnomeSort(a = List, sAsc = isTrue) public constant binary returns ArrayList
sDsc = \sAsc -- Ascending/descending switches
ra = ArrayList(a)
i_ = 1
j_ = 2
loop label i_ while i_ < ra.size
ctx = (Comparable ra.get(i_ - 1)).compareTo(Comparable 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
</lang>
- Output
[3, 3, 1, 2, 4, 3, 5, 6] [1, 2, 3, 3, 3, 4, 5, 6]
Nim
<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</lang> Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]
Objeck
<lang objeck> function : GnomeSort(a : Int[]) {
i := 1; j := 2;
while(i < a->Size()) {
if (a[i-1] <= a[i]) {
i := j;
j += 1;
}
else {
tmp := a[i-1];
a[i-1] := a[i];
a[i] := tmp;
i -= 1;
if(i = 0) {
i := j;
j += 1;
};
};
};
} </lang>
OCaml
from the toplevel: <lang ocaml># let gnome_sort a =
let i = ref 1
and j = ref 2 in
while !i < Array.length a do
if a.(!i-1) <= a.(!i) then
begin
i := !j;
j := !j + 1;
end else begin
swap a (!i-1) (!i);
i := !i - 1;
if !i = 0 then begin
i := !j;
j := !j + 1;
end;
end;
done;
;;
val gnome_sort : 'a array -> unit = <fun>
- let a = [| 7; 9; 4; 2; 1; 3; 6; 5; 0; 8; |] ;;
val a : int array = [|7; 9; 4; 2; 1; 3; 6; 5; 0; 8|]
- gnome_sort a ;;
- : unit = ()
- a ;;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]</lang>
Octave
<lang octave>function s = gnomesort(v)
i = 2; j = 3;
while ( i <= length(v) )
if ( v(i-1) <= v(i) )
i = j;
j++;
else
t = v(i-1);
v(i-1) = v(i);
v(i) = t;
i--;
if ( i == 1 )
i = j; j++;
endif endif endwhile s = v;
endfunction</lang>
<lang octave>v = [7, 9, 4, 2, 1, 3, 6, 5, 0, 8]; disp(gnomesort(v));</lang>
ooRexx
version 1
<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
</lang> Output:
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
version 2
<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</lang>
output Similar to REXX version 2
Oz
<lang oz>declare
fun {GnomeSort Xs}
case Xs of nil then nil
[] X|Xr then {Loop [X] Xr}
end
end
fun {Loop Vs Ws}
case [Vs Ws]
of [V|_ W|Wr] andthen V =< W then {Loop W|Vs Wr}
[] [V|Vr W|Wr] then {Loop Vr W|V|Wr}
[] [nil W|Wr] then {Loop [W] Wr}
[] [Vs nil ] then {Reverse Vs}
end
end
in
{Show {GnomeSort [3 1 4 1 5 9 2 6 5]}}</lang>
PARI/GP
<lang parigp>gnomeSort(v)={
my(i=2,j=3,n=#v,t);
while(i<=n,
if(v[i-1]>v[i],
t=v[i];
v[i]=v[i-1];
v[i--]=t;
if(i==1, i=j; j++);
,
i=j;
j++
)
);
v
};</lang>
Pascal
<lang pascal>procedure gnomesort(var arr : Array of Integer; size : Integer); var
i, j, t : Integer;
begin
i := 1;
j := 2;
while i < size do begin
if arr[i-1] <= arr[i] then
begin
i := j; j := j + 1
end
else begin
t := arr[i-1]; arr[i-1] := arr[i]; arr[i] := t; i := i - 1; if i = 0 then begin i := j; j := j + 1 end
end end;
end;</lang>
Perl
<lang perl>use strict;
sub gnome_sort {
my @a = @_;
my $size = scalar(@a);
my $i = 1;
my $j = 2;
while($i < $size) {
if ( $a[$i-1] <= $a[$i] ) { $i = $j; $j++; } else { @a[$i, $i-1] = @a[$i-1, $i]; $i--; if ($i == 0) { $i = $j; $j++; } }
} return @a;
}</lang>
<lang perl>my @arr = ( 10, 9, 8, 5, 2, 1, 1, 0, 50, -2 ); print "$_\n" foreach gnome_sort( @arr );</lang>
Phix
with javascript_semantics function gnomeSort(sequence s) integer i = 1, j = 2 while i<length(s) do object si = s[i], sn = s[i+1] if si<=sn then i = j j += 1 else s[i] = sn s[i+1] = si i -= 1 if i = 0 then i = j j += 1 end if end if end while return s end function ?gnomeSort(shuffle(tagset(10)))
PHP
<lang php>function gnomeSort($arr){ $i = 1; $j = 2; while($i < count($arr)){ if ($arr[$i-1] <= $arr[$i]){ $i = $j; $j++; }else{ list($arr[$i],$arr[$i-1]) = array($arr[$i-1],$arr[$i]); $i--; if($i == 0){ $i = $j; $j++; } } } return $arr; } $arr = array(3,1,6,2,9,4,7,8,5); echo implode(',',gnomeSort($arr));</lang>
1,2,3,4,5,6,7,8,9
PicoLisp
<lang PicoLisp>(de gnomeSort (Lst)
(let J (cdr Lst)
(for (I Lst (cdr I))
(if (>= (cadr I) (car I))
(setq I J J (cdr J))
(xchg I (cdr I))
(if (== I Lst)
(setq I J J (cdr J))
(setq I (prior I Lst)) ) ) ) )
Lst )</lang>
PL/I
<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 t fixed; declare (i, j) fixed;
i = 1; j = 2;
do while (i <= hbound(A));
if a(i-1) <= a(i) then
do;
i = j; j = j + 1;
end;
else
do;
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;
end;
END GNOME_SORT;
END SORT;</lang> Results:
0 1 2 3 4 5 6 7 8 9
PowerBASIC
The 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.
<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</lang>
Sample output:
7426 , 7887 , 8297 , 2671 , 7586 , 7160 , 1195 , 665 , 9352 , 6199 , 665 , 1195 , 2671 , 6199 , 7160 , 7426 , 7586 , 7887 , 8297 , 9352 ,
PowerShell
<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)" </lang> Output:
3 8 11 19 21 36 60 63 80 87 100
PureBasic
<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</lang>
Python
<lang python>>>> def gnomesort(a): i,j,size = 1,2,len(a) while i < size: if a[i-1] <= a[i]: i,j = j, j+1 else: a[i-1],a[i] = a[i],a[i-1] i -= 1 if i == 0: i,j = j, j+1 return a
>>> gnomesort([3,4,2,5,1,6]) [1, 2, 3, 4, 5, 6] >>></lang>
Quackery
<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 ( [ --> [ )</lang>
R
Starting from 1
<lang r>gnomesort <- function(x) {
i <- 1
j <- 1
while(i < length(x))
{
if(x[i] <= x[i+1])
{
i <- j
j <- j+1
} else
{
temp <- x[i]
x[i] <- x[i+1]
x[i+1] <- temp
i <- i - 1
if(i == 0)
{
i <- j
j <- j+1
}
}
}
x
} gnomesort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</lang>
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. <lang r>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")</lang>
- Output:
> gnomeSort(ints) [1] -19 -1 0 1 2 4 5 5 10 23 > 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"
Racket
<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) . ,xs)])
(match x
[`(,ps) ps]
[`((,p . ,ps) ,n . ,ns)
(loop (cond [(<=? n p) `((,n ,p . ,ps) . ,ns)]
[(null? ps) `((,n) ,p . ,ns)]
[else `(,ps ,n ,p . ,ns)]))]))]))
(gnome-sort2 '(3 2 1 4 5 6) <=) </lang>
Raku
(formerly Perl 6)
<lang perl6>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;
}
}
}</lang>
my @n = (1..10).roll(20); say @n.&gnome_sort ~~ @n.sort ?? 'ok' !! 'not ok';
Rascal
<lang rascal>import List;
public list[int] gnomeSort(a){ i = 1; 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; }</lang>
An example output:
<lang rascal>gnomeSort([4, 65, 2, -31, 0, 99, 83, 782, 1]) list[int]: [-31,0,1,2,4,65,83,99,782]</lang>
REXX
version 1
This REXX version uses an unity-based array (instead of a zero-based array). <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</lang>
- output:
(Shown at three-quarter size.)
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
version 2
<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
</lang> output
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
Ring
<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
</lang>
Ruby
<lang ruby>class Array
def gnomesort!
i, j = 1, 2
while i < length
if self[i-1] <= self[i]
i, j = j, j+1
else
self[i-1], self[i] = self[i], self[i-1]
i -= 1
if i == 0
i, j = j, j+1
end
end
end
self
end
end ary = [7,6,5,9,8,4,3,1,2,0] ary.gnomesort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Rust
<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);
}</lang>
- Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Scala
<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
}
}
}</lang>
Scheme
<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)
(let gnome ((p (list (car input-list)))
(n (cdr input-list)))
(if (null? n) ; no more flowerpots?
p ; we're done
(let ((prev-pot (car p))
(next-pot (car n)))
(if (in-order next-pot prev-pot)
; if the pots are in order, step forwards.
; otherwise, exchange the two pots, and step backwards.
(gnome (cons next-pot p) ; Prev list grows
(cdr n)) ; Next list shorter by one
(if (null? (cdr p)) ; are we at the beginning?
(gnome ; if so, we can't step back
(list next-pot) ; simply exchange the pots without
(cons prev-pot (cdr n))) ; changing lengths of lists
(gnome
(cdr p) ; Prev list shorter by one
(cons next-pot (cons prev-pot (cdr n))))))))))</lang>
#;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)
Sidef
<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;</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Smalltalk
<lang smalltalk>Smalltalk at: #gnomesort put: nil.
"Utility" OrderedCollection extend [
swap: a with: b [ |t|
t := self at: a.
self at: a put: b.
self at: b put: t
]
].
"Gnome sort as block closure" gnomesort := [ :c |
|i j|
i := 2. j := 3.
[ i <= (c size) ]
whileTrue: [
(c at: (i-1)) <= (c at: i)
ifTrue: [
i := j copy.
j := j + 1.
]
ifFalse: [
c swap: (i-1) with: i.
i := i - 1.
i == 1
ifTrue: [
i := j copy.
j := j + 1
]
]
]
].</lang>
Testing
<lang smalltalk>|r o| r := Random new. o := OrderedCollection new.
1 to: 10 do: [ :i | o add: (r between: 0 and: 50) ].
gnomesort value: o.
1 to: 10 do: [ :i | (o at: i) displayNl ].</lang>
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.
<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) :S(GNOME.FORWARD)
swap(.gnome<j>, .gnome)
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) :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</lang>
The test script looks like this: <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</lang>
Swift
<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)")</lang>
- Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Tcl
<lang tcl>package require Tcl 8.5 package require struct::list
proc gnomesort {a} {
set i 1
set j 2
set size [llength $a]
while {$i < $size} {
if {[lindex $a [expr {$i - 1}]] <= [lindex $a $i]} {
set i $j
incr j
} else {
struct::list swap a [expr {$i - 1}] $i
incr i -1
if {$i == 0} {
set i $j
incr j
}
}
}
return $a
}
puts [gnomesort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
TI-83 BASIC
Store input into L1, run prgmSORTGNOM, output will be in L2.
:1→P :L1→L2 :While P<dim(L2) :If PP=1 :Then :P+1→P :Else :If L2(P)≥L2(P-1) :Then :P+1→P :Else :L2(P)→Q :L2(P-1)→L2(P) :Q→L2(P-1) :P-1→P :End :End :End :If L2(dim(L2))<L2(dim(L2)-1) :Then :L2(dim(L2))→Q :L2(dim(L2)-1)→L2(dim(L2)) :Q→L2(dim(L2)-1) :End :DelVar P :DelVar Q :Return
True BASIC
<lang qbasic> RANDOMIZE !RAMDOMZE 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 </lang>
uBasic/4tH
<lang>PRINT "Gnome sort:"
n = FUNC (_InitArray) PROC _ShowArray (n) PROC _Gnomesort (n) PROC _ShowArray (n)
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</lang>
Ursala
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. <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</lang>
Most of the code is wasted on dull but unavoidable stack manipulations. Here is a test program using the lexical partial order relation. <lang Ursala>#import std
- cast %s
t = gnome_sort(lleq) 'dfijhkwlawfkjnksdjnoqwjefgflkdsgioi'</lang> output:
'adddeffffgghiiijjjjkkkkllnnooqsswww'
VBA
<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</lang>
- Output:
1, 1, 1, 3, 4, 5, 7, 20
VBScript
Implementation
<lang vb>function gnomeSort( a ) dim i dim j i = 1 j = 2 do while i < ubound( a ) + 1 if a(i-1) <= a(i) then i = j j = j + 1 else swap a(i-1), a(i) i = i - 1 if i = 0 then i = j j = j + 1 end if end if loop gnomeSort = a end function
sub swap( byref x, byref y ) dim temp temp = x x = y y = temp end sub</lang>
Invocation
<lang vb>dim a dim b
a = array( "zanzibar", "aardvark","ampicillin","zulu","gogodala", "wolverhampton") b = gnomeSort( a ) wscript.echo join(a, ", ")
a = array( 234,567,345,568,2345,89,547,23,649,5769,456,456,567) b = gnomeSort( a ) wscript.echo join(a, ", ")
a = array( true, false, true, true, false, false, true, false) b = gnomeSort( a ) wscript.echo join(a, ", ")
a = array( 1,2,2,4,67789,-3,-45.99) b = gnomeSort( a ) wscript.echo join(a, ", ")
a = array( now(), now()-1,now()+2) b = gnomeSort( a ) wscript.echo join(a, ", ")</lang>
Output
<lang VBScript>aardvark, ampicillin, gogodala, wolverhampton, zanzibar, zulu 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</lang> Note: All data in VBScript is of type Variant. Thus the code can sort many different types of data without code modification.
Wren
<lang ecmascript>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 as = [ [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 as) {
var b = (asc) ? a : a.toList
System.print("Before: %(b)")
gnomeSort.call(b, asc)
System.print("After : %(b)")
System.print()
}
}</lang>
- Output:
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]
XPL0
<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, ^ )]; ]</lang>
- Output:
-5 1 1 2 3 4 4 5 6 9
zkl
<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
}</lang> <lang zkl>gnomeSort("This is a test".split("")).println();</lang>
- Output:
L(" "," "," ","T","a","e","h","i","i","s","s","s","t","t")