Heap-Sort
Implementierung des Heap-Sort Algorithmus auf programmierbaren Taschenrechnern.
TI-58C Code für Heap-Sort :
000 76 Lbl 001 92 RTN 002 92 RTN 003 76 Lbl # swap bedingt 004 11 A 005 22 INV 006 77 x≥t? 007 92 RTN 008 67 x=t? 009 92 RTN 010 76 Lbl # swap 011 16 A' 012 63 Exc Ind 013 24 24 014 63 Exc Ind 015 25 25 016 63 Exc Ind 017 24 24 018 86 St flg 019 01 1 020 92 RTN 021 76 Lbl # node + leaf pointer setzen 022 23 lnx 023 53 ( 024 43 RCL 025 24 24 026 65 x 027 02 2 028 54 ) 029 42 STO 030 26 26 031 53 ( 032 24 CE 033 85 + 034 01 1 035 54 ) 036 42 STO 037 27 27 038 92 RTN 039 76 Lbl # heapify 040 33 x² 041 71 SBR 042 23 lnx 043 43 RCL 044 27 27 045 32 x<>t 046 43 RCL 047 28 28 048 77 x≥t? 049 19 D' 050 43 RCL 051 28 28 052 32 x<>t 053 43 RCL 054 26 26 055 67 x=t? 056 17 B' 057 92 RTN 058 76 Lbl # swap left leaf 059 17 B' 060 43 RCL 061 26 26 062 42 STO 063 25 25 064 73 RCL Ind 065 24 24 066 32 x<>t 067 73 RCL Ind 068 25 25 069 71 SBR 070 11 A 071 92 RTN 072 76 Lbl # swap double leaf 073 19 D' 074 73 RCL Ind 075 27 27 076 32 x<>t 077 73 RCL Ind 078 26 26 079 77 x≥t? 080 10 E' 081 43 RCL 082 27 27 083 42 STO 084 25 25 085 76 Lbl 086 34 √x 087 73 RCL Ind 088 24 24 089 32 x<>t 090 73 RCL Ind 091 25 25 092 71 SBR 093 11 A 094 43 RCL 095 25 25 096 42 STO 097 24 24 098 61 GTO 099 33 x² 100 76 Lbl 101 10 E' 102 43 RCL 103 26 26 104 42 STO 105 25 25 106 61 GTO 107 34 √x 108 76 Lbl # main 109 15 E 110 42 STO 111 29 29 112 42 STO 113 28 28 114 76 Lbl # 1st heapify 115 13 C 116 22 INV 117 86 St flg 118 01 1 119 43 RCL 120 28 28 121 42 STO 122 00 00 123 01 1 124 22 INV 125 44 SUM 126 00 00 127 76 Lbl 128 18 C' 129 53 ( 130 43 RCL 131 00 00 132 85 + 133 01 1 134 54 ) 135 42 STO 136 25 25 137 53 ( 138 24 CE 139 55 ÷ 140 02 2 141 54 ) 142 42 STO 143 24 24 144 73 RCL Ind 145 24 24 146 32 x<>t 147 73 RCL Ind 148 25 25 149 71 SBR 150 11 A 151 97 Dsz 152 00 0 153 18 C' 154 87 If flg 155 01 1 156 13 C 157 71 SBR 158 32 x<>t 159 76 Lbl # heapify loop 160 35 1/x 161 01 1 162 42 STO 163 24 24 164 71 SBR 165 33 x² 166 71 SBR 167 32 x<>t 168 02 2 169 32 x<>t 170 43 RCL 171 28 28 172 77 x≥t? 173 35 1/x 174 92 RTN 175 76 Lbl # swap + reduce length 176 32 x<>t 177 01 1 178 42 STO 179 24 24 180 43 RCL 181 28 28 182 42 STO 183 25 25 184 71 SBR 185 16 A' 186 01 1 187 22 INV 188 44 SUM 189 28 28 190 92 RTN R00 # pointer R01-23 # Listenelemente R29 # Länge gesamte Liste R28 # Länge aktuelle Liste R27 # Index right leaf R26 # Index left leaf R25 # Index swap leaf R24 # Index top leaf
Die Rechenzeit ist der Mittelwert aus drei Zeitmessungen mit jeweils unterschiedlichen zufälligen Zahlen.
Der Code implementiert den Heap Sort Algorithmus, der in der Laufzeit eine Komplexität von O(n log n) zeigt. Die vorherige Implementation verhielt sich entsprechend O(n*n), war kein Heap-Sort.