Implementazioni di algoritmi/Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Aggiunta implementazione ottimizzata in Java |
|||
Riga 300:
import java.lang.reflect.Array;
/*
private static <T> void swap(T[] array, int i, int j) {▼
* scambia gli elementi dell'array in posizione i, j
* T(n) = O(1)
*/
T aus = array[i];
array[i] = array[j];
Line 308 ⟶ 312:
}
/*
private static <T extends Comparable<T>> int insertionPos(T[] array, int from, int to, T key) {▼
* calcola la posizione in cui inserire l'elemento key nell'array da from a to
* attraverso la ricerca binaria
* T(n) = O(log(n)), n = to - from
*/
int low = from, high = to;
Line 323 ⟶ 332:
}
/*
private static <T extends Comparable<T>> int insert(T[] array, T[] aus, int from, int to, T key, int i) {▼
* inserisce una porzione di array nel vettore di supporto aus, in modo che risulti ordinato
* T(n) = O(n), n = to - from
*/
▲
int insPos = insertionPos(array, from, to, key);
int n = insPos - from;
Line 330 ⟶ 343:
}
/*
* esegue il merge delle parti del vettore in maniera ottimizzata
* T(n) = O(n), n = to - from nel caso peggiore
* T(n) = O(1) nel caso migliore
*/
@SuppressWarnings("unchecked")
if (array[mid - 1].compareTo(array[mid]) <= 0)
return;
Line 367 ⟶ 385:
if (len == 2) {
/*
* se la lunghezza della porzione da ordinare è 2, evita il merge e le chiamate ricorsive e,
* se necessario, scambia di posto gli elementi
*/
if (array[from].compareTo(array[from + 1]) > 0)
SortUtils.swap(array, from, from + 1);
Line 386 ⟶ 408:
public static <T extends Comparable<T>> void sort(T[] array) {
//caso base (lunghezza porzione = 2)
for (int i = 1; i < array.length; i += 2)
if (array[i - 1].compareTo(array[i]) > 0)
SortUtils.swap(array, i - 1, i);
//passo induttivo (esecuzione del merge)
int n;
for (n = 4; n < array.length; n *= 2) {
Line 397 ⟶ 421:
SortUtils.merge(array, i - n, mid, i);
// il merge alla fine può essere eseguito solo se ci sono 2 porzioni
if (array.length % n > half) {
int last = n * (array.length / n);
Line 404 ⟶ 429:
n /= 2;
// esegue l'ultimo merge nel caso in cui le due porzioni finali siano di lunghezza diversa
if(n < array.length)
SortUtils.merge(array, 0, n, array.length);
| |||