Sunday, May 9, 2021

HP 12C: Bubble Sort

HP 12C: Bubble Sort


Sorting Numbers


The program below uses a bubble sort to sort the numbers in stacks R1, R2, R3, and R4 (this can be varied).   A bubble sort is a simple, but timely, sorting algorithm by taking two elements and swapping them if needed.  The bubble sort algorithm does not have a mechanism to determine if the sort is completed, therefore several passes are required to guarantee that everything is sorted properly.   


I recommend that you use the newer 12C calculators (those that are powered with 2 CR2032 batteries, for instance, manufactured today) due to the increase in processing speed.


An example sort:

74, 56, 66, 82


Numbers that are compared are in red. 


Pass 1:

74, 56, 66, 82

56, 74, 66, 82

56, 66, 74, 82


Pass 2:

56, 66, 74, 82

56, 66, 74, 82

56, 66, 74, 82


At this point we know the sort is done, but the algorithm does not know it.  


Pass 3:

56, 66, 74, 82

56, 66, 74, 82

56, 66, 74, 82


Final:

56, 66, 74, 82



HP 12C Program:  Bubble Sort of Four Numbers


This program sorts the numbers in the registers R1, R2, R3, and R4.  A counter number is stored in R0.  


STEP KEY         KEY CODE

01 3         3 // store the counter, n-1 numbers    

02 STO 0 44, 0

03 RCL 4 45, 4 // main loop starts here

04 RCL 3 45, 3

05 x ≤ y 43, 34

06 x <> y 34

07 STO 4 44, 4

08 R ↓         33

09 STO 3 44, 3

10 RCL 2 45, 2

11 x ≤ y 43, 34

12 x <> y 34

13 STO 3 44, 3

14 R ↓         33

15 STO 2 44, 2

16 RCL 1 45, 1

17 x ≤ y 43, 34

18 x <> y 34

19 STO 2 44, 2

20 R ↓         33

21 STO 1 44, 1

22 1         1

23 STO- 0         44, 30, 0

24 RCL 0 45, 0

25 x = 0 43, 35

26 GTO 00         43, 33, 00 // if R0 = 0, end the program

27 GTO 03         43, 33, 03 // if not, repeat the main loop


Instructions


1.  Store four numbers in the registers R1, R2, R3, and R4.

2.  Run the program.  A 0 will indicate when the program is done.

3.  Numbers stored in ascending order will be stored:  least in R1 to most in R4.


You can modify the program to include as many registers as memory allows.  Keep in mind the structure:


n-1 //  n = number of registers

STO 0

// start main loop

RCL i

RCL i-1

x ≤ y

x <> y

STO i

R ↓

STO i-1 // reduce i by 1 until i = 2

// adjust counter

1 // last lines start here, need at least 6 lines for this

STO- 0

RCL 0

x = 0

GTO 00

GTO 03


Examples


Example 1:

R1:  866, R2:  501, R3:  928, R4: 563

Result:

R1:  501, R2:  562, R3:  866,  R4:  928


Example 2:

R1:  314, R2:  506,  R3:  497,  R4:  621

Result:

R1:  314, R2:  497,  R3:  506,  R4:  621


Example 3:

R1:  -76,  R2:  68,  R3:  94,  R4: -11

Result:

R1:  -76,  R2:  -11, R3:  68,  R4:  94


Source


Personal Programmers Club. (various authors)   "Special Routines Issue"  Vol. 5 No. 7 August 1978  Publication: Santa Ana, CA 


Eddie


All original content copyright, © 2011-2021.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.