HomeWork5 < Architetture2/MZ/AA15

Tags: view all tags

---+++ Homework 5 - ordinamento con Heapsort

__Questo homework di recupero è riservato a chi non ha svolto tutti i 4 homework precedenti__

   1 Realizzate la funzione ricorsiva *heapsort* che riceve come argomenti:
      * l'indirizzo di un vettore contenente interi a partire dall'indice 1
      * il numero di elementi *N&lt;1000* del vettore
   1 La funzione ordina il vettore in ordine _crescente_ (distruttivamente) usando l'algoritmo *[[http://en.wikipedia.org/wiki/Heapsort][Heapsort]]*
      * per semplificare i conti delle posizione dei figli usate uno heap che ha la radice all'indice *1* del vettore
      * per il passo iniziale di trasformazione del vettore in uno heap usate *[[https://en.wikipedia.org/wiki/Heapsort#Example][il meccanismo visualizzato dall'esempio della pagina Heapsort]]*
         * partite dallo heap vuoto
         * inserite uno per volta gli elementi del vettore disordinato nello heap nel prossimo elemento libero (una foglia)
         * fate risalire il valore nello heap (scambiandolo col padre) se ha valore maggiore del nodo padre
      * nella seconda fase di ordinamento:
         * per ogni scambio della radice con l'ultimo nodo della parte heap fate calare la radice al suo posto scambiandola con il figlio maggiore
   1 *Modificate la funzione che porta un nodo dalla radice alla sua posizione finale in modo che ad ogni inserimento di un valore nello heap stampi su una riga il valore e la posizione* in cui esso va a finire separati da spazio, e poi un accapo (questo avviene nel caso base quando il nodo non ha più figli con cui può essere scambiato)
      * __NOTA__ il valore e la posizione vanno stampate anche se il nodo non si deve muovere e resta nella radice
   1 Realizzate il *main* del programma che
      * legge il valore *N*
      * legge gli N valori e li inserisce nel vettore (senza ordinarli e senza creare lo heap)
      * chiama la funzione *heapsort* che ordina il vettore
      * stampa su linee separate tutti gli elementi del vettore ordinato

---+++ Esempio di input (lo stesso di Wikipedia) commentato (la parte dopo i # ignoratela)
Se l'input è il vettore *66, 55, 33, 11, 88, 77, 22, 44*
<verbatim>
8           # numero di elementi
66          # elemento in posizione 1
55          #
33
11
88
77
22
44          # elemento in posizione 8
</verbatim>

---+++ Output atteso e commentato (la parte dopo i # ignoratela)

Dopo aver trasformato il vettore in uno heap come nell' [[https://en.wikipedia.org/wiki/Heapsort#Example][esempio]] abbiamo
   * 88, 66, 77, 44, 55, 33, 22, 11
e quindi mano a mano che si scambia l'ultimo elemento col primo e lo si fa scendere al suo posto vengono stampate le coppie &lt;valore posizione&gt;
<verbatim>
              # si scambia 88 con 11
11 6          # il valore 11 va a finire all'indice 6
              # si scambia 77 con 22
22 5          # il valore 22 va a finire all'indice 5
              # si scambia 66 con 11
11 4          # il valore 11 va a finire all'indice 4
              # si scambia 55 con 22
22 2          # il valore 22 va a finire all'indice 2
              # si scambia 44 con 11
11 3          # il valore 11 va a finire all'indice 3
              # si scambia 33 con 11
11 2          # il valore 11 va a finire all'indice 2
              # si scambia 22 con 11
11 1          # il valore 11 resta all'indice 1
# seguiti dai valori ordinati del vettore
11
22
33
44
55
66
77
88
</verbatim>


---++++ Da consegnare entro il 5 giugno 2016 ore 24

Per consegnare il programma:
   * dovete essere [[TWiki.TWikiRegistration][iscritti a twiki]]
   * usare la [[/~andrea/consegna-HW-2016.html][pagina di consegna]] 
   * Non copiate o il compito verrà annullato ad entrambi
   * Scadenza della consegna: *domenica 5 maggio ore 24*

__ATTENZIONE__ entrambe le funzioni per trasformare il vettore in uno heap e per ordinarlo devono essere ricorsive 

*anche questo homework vale 1 punto*

L'esempio è disponibile anche come file sulla [[%ATTACHURL%][pagina dei test]], per usarlo usate la linea di comando
   * __java -jar Mars_4.5.jar me nc sm ic file.asm &lt; es1.in &gt; es1.out__
   * per controllare che l'output sia uguale potete usare il comando *diff*

-- Users.AndreaSterbini - 19 May 2016

<!--
   * Set ALLOWTOPICCHANGE = Users.AndreaSterbini
-->