The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

HP 35s Bubble Sort
Message #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 Sort
Message #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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall