HP Forums
HP 35s Bubble Sort - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: HP 35s Bubble Sort (/thread-146887.html)

HP 35s Bubble Sort - Elliott W Jackson - 02-14-2009

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.

Re: HP 35s Bubble Sort - Marcus von Cube, Germany - 02-14-2009

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.