# HP Forums

Full Version: (41) Quick Sort
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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```
I'd like to see what the PPC ROM routines S2 and S3 do with large data sets on the DM41X.
(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```
Wow, S2 and S3 are incredibly fast !
ty Sylvain.

Gene
(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.
Reference URL's
• HP Forums: https://www.hpmuseum.org/forum/index.php
• :