//
home

Ultimi articoli

QuickSort: algoritmo di ordinamento ricorsivo in assembler MIPS

Rappresentazione grafica dell'algoritmo di ordinamento ricorsivo QuickSort

L’algoritmo di ordinamento QuickSort è un algoritmo ricorsivo  divide et impera potenzialmente stabile  che ordina in loco un array di dimensione n eseguendo  Θ(n²) confronti worst case. L’idea di base è partizionare ricorsivamente la sequenza intorno ad un perno. Ricorsivamente, avremo da una parte una sottosequenza di elementi maggiori uguali al perno, dall’altra una sottosequenza di elementi minori. L’algoritmo di occuperà infine di fondere opportunamente gli elementi in un’unica sequenza ordinata. Basandosi sulla tecnica algoritmica divide et impera, avremo due procedure:

procedura divide: il partizionamento divide ricorsivamente una sequenza di dimensione L1+L2=n in due sottosequenze di taglia non necessariamente bilanciata di dimensione L1 ed L2 tali che, scelto un perno (cioè un elemento appartenente alla sequenza), la sottosequenza di sinistra di dimensione L1 contenga tutti gli elementi minori o uguali al perno, e la sottosequenza di destra di dimensione L2 contenga tutti gli elementi maggiori del perno. Un partizionamento attorno ad un perno in una sequenza di dimensione n richiede (n-1) confronti (infatti ogni elemento della sequenza viene confrontato con il perno una sola volta).

Il partizionamento lavora in loco: si scorre infatti l’array avanzando in parallelo da sinistra verso destra e da destra verso sinistra, mettendo gli elementi minori o uguali al perno nella parte inferiore dell’array, e quelli maggiori nella parte superiore. In ogni istante quindi, gli elementi S[i]…S[inf-1] sono minori o uguali al perno, mentre gli elementi S[sup+1]…S[f] sono maggiori del perno.

procedura impera: il merging concatena ripetutamente due sottosequenze ordinate.

Una dovuta precisazione…

La scelta del perno è sostanziale dal punto di vista prestazionale. Il criterio di selezione del perno può essere:

  • randomizzato
  • deterministico

L’algoritmo QuickSort randomizzato è più efficiente dell’algoritmo QuickSort deterministico. Tuttavia dimostrerò l’implementazione della versione deterministica, in quanto dal punto di vista della realizzazione in codice, le due versioni differiscono solo per il criterio di selezione del perno.

Codice C (download codice)

#define ARRAY_DIMENSION 10

int main(int argc, char** argv) {

int A[ARRAY_DIMENSION]={10,9,8,7,6,5,4,3,2,1};

int i;

printf(“Array before QuickSort algorithm:\n”);

print_array(A, ARRAY_DIMENSION);

quicksort(A, 0, ARRAY_DIMENSION-1);

printf(“\n\nArray after QuickSort algorithm:\n”);

print_array(A, ARRAY_DIMENSION);

}

void quicksort(int A[], int m, int n){

int key,i,j,k;

if(m<n) {

k = choose_pivot(m, n);

swap(&A[m], &A[k]);

key = A[m];

i = m+1;

j = n;

while(i <= j) {

while((i <= n) && (A[i] <= key))

i++;

while((j >= m) && (A[j] > key))

j–;

if( i < j)

swap(&A[i], &A[j]);

}

swap(&A[m], &A[j]);

quicksort(A, m, j-1);

quicksort(A, j+1, n);

}

}

int choose_pivot(int i, int j){

return((i+j)/2);

}

void swap(int *a, int *b){

int temp;

temp = *a;

*a = *b;

*b = temp;

}

void print_array(int A[], int n){

int i;

for(i=0; i<n; i++) printf(“%d\t”, A[i]);

}

Codice Assembler MIPS (download codice)

.data
msg_welcome: .asciiz “Il programma ordina gli elementi di un array di interi 10-dimensionale tramite l’algoritmo di ordinamento ricorsivo QuickSort.\n\n”
msg_before_quicksort: .asciiz “\nArray prima del QuickSort:\n”
msg_after_quicksort: .asciiz “\nArray dopo il QuickSort:\n”
RTN: .asciiz “\n”
TAB: .asciiz “\t”
A: .word 10,9,8,7,6,5,4,3,2,1
ARRAY_DIMENSION: .word 10

.text
.globl main

### MAIN ###
main:
_welcome:
la $a0,msg_welcome #carica l’indirizzo di msg_welcome.
addi $v0,$zero,4 #codice servizio print string.
syscall

_print_array_before_quicksort:
la $a0,msg_before_quicksort #carica l’indirizzo di msg_before_quicksort.
addi $v0,$zero,4 #codice servizio print string.
syscall
la $a0,A #$a0=&(A+0).
la $s0,ARRAY_DIMENSION #carica l’indirizzo di ARRAY_DIMENSION.
lw $a1,0($s0) #$a1=ARRAY_DIMENSION.
jal print_array #chiama print_array(A,ARRAY_DIMENSION).
nop

_quicksort:
la $a0,A #$a0=&(A+0).
addiu $a1,$zero,0 #$a1=m=0.
lw $a2,0($s0) #$a2=ARRAY_DIMENSION.
subu $a2,$a2,1 #$a2=(ARRAY_DIMENSION-1).
jal quicksort #chiama quicksort(A,0,ARRAY_DIMENSION-1).
nop

_print_array_after_quicksort:
la $a0,msg_after_quicksort #carica l’indirizzo di msg_after_quicksort.
addi $v0,$zero,4 #codice servizio print string.
syscall
la $a0,A #$a0=&(A+0).
lw $a1,0($s0) #$a1=ARRAY_DIMENSION.
jal print_array #chiama print_array(A,ARRAY_DIMENSION).
nop

_exit_program:
addi $v0,$zero,10 #codice servizio exit.
syscall
### FINE MAIN ###

### FUNZIONE void quicksort(int A[],int m,int n): $a0=&(A+0), $a1=m, $a2=n ###
quicksort:
subu $sp,$sp,16 #alloca uno stack frame da 16 byte per void quicksort(int A[],int m,int n): 4 byte per $ra, 4 byte per $a0=&(A+0), 4 byte per $a1=m, 4 byte per $a2=n.
sw $ra,0($sp) #carica l’indirizzo di ritorno nello stack frame.
sw $a0,4($sp) #carica &(A+0) nello stack frame.
sw $a1,8($sp) #carica m nello stack frame.
sw $a2,12($sp) #carica n nello stack frame.

slt $t0,$a1,$a2 #$t0=1 iff m<n. $t0=0 iff m=>n.
beq $t0,$zero,_m_maggiore_uguale_n #salta a m_maggiore_n sse m=>n.
nop

_m_minore_n:
addiu $a0,$a1,0 #$a0=m, argomento m per int choose_pivot(m,n).
addiu $a1,$a2,0 #$a1=n, argomento n per int choose_pivot(m,n).
jal choose_pivot #chiama choose_pivot(m,n).
nop
addiu $t3,$v0,0 #$t3=k=choose_pivot(m,n).
lw $a0,4($sp) #ripristina $a0=&(A+0).
lw $a1,8($sp) #ripristina $a1=m.

sll $t4,$a1,2 #$t4=4*m.
add $a0,$a0,$t4 #$a0=&A[m], argomento per swap(&A[m],&A[k]).
lw $t4,4($sp) #$t4=$a0=&(A+0).
sll $t5,$t3,2 #$t5=4*k.
add $a1,$t4,$t5 #$a1=&A[k], argomento per swap(&A[m],&A[k]).
jal swap #chiama swap(&A[m],&A[k]).
nop
lw $a0,4($sp) #ripristina $a0=&(A+0).
lw $a1,8($sp) #ripristina $a1=m.

sll $t4,$a1,2 #$t4=4*m.
add $t4,$a0,$t4 #$t4=&A[m].
lw $t5,0($t4) #$t5=key=A[m].

addiu $t1,$a1,1 #i=(m+1).
addiu $t2,$a2,0 #j=n.

_cicle_while_1:
slt $t0,$t2,$t1 #$t0=1 iff j<i. $t0=0 iff j=>i.
bne $t0,$zero,_end_cicle_while_1 #salta alla fine del ciclo sse j<i.
nop

_cicle_while_2:
slt $t0,$a2,$t1 #$t0=1 iff n<i. $t0=0 iff n=>i.
bne $t0,$zero,_end_cicle_while_2 #salta alla fine del ciclo sse n<i.
nop

sll $t6,$t1,2 #$t6=4*i.
add $t6,$a0,$t6 #$t6=&A[i].
lw $s1,0($t6) #$s1=A[i].

slt $t0,$t5,$s1 #$t0=1 iff key<A[i]. $t0=0 iff key=>A[i].
bne $t0,$zero,_end_cicle_while_2 #salta alla fine del ciclo sse key<A[i].
nop

addiu $t1,$t1,1 #i++.
j _cicle_while_2 #salta al ciclo while 2.
nop

_end_cicle_while_2:
nop

_cicle_while_3:
slt $t0,$t2,$a1 #$t0=1 iff j<m. $t0=0 iff j=>m.
bne $t0,$zero,_end_cicle_while_3 #salta alla fine del ciclo sse j<m.
nop

sll $t7,$t2,2 #$t7=4*j.
add $t7,$a0,$t7 #$t7=&A[j].
lw $s2,0($t7) #$s2=A[j].

slt $t0,$t5,$s2 #$t0=1 iff key<A[j]. $t0=0 iff key=>A[j].
beq $t0,$zero,_end_cicle_while_3 #salta alla fine del ciclo sse key=>A[j].
nop

subu $t2,$t2,1 #j–.
j _cicle_while_3 #salta a ciclo while 3.
nop

_end_cicle_while_3:
nop

_if:
slt $t0,$t1,$t2 #$t0=1 iff i<j. $t0=0 iff i=>j.
beq $t0,$zero,_end_if #salta alla fine dell’if sse i=>j.
nop

sll $t6,$t1,2 #$t6=4*i.
add $a0,$a0,$t6 #$a0=&A[i], argomento per swap(&A[i],&A[j]).
lw $t4,4($sp) #$t4=$a0=&(A+0).
sll $t7,$t2,2 #$t7=4*j.
add $a1,$t4,$t7 #$a1=&A[j], argomento per swap(&A[i],&A[j]).
jal swap #chiama swap(&A[m],&A[k]).
nop

lw $a0,4($sp) #ripritsina $a0=&(A+0).
lw $a1,8($sp) #ripristina $a1=m.

_end_if:
j _cicle_while_1 #salta al ciclo while 1.
nop

_end_cicle_while_1:
nop

sll $t4,$a1,2 #$t4=4*m.
add $a0,$a0,$t4 #$a0=&A[m], argomento per swap(&A[m],&A[j]).
lw $t4,4($sp) #$t4=$a0=&(A+0).
sll $t5,$t2,2 #$t5=4*j.
add $a1,$t4,$t5 #$a1=&A[j], argomento per swap(&A[m],&A[j]).
jal swap #chiama swap(&A[m],&A[j]).
nop

lw $a0,4($sp) #ripritsina $a0=&(A+0), argomento per quicksort(A,m,j-1).
lw $a1,8($sp) #ripristina $a1=m, argomento per quicksort(A,m,j-1).
subu $a2,$t2,1 #$a2=j-1, argomento per quicksort(A,m,j-1).

subu $sp,$sp,4 #alloca uno stack frame per conservare il valore di $t2=j durante le chiamate ricorsive.
sw $t2,0($sp) #carica $t2=j nello stack frame.

jal quicksort #chiama quicksort(A,m,j-1).
nop

lw $t2,0($sp) #ripristina $t2=j.
addiu $sp,$sp,4 #dealloca lo stack frame utilizzato per conservare il valore di $t2=j durante le chiamate ricorsive.

lw $a0,4($sp) #carica $a0=&(A+0), argomento per quicksort(A,j+1,n).
addiu $a1,$t2,1 #$a1=j+1, argomento per quicksort(A,j+1,n).
lw $a2,12($sp) #carica $a2=n, argomento per quicksort(A,j+1,n).

subu $sp,$sp,4 #alloca uno stack frame per conservare il valore di $t2=j durante le chiamate ricorsive.
sw $t2,0($sp) #carica $t2=j nello stack frame.

jal quicksort #chiama quicksort(A,j+1,n).
nop

lw $t2,0($sp) #ripristina $t2=j.
addiu $sp,$sp,4 #dealloca lo stack frame utilizzato per conservare il valore di $t2=j durante le chiamate ricorsive.

_m_maggiore_uguale_n:
lw $ra,0($sp) #carica l’indirizzo di ritorno.
addiu $sp,$sp,16 #dealloca lo stack frame da 16 byte per void quicksort(int n, int *A, int m).
jr $ra #torna al chiamante.
### FINE FUNZIONE quicksort(int n, int *A, int m) ###

### FUNZIONE void swap(int *x, int *y): $a0=&x, $a1=&y ###
swap:
subu $sp,$sp,16 #alloca uno stack frame da 16 byte per void swap(int *x, int *y): 4 byte per $ra, 4 byte per $a0=&x, 4 byte per &y, 4 byte per *x.
sw $ra,0($sp) #carica l’indirizzo di ritorno nello stack frame.
sw $a0,4($sp) #carica &x nello stack frame.
sw $a1,8($sp) #carica &y nello stack frame.

lw $t0,0($a0) #$t0=*x.
sw $t0,12($sp) #carica *x nello stack frame.

lw $t0,0($a1) #$t0=*y.
sw $t0,0($a0) #*x=*y.

lw $t0,12($sp) #carica *x.
sw $t0,0($a1) #*y=*x

lw $ra,0($sp) #carica l’indirizzo di ritorno.
addiu $sp,$sp,16 #dealloca lo stack frame per void swap(int *x, int *y).
jr $ra #torna al chiamante.
### FINE FUNZIONE void swap(int *x, int *y) ###

### FUNZIONE int choose_pivot(int i, int j): $a0=i, $a1=j, $v0=choose_pivot(i,j) ###
choose_pivot:
subu $sp,$sp,12 #alloca uno stack frame da 12 byte per int choose_pivot(int i, int j): 4 byte per $ra, 4 byte per $a0=i, 4 byte per $a1=j.
sw $ra,0($sp) #carica l’indirizzo di ritorno nello stack frame.
sw $a0,4($sp) #carica i nello stack frame.
sw $a1,8($sp) #carica j nello stack frame.

add $v0,$a0,$a1 #$v0=(i+j).
srl $v0,$v0,1 #$v0=(i+j)/2.

lw $ra,0($sp) #carica l’indirizzo di ritorno.
addiu $sp,$sp,12 #dealloca lo stack frame per int choose_pivot(int i, int j).
jr $ra #torna al chiamante.
### FINE FUNZIONE choose_pivot(int i, int j) ###

### FUNZIONE void print_array(int A[],int n): $a0=&(A+0), $a1=n ###
print_array:
subu $sp,$sp,12 #alloca uno stack frame da 12 byte per void print_array(int A[],int n): 4 byte per $ra, 4 byte per $a0=&(A+0), 4 byte per $a1=n.
sw $ra,0($sp) #carica l’indirizzo di ritorno nello stack frame.
sw $a0,4($sp) #carica &(A+0) nello stack frame.
sw $a1,8($sp) #carica n nello stack frame.

addiu $t1,$zero,0 #$t1=i=0.
addiu $t2,$a0,0 #$t2=$a0=&(A+0).
addiu $t3,$a1,0 #$t3=$a1=n.

_cicle_for:
slt $t0,$t1,$t3 #$t0=1 iff i<n. $t2=0 iff i=>n.
beq $t0,$zero,_end_cicle_for #salta alla fine del ciclo for sse i=>n.

sll $t4,$t1,2 #$t4=4*i.
add $t5,$t2,$t4 #$t5=&(A+i).

lw $a0,0($t5) #$a0=*(A+i).
addiu $v0,$zero,1 #codice servizio print int.
syscall

la $a0,TAB #carica l’indirizzo della stringa TAB.
addiu $v0,$zero,4 #codice servizio print string.
syscall

addiu $t1,$t1,1 #i++
j _cicle_for

_end_cicle_for:
la $a0,RTN #carica l’indirizzo della stringa RTN.
addiu $v0,$zero,4 #codice servizio print string.
syscall

lw $ra,0($sp) #carica l’indirizzo di ritorno.
addiu $sp,$sp,12 #dealloca lo stack frame per void print_array(int A[],int n).
jr $ra #torna al chiamante.
### FINE FUNZIONE void print_array(int A[],int n) ###

Updates

Top Rated

@giacomomarciani

Stats

  • 25,688 visite