The Museum of HP Calculators

HP Forum Archive 19

 HP 35s Bubble SortMessage #1 Posted by Elliott W Jackson on 14 Feb 2009, 12:12 a.m. 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.

 Re: HP 35s Bubble SortMessage #2 Posted by Marcus von Cube, Germany on 14 Feb 2009, 4:36 a.m.,in response to message #1 by Elliott W Jackson 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.

Go back to the main exhibit hall