HP Forums

Full Version: HP 35s Bubble Sort
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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 )
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 RTN

LN=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.

Bubble sort isn't bad, if the items are "in almost sort order" at the beginning of the algorithm. If all items are already sorted, a single pass is all to find that out. Bubble sort is stable, too, that is, it leaves the original sorting of items considered "equal" by the comparison algorithm intact.