+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP-41C Software Library (/forum-11.html)
+--- Thread: Heapsort (/thread-5079.html)
Heapsort - Werner - 11-05-2015 12:30 PM
sorts a contiguous block aaa,bbb. Uses M,N,O,Q
113 bytes including END
Code:
01>LBL"HSORT" -- In: a,b
02 ENTER
03 FRC
04 E3
05 x
06 X<Y? -- less than 2 elements
07 RTN
08 STO O -- O: b
09 X<>Y
10 1
11 -
12 STO M -- M: a-1,b
13 INT
14 -
15 2
16 /
17 INT
18 STO N -- N: INT(n/2), n = b-a+1
19>LBL 02 -- heapify
20 RCL N
21 RCL M
22 +
23 XEQ 10
24 DSE N
25 GTO 02
26>LBL 03 -- sort heap
27 E-3
28 ST- L
29 LASTX
30 ISG X
31 X=0?
32 RTN
33 RCL IND X
34 X<> IND O
35 STO IND Y
36 Rv
37 DSE O
38 XEQ 10
39 GTO 03
40>LBL 04 -- two leaves
41 RCL IND Y
42 RCL IND Y
43 X<Y?
44 CLX
45 RCL IND Q
46 X<>Y
47 X<=Y?
48 RTN
49 X<> IND Q
50 STO IND T
51 R^
52>LBL 10 -- SiftDown(i,b) L: a-1,b X: i,b
53 STO Q -- Q:i
54 ST+ X
55 LASTX
56 -
57 ENTER
58 ISG Y -- X:2i Y:2i+1
59 GTO 04
60 DSE Y
61 RTN -- no leaves
62 RCL IND Q -- one leaf & end
63 RCL IND Y
64 X<=Y?
65 RTN
66 X<> IND Q
67 STO IND Z
68 ENDCheers, Werner