HP 35s Bubble Sort



#3

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


#4

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.


Possibly Related Threads…
Thread Author Replies Views Last Post
  Rearanging the "Fixed" sort order of Prime's Apps icons Joe Horn 3 1,781 10-02-2013, 10:24 AM
Last Post: Han
  Sort of OT: Dice odds Dave Britten 9 3,167 09-13-2011, 01:29 PM
Last Post: Kiyoshi Akima
  Symbolic math with the 35s (well.. sort of) Dieter 4 1,700 08-28-2010, 01:35 AM
Last Post: Karl Schneider
  Why are Serial Ports so Annoying? 49G But sort of Off Topic bill platt 5 1,692 03-02-2010, 11:50 AM
Last Post: Ron Ross
  Random Number Generation Challenge (sort of) Namir 9 2,585 02-15-2010, 08:05 AM
Last Post: Bart (UK)
  OT sort-of: Reverse Engineering Calculator OS Chuck 4 1,520 10-14-2009, 09:49 AM
Last Post: Tom Mathes
  HP 35s Gnome Sort Elliott W Jackson 0 788 02-13-2009, 10:52 PM
Last Post: Elliott W Jackson
  HP35s Program Logger (sort of) Chuck 2 1,100 10-10-2007, 01:20 PM
Last Post: Jeff O.
  hp 50g sort order in Filer Rich Messeder (US) 10 2,623 11-27-2006, 01:01 AM
Last Post: James M. Prange (Michigan)
  RPN Stack Sort Problem Katie Wasserman 15 3,575 07-26-2006, 07:20 PM
Last Post: Paul Dale

Forum Jump: