Fondamenti di Informatica (STI) 2005-2006
Lezioni del 2 e 9 maggio 2006
Algoritmi di ordinamento
Nel file Sorting.java sono realizzati gli algoritmi di ordinamento per selezione
(selection sort, metodo
sortUsandoSelectionSort
) e ordinamento per fusione (merge sort, metodo
sortUsandoMergeSort
).
Il metodo sortUsandoMergeSort
a sua volta usa i metodi mergeSort
e merge
La classe è stata documentata attraverso l'utilità JavaDoc. I commenti che iniziano con il doppio asterisco (/** ... */),
attraverso il comando di linea javadoc nomeDelFileDaCommentare, producono automaticamente delle pagine web di documentazione
(si veda la pagina index.html)
L'algoritmo merge sort e la sua complessità computazionale sono descritti nel testo di Cormen, Leiserson, Rivest
(si veda Materiale didattico)
Nel file QuickSort.java è realizzato l'algoritmo quick sort.
Una animazione del quick sort che usa solo una finestra di testo è disponibile in
QuickSortAnimato.java
Una interessante raccolta di applet java che mostrano il funzionamento di molti algoritmi di ordinamento, tra cui il merge sort
(Double Storage Merge Sort), il Selection Sort e il Quick Sort è
disponibile in http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
Cliccare su ciascuna immagine per avviare la demo.
Le stesse applet sono disponibili su
http://www.cs.ubc.ca/spider/harrison/Java/index.html.