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<1000 del vettore
2. La funzione ordina il vettore in ordine crescente (distruttivamente) usando l'algoritmo 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 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
3. 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
4. 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)

8           # numero di elementi
66          # elemento in posizione 1
55          #
33
11
88
77
22
44          # elemento in posizione 8

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

Dopo aver trasformato il vettore in uno heap come nell' esempio abbiamo

• 88, 66, 77, 44, 55, 33, 22, 11

              # 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

Da consegnare entro il 5 giugno 2016 ore 24

Per consegnare il programma:

• dovete essere iscritti a twiki
• usare la 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 pagina dei test, per usarlo usate la linea di comando

• java -jar Mars_4.5.jar me nc sm ic file.asm < es1.in > es1.out
• per controllare che l'output sia uguale potete usare il comando diff

-- AndreaSterbini - 19 May 2016