HeapSort

Questa lezione ha come oggetto l'algoritmo di ordinamento HeapSort.

1. Leggere lo pseudocodice seguente. Si noti che il codice funziona per vettori con primo indice pari a 1 (e non 0). Riadattare il codice oppure usarlo su vettori dall'indice 1 in avanti.

   
   Parent(i)
   return  i div 2 
   
   
   Left(i)
   return 2i
   
   
   Right(i)
   return 2i+1
   
   
   Heapify(A,i)
   l = Left(i)
   r = Right(i)
   IF ((l <= heapsize(A)) and (A[l] > A[i]))
     largest = l
   ELSE
     largest = i
   ENDIF
   IF ((r <= heapsize(A)) and (A[r] >= A[largest]))
     largest = r
   ENDIF
   IF (largest != i)
     Exchange(A,i,largest)
     Heapify(A, largest)
   ENDIF
   
   
   HeapBuild(A)
   heapsize(A) = length(A) 
   FOR (i=length(A) div 2 downto 1)
     Heapify(A,i) 
   ENDFOR
   
   
   HeapSort(A)
   HeapBuild(A)
   FOR (i=length(A) downto 2)
     Exchange(A,1,i)
     heapsize(A) = heapsize(A) - 1
     Heapify(A,1)
   ENDFOR
   

2. Scrivere una classe HeapSort che ordina, in senso crescente, un vettore casuale di interi con il metodo do ordinamento HeapSort.
3. Aggiornare la classe SortWorkBench con l'algoritmo HeapSort. Fare in modo che la classe scriva le statistiche calcolate (media, deviazione, coefficiente di variazione) per i vari algoritmi di ordinamento in un documento XML. Visualizzare quindi il documento con un browser (opzionalmente, associare un foglio CSS al documento XML).