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