* MMIX-Implementierung des Heapsort-Algorithmus * ============================================= * von Jan-Hendrik Behrmann 2012 base IS $0 * Adresse des Arrays N IS $1 * Anzahl der Elemente l IS $2 * linke Grenze des Heaps r IS $3 * rechte Grenze des Heaps i IS $4 * Position des aktuellen Knotens x IS $5 * Wert des aktuellen Knotens j IS $6 * Position des linken / größeren Kindes y IS $7 * Wert des linken / größeren Kindes k IS $8 * Position rechtes Kind z IS $9 * Wert des rechten Kindes test IS $10 * Hilfsvariable für Vergleiche swap IS $11 * Tauschvariable hsort BNP N,end * bei 0 Elementen sofort beenden % r = 8 * N - 8 SLU r,N,3 SUB r,r,8 % l = (N / 2) * 8 [!= N * 4] SRU l,N,1 SLU l,l,3 BZ l,end * l=0 => es gibt nur ein Element, sofort beenden % l > 0; beim Heap-Aufbau 1H SUB l,l,8 LDO x,base,l % Aktuellen Teilbaum setzen 3H SET j,l JMP 4F 5H LDO y,base,j * Wert des linken Kindes nach y laden BZ test,6F * j == r -> es gibt kein rechtes Kind % j < r -> dieser Knoten hat 2 Kinder % Vergleich der beiden Kinder ADD k,j,8 * k = j+1 LDO z,base,k CMP test,y,z * in y steht der Wert des linken Kindes CSNP y,test,z * y ggf. mit Wert des rechten Kindes ersetzen CSNP j,test,k * j ggf. mit Pos. des rechten Kindes ersetzen % Vergleich von Knoten und größtem Kind 6H CMP test,x,y BNN test,8F * Kind ist nicht größer, zu Ende von Heapify % y > x 7H STO y,base,i * Kind an aktuelle Position schreiben % Heapify auf aktuellen Teilbaum 4H SET i,j 2ADDU j,i,8 * j = 2 * i + 8 CMP test,j,r PBNP test,5B * j <= r -> dieser Knoten hat mindestens 1 Kind % x <= y 8H STO x,base,i * Wert x an aktuelle Position schreiben BP l,1B * wenn l > 0 zurück zum Heapaufbau % l = 0; beim Sortieren; neues X laden 2H LDO x,base,r LDO swap,base,0 STO swap,base,r SUB r,r,8 % if r > 0 -> Heapify PBP r,3B % r = 0; Sortieren fertig 9H STO x,base,0 end POP 0,0