02-14-2009, 12:12 AM

The Wiki site claims the Gnome Sort to be the simplest, but it turns out that converting the Bubble Sort to HP GTO-ese is actually simpler, and has faster run times too.

Pseudo code:

procedure bubbleSort( A : list of sortable items ) defined as:

n := length( A )

do

swapped := false

n := n - 1

for each i in 0 to n - 1 inclusive do:

if A[ i ] > A[ i + 1 ] then

swap( A[ i ], A[ i + 1 ] )

swapped := true

end if

end for

while swapped

end procedure

Program listing:

S001 LBL S

S002 STO Z bbb.eee

S003 CF 0 start of do-while

S004 0.001

S005 STO- Z bbb.(eee - 1)

S006 RCL Z

S007 STO I for (I = bbb; I <= eee - 1; i++)

S008 RCL I

S009 1

S010 +

S011 STO J

S012 RCL(J) A[i+1]

S013 RCL(I) A[i]

S014 x<=y?

S015 GTO S020

S016 STO(J) A[i+1] = A[i]

S017 RDN

S018 STO(I) A[i] = A[i+1]

S019 SF 0 swapped = true

S020 ISG I

S021 GTO S008

S022 FS? 0 swapped = true?

S023 GTO S003

S024 RTNLN=78 CK=B7E4

And finally, some timings:

21 registers, 10.030: 23 seconds

21 registers, 10.030: 24 seconds

101 registers, 10.110: ~10 minutes

So, even the much-detested Bubble Sort is superior to the cutesy Gnome Sort I started this project with.