HP Forums
(41) Quick Sort - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP-41C Software Library (/forum-11.html)
+--- Thread: (41) Quick Sort (/thread-18089.html)

(41) Quick Sort - arhtur - 03-01-2022 04:56 AM

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


RE: (41) Quick Sort - Gene - 03-01-2022 12:28 PM

I'd like to see what the PPC ROM routines S2 and S3 do with large data sets on the DM41X.

RE: (41) Quick Sort - Sylvain Cote - 03-01-2022 04:08 PM

(03-01-2022 12:28 PM)Gene Wrote:  I'd like to see what the PPC ROM routines S2 and S3 do with large data sets on the DM41X.

DM41X Results (DMCP 3.2 & DM41X 2.1)
Code:
R= 25  //  Power:USB  //  S2=  0s 66  //  S3=      0s 71
R= 50  //  Power:USB  //  S2= n/a     //  S3=      1s 86
R=100  //  Power:USB  //  S2= n/a     //  S3=      3s 92

R= 25  //  Power:bat  //  S2=  2s  7  //  S3=      2s 23
R= 50  //  Power:bat  //  S2= n/a     //  S3=      5s 91
R=100  //  Power:bat  //  S2= n/a     //  S3=     12s 43

41CL Results (latest update)
Code:
R= 25  //  Turbo:x50  //  S2=  2s 12  //  S3=      2s 18
R= 50  //  Turbo:x50  //  S2= n/a     //  S3=      5s 62
R=100  //  Turbo:x50  //  S2= n/a     //  S3=     11s 92

R= 25  //  Turbo:x10  //  S2=  4s 10  //  S3=      4s 54 
R= 50  //  Turbo:x10  //  S2= n/a     //  S3=     11s 31
R=100  //  Turbo:x10  //  S2= n/a     //  S3=     23s 90

R= 25  //  Turbo: x0  //  S2= 26s 94  //  S3=     28s 85
R= 50  //  Turbo: x0  //  S2= n/a     //  S3=  1m 15s 77
R=100  //  Turbo: x0  //  S2= n/a     //  S3=  2m 41s 68

Test
Code:
CLRG
0             // seed
.024          // registers, R50 use .049 and R100 uses .099
XEQ "DTALD"
.024          // registers, R50 use .049 and R100 uses .099
XEQ "DTAS2"   // or XEQ "DTAS3"

Data Loader → Y=random-generator-seed X=Registers SSS.EEEII
Code:
LBL "DTALD"
X<>Y
LBL 00
XEQ 10
STO IND Y
ISG Y
GTO 00
CLST
RTN
Random Number Generator (from Games Pac)
Code:
LBL 10
9821
*
.211327
+
FRC
RTN
Data Sorter with S2 → X=Registers SSS.EEEII (<= 32 registers)
Code:
LBL "DTAS2"
0
SETSW
RDN
RUNSW
XROM "S2"
STOPSW
RCLSW
RTN
Data Sorter with S3 → X=Registers SSS.EEEII
Code:
LBL "DTAS3"
CF 26      // disable sound to remove S3 BEEP bias
0
SETSW
RDN
RUNSW
XROM "S3"
STOPSW
RCLSW
RTN


RE: (41) Quick Sort - Gene - 03-02-2022 12:24 PM

Wow, S2 and S3 are incredibly fast !
ty Sylvain.

Gene

RE: (41) Quick Sort - Sylvain Cote - 03-02-2022 02:15 PM

(03-02-2022 12:24 PM)Gene Wrote:  Wow, S2 and S3 are incredibly fast !
I was surprised by the sort times. Both calculators under normal usage (DM41X bat & 41CL 50x), are 13.X times faster than the original calculator in this scenario.

(03-02-2022 12:24 PM)Gene Wrote:  ty Sylvain.
My pleasure Gene.