我是一名工程专业的学生。我已经在 Visual2 中开发了这种有效的递归快速排序算法,但我仍然无法完成它,因为我应该在子例程末尾弹出我在同一子例程开始时存储的所有寄存器。谁能帮我? 此外,如果列表的长度是<=1. You can find the code I've developed attached
,我应该找到一种方法来提前停止子例程 ; INIZIO PROGRAMMA
MOV R0, #LIST ; Carico l'indirizzo di memoria di LEN
STR R0, [R13]
MOV R0, #LEN ; Carico l'indirizzo di memoria di LEN
LDR R0, [R0] ; Carico il valore dell'indirizzo di memoria
STR R0, [R13, #-4]!
BL QUICKSORT ; muovo il contenuto di PC in LR e salto a QUICKSORT
END
; SOTTOPROGRAMMA "QUICKSORT"
; R0 = Registro che punta alla posizione assoluta del primo elemento della lista
; R1 = Registro che indica la lunghezza della lista alla destra del pivot
; R8 = Registro che indica la lunghezza della lista alla sinistra del pivot
; R2 = Registro che serve per scorrere gli elementi della lista
; R3 = Registro che indica la posizione relativa in cui andrà inserito il pivot una volta ordinata la lista
; R4 = Registro che contiene il valore del pivot
; R5 = Registro che contiene progressivamente i valori da confrontare con il pivot
; R7 = Registro d'appoggio
QUICKSORT STR R0, [R13, #-4]!
STR R1, [R13, #-4]!
STR R8, [R13, #-4]!
STR R2, [R13, #-4]!
STR R3, [R13, #-4]!
STR R4, [R13, #-4]!
STR R5, [R13, #-4]!
STR R7, [R13, #-4]!
LDR R0, [R13, #32]
; Viene azzerato il contenuto dei registri che non vengono inizialmente sovrascritti
MOV R1, #0
MOV R2, #0
MOV R3, #0
MOV R8, #0
; Converto la lunghezza della lista come multiplo di 4
CONV ADD R1, R1, #4
SUB R0, R0, #1
CMP R0, #1
BGT CONV
LDR R0, [R13, #36]
Q_SORT STR LR, [R13, #-4]!
CMP R8, R1
BGE SORTED
MOV R7, R1
LENGTH ADD R2, R2, #4
SUB R7, R7, #4
CMP R8, R7
BLT LENGTH
ADD R3, R2, #4
LDR R4, [R0, R8]
; Ciclo sulla lista
CYCLESRT LDR R5, [R0, R2] ; Carico in R5 il valore dell'array all'indirizzo R0+[R2]
CMP R2, R8 ; Quando si è raggiunta la posizione del pivot si termina il ciclo e si passa in "SW_PIV"
BLE SW_PIV
CMP R5, R4 ; Se il valore contenuto in R5 > R4 salta in SWITCH
BGT SWITCH
ADD R2, R2, #-4 ; Si aggiorna lo spiazzamento
B CYCLESRT
; Blocco in cui si effettua lo scambio di due valori
SWITCH SUB R3, R3, #4 ; Si aggiorna la posizione del pivot al valore precedente
; Blocco in cui viene effettuato lo scambio dei due valori
LDR R7, [R0, R3] ; Si inserisce il valore che si trova all'indirizzo R0+[R3] in R7
STR R5, [R0, R3] ; Si inserisce il valore di R5 all'indirizzo R0+[R3]
STR R7, [R0, R2] ; Si inserisce il valore di R7 all'indirizzo R0+[R2]
SUB R2, R2, #4 ; Si aggiorna lo spiazzamento
B CYCLESRT
; Blocco in cui ci si entra una volta aver ordinato tutta la lista tranne che il pivot. Viene switchato il pivot con il primo elemento
; minore o uguale in modo tale che il pivot prenda la sua posizione finale all'interno dell'array.
SW_PIV SUB R3, R3, #4
LDR R7, [R0, R3]
STR R4, [R0, R3]
STR R7, [R0, R8]
STR R3, [R13, #-4]!
STR R1, [R13, #-4]!
LEFT SUB R1, R3, #4
BL Q_SORT
RIGHT LDR R1, [R13], #4
LDR R3, [R13], #4
ADD R2, R3, #4
MOV R8, R2
BL Q_SORT
SORTED LDR PC, [R13], #4
; AREA DATI
LIST DCD 4, -23, 3, 4, 12, 54
LEN DCD 6
正确的代码应该以我使用的寄存器的子例程“快速排序”中的最终弹出结束
我开发了一个可能的实现。您可以找到下面所附的代码。
; INIZIO PROGRAMMA
MOV R0, #LIST ; Carico l'indirizzo di memoria di LEN
STR R0, [R13]
MOV R0, #LEN ; Carico l'indirizzo di memoria di LEN
LDR R0, [R0] ; Carico il valore dell'indirizzo di memoria
STR R0, [R13, #-4]!
BL QUICKSORT ; muovo il contenuto di PC in LR e salto a QUICKSORT
END
; SOTTOPROGRAMMA "QUICKSORT"
; R0 = Registro che punta alla posizione assoluta del primo elemento della lista
; R1 = Registro che indica la lunghezza della lista alla destra del pivot
; R8 = Registro che indica la lunghezza della lista alla sinistra del pivot
; R2 = Registro che serve per scorrere gli elementi della lista
; R3 = Registro che indica la posizione relativa in cui andrà inserito il pivot una volta ordinata la lista
; R4 = Registro che contiene il valore del pivot
; R5 = Registro che contiene progressivamente i valori da confrontare con il pivot
; R7 = Registro d'appoggio
QUICKSORT STR LR, [R13, #-4]!
STR R0, [R13, #-4]!
STR R1, [R13, #-4]!
STR R8, [R13, #-4]!
STR R2, [R13, #-4]!
STR R3, [R13, #-4]!
STR R4, [R13, #-4]!
STR R5, [R13, #-4]!
STR R7, [R13, #-4]!
LDR R0, [R13, #36]
; Viene azzerato il contenuto dei registri che non vengono inizialmente sovrascritti
MOV R1, #0
MOV R2, #0
MOV R3, #0
MOV R8, #0
; Salto con link a CONV
BL CONV
; Ripristino dei registri dallo stack
NEEs LDR R7, [R13], #4
LDR R5, [R13], #4
LDR R4, [R13], #4
LDR R3, [R13], #4
LDR R2, [R13], #4
LDR R8, [R13], #4
LDR R1, [R13], #4
LDR R0, [R13], #4
; Uscita dall'algoritmo Quick Sort
LDR PC, [R13], #4
; Se la lunghezza della lista è inferiore o uguale ad 1 termina l'algoritmo
CONV CMP R0, #1
BLE NEEs
; Converto la lunghezza della lista come multiplo di 4
ADD R1, R1, #4
SUB R0, R0, #1
CMP R0, #1
BGT CONV
LDR R0, [R13, #40]
Q_SORT STR LR, [R13, #-4]!
CMP R8, R1
BGE SORTED
MOV R7, R1
LENGTH ADD R2, R2, #4
SUB R7, R7, #4
CMP R8, R7
BLT LENGTH
ADD R3, R2, #4
LDR R4, [R0, R8]
; Ciclo sulla lista
CYCLESRT LDR R5, [R0, R2] ; Carico in R5 il valore dell'array all'indirizzo R0+[R2]
CMP R2, R8 ; Quando si è raggiunta la posizione del pivot si termina il ciclo e si passa in "SW_PIV"
BLE SW_PIV
CMP R5, R4 ; Se il valore contenuto in R5 > R4 salta in SWITCH
BGT SWITCH
ADD R2, R2, #-4 ; Si aggiorna lo spiazzamento
B CYCLESRT
; Blocco in cui si effettua lo scambio di due valori
SWITCH SUB R3, R3, #4 ; Si aggiorna la posizione del pivot al valore precedente
; Blocco in cui viene effettuato lo scambio dei due valori
LDR R7, [R0, R3] ; Si inserisce il valore che si trova all'indirizzo R0+[R3] in R7
STR R5, [R0, R3] ; Si inserisce il valore di R5 all'indirizzo R0+[R3]
STR R7, [R0, R2] ; Si inserisce il valore di R7 all'indirizzo R0+[R2]
SUB R2, R2, #4 ; Si aggiorna lo spiazzamento
B CYCLESRT
; Blocco in cui ci si entra una volta aver ordinato tutta la lista tranne che il pivot. Viene switchato il pivot con il primo elemento
; minore o uguale in modo tale che il pivot prenda la sua posizione finale all'interno dell'array.
SW_PIV SUB R3, R3, #4
LDR R7, [R0, R3]
STR R4, [R0, R3]
STR R7, [R0, R8]
STR R3, [R13, #-4]!
STR R1, [R13, #-4]!
LEFT SUB R1, R3, #4
BL Q_SORT
RIGHT LDR R1, [R13], #4
LDR R3, [R13], #4
ADD R2, R3, #4
MOV R8, R2
BL Q_SORT
SORTED LDR PC, [R13], #4
; AREA DATI
LIST DCD -25, 21, -11, 40, -74, -73, -93, -54, 52, -28, 55, -44, 50, -33, 79, 23, -39, 44, -55, -68
LEN DCD 20