QuickSort MIPS - recursivo e iterativo

O objetivo deste trabalho ´ realizar a implementa¸ao em MIPS do algoritmo de ordena¸ao e c˜ c˜ QuickSort em sua vers˜o recursiva e iterativa. Como parte do desenvolvimento do trabalho a ser´ feita uma an´lise das implementa¸˜es, atrav´s da compara¸ao dos c´digos, analisando a a co e c˜ o o desempenho e a quantidade de instru¸˜es para cada vers˜o. co a

1

Implementa¸˜o recursiva ca Para a implementa¸ao recursiva se faz necess´rio o uso e manuten¸ao da pilha em MIPS. c˜ a c˜ Como n˜o se pode perder a referencia para os valores dos elementos passados como parˆmetro a a para as chamadas recursivas, primeiro incrementa-se o valor do registrador sp - stack point em um n´mero suficiente para guardar a quantidade de vari´veis utilizadas no programa. u a
Ap´s a utiliza¸˜o e armazenamento dos devidos registradores, as posi¸oes utilizadas na pilha o ca c˜ da recurs˜o s˜o liberadas e seu valor ´ decrementado para o valor original. a a e 1.1

Algoritmo utilizado

Para a implementa¸ao recursiva foi utilizado o algoritmo mostrado a baixo: c˜ v o i d QuickSort ( TItem ∗v , i n t n ) {
Q u i c k S o r t o r d e n a ( v , 0 , n −1) ;
}
// Ordena o v e t o r v [ e s q . . d i r ] v o i d Q u i c k S o r t o r d e n a ( TItem ∗v , i n t int i , j ;
QuickSort particao ( v , esq , d i r i f ( esq < j ) QuickSort ordena ( v i f ( i < d i r ) QuickSort ordena (v
}

esq , i n t d i r ) {
, &i , &j ) ;
, esq , j ) ;
, i , dir );

v o i d Q u i c k S o r t p a r t i c a o ( TItem ∗v , i n t e s q , i n t d i r , i n t ∗ i , int ∗ j ) {
TItem p i v o , aux ;
∗ i = esq ; ∗ j = d i r ; p i v o = v [ ( ∗ i + ∗ j ) / 2 ] ; /∗ obtem o p i v o x ∗/ do { w h i l e ( ! ( p i v o . chave