# HP Forums

Full Version: HP 35s Bubble Sort
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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.

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.