(41) Quick Sort

[arhtur]

When using the DM41x, I found that a bubble sort took approximately 1 minute to sort 50 numbers. Since the DM41x is about 50 times as fast as a HP 41C, that means the HP 41C would take approx. 50 minutes to bubble sort 50 numbers.

I implemented a non-recursive version of quick sort based on a public domain algorithm by Darel Rex Finley. In quick sort, there is a begin array pointer (register 95), end array pointer (register 96), left pointer (register 97), right pointer (register 98) and pivot (register 92). There are a few more registers used for loop control, etc. The numbers to be sorted are in registers 0 to 49. I did SIZE 250 just to be safe. The begin array starts at register 120 and the end array starts at register 180. This version took about 31 seconds to sort 50 numbers on the DM41x. Because there’s a lot of overhead in this algorithm, it is only about twice as fast as the bubble sort.

To run the quicksort, first do SIZE 250. Store your unsorted numbers in registers 0 to 49. If you want to view the unsorted numbers, you can XEQ VIEWS (and repeatedly press R/S to see each number). Then XEQ QS. You can XEQ VIEWS again to see the sorted numbers.

Here is a simple DM41x program to fill the first 50 registers with random numbers using a time based random number generator:

LBL "FIL"
0.049
STO 91
LBL "FIL1"
TRNG
50
*
STO IND 91
ISG 91
GTO "FIL1"
RTN

Quick Sort Program:

Code:

LBL "QS"
180
STO 91
120
STO 95
RCL 91
STO 96
0
STO IND 95
50
STO IND 96
0
STO 90
LBL "Q1"
120
RCL 90
+
STO 95
RCL IND 95
STO 97
RCL 91
RCL 90
+
STO 96
RCL IND 96
1
-
STO 98
RCL 98
RCL 97
X<Y?
GTO "Q2"
1
ST- 90
GTO "Q10"
LBL "Q2"
RCL IND 97
STO 92
LBL "Q2A"
RCL 97
RCL 98
X<=Y?
GTO "Q3"
LBL "Q3A"
RCL 92
RCL IND 98
X<Y?
GTO "Q4"
RCL 97
RCL 98
X<=Y?
GTO "Q4"
1
ST- 98
GTO "Q3A"
LBL "Q4"
RCL 97
RCL 98
X<=Y?
GTO "Q5"
RCL IND 98
STO IND 97
1
ST+ 97
LBL "Q5"
RCL 92
RCL IND 97
X>Y?
GTO "Q6"
RCL 97
RCL 98
X<=Y?
GTO "Q6"
1
ST+ 97
GTO "Q5"
LBL "Q6"
RCL 97
RCL 98
X<=Y?
GTO "Q2A"
RCL IND 97
STO IND 98
1
ST- 98
GTO "Q2A"
LBL "Q3"
RCL 92
STO IND 97
RCL 90
1
+
120
+
STO 95
RCL 97
1
+
STO IND 95
RCL 90
1
+
RCL 91
+
STO 96
RCL 96
1
-
STO 93
RCL IND 93
STO IND 96
RCL 91
RCL 90
+
STO 96
RCL 97
STO IND 96
1
ST+ 90
LBL "Q10"
RCL 90
0
X<=Y?
GTO "Q1"
RTN
LBL "VIEWS"
0.049
STO 91
LBL "VIEWS1"
RCL IND 91
STOP
ISG 91
GTO "VIEWS1"
RTN
END