Implementazioni di algoritmi/Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Aggiunta implementazione ottimizzata in Java |
|||
Riga 293:
}
</source>
=== Java (Ottimizzazione) ===
==== Metodi di supporto ====
<syntaxhighlight lang="java">
import java.lang.reflect.Array;
public class SortUtils {
private static <T> void swap(T[] array, int i, int j) {
T aus = array[i];
array[i] = array[j];
array[j] = aus;
}
private static <T extends Comparable<T>> int insertionPos(T[] array, int from, int to, T key) {
int low = from, high = to;
while (low < high) {
int mid = (low + high) / 2;
if (array[mid].compareTo(key) > 0)
high = mid;
else
low = mid + 1;
}
return low;
}
private static <T extends Comparable<T>> int insert(T[] array, T[] aus, int from, int to, T key, int i) {
int insPos = insertionPos(array, from, to, key);
int n = insPos - from;
System.arraycopy(array, from, aus, i, n);
return n;
}
@SuppressWarnings("unchecked")
private static <T extends Comparable<T>> void merge(T[] array, int from, int mid, int to) {
if (array[mid - 1].compareTo(array[mid]) <= 0)
return;
int start = insertionPos(array, from, mid, array[mid]);
T[] aus = (T[]) Array.newInstance(array.getClass().getComponentType(), to - start);
int i = 0, posLeft = start, posRight = mid;
while (posLeft < mid && posRight < to) {
int n = insert(array, aus, posRight, to, array[posLeft], i);
i += n;
posRight += n;
if (posRight < to) {
n = insert(array, aus, posLeft, mid, array[posRight], i);
i += n;
posLeft += n;
}
}
if (posLeft < mid)
System.arraycopy(array, posLeft, array, start + i, mid - posLeft);
System.arraycopy(aus, 0, array, start, i);
}
}
</syntaxhighlight>
==== Versione ricorsiva ====
<syntaxhighlight lang="java">
public class RecursiveMergeSort {
public static <T extends Comparable<T>> void sort(T[] array, int from, int to) {
int len = to - from;
if (len == 2) {
if (array[from].compareTo(array[from + 1]) > 0)
SortUtils.swap(array, from, from + 1);
} else if (len > 2) {
int mid = from + len / 2;
sort(array, from, mid);
sort(array, mid, to);
SortUtils.merge(array, from, mid, to);
}
}
}
</syntaxhighlight>
==== Versione iterativa ====
<syntaxhighlight lang="java">
public class IterativeMergeSort {
public static <T extends Comparable<T>> void sort(T[] array) {
for (int i = 1; i < array.length; i += 2)
if (array[i - 1].compareTo(array[i]) > 0)
SortUtils.swap(array, i - 1, i);
int n;
for (n = 4; n < array.length; n *= 2) {
int half = n / 2;
for (int i = n, mid = half; i <= array.length; i += n, mid += n)
SortUtils.merge(array, i - n, mid, i);
if (array.length % n > half) {
int last = n * (array.length / n);
SortUtils.merge(array, last, last + half, array.length);
}
}
n /= 2;
if(n < array.length)
SortUtils.merge(array, 0, n, array.length);
}
}
</syntaxhighlight>
===[[w:Python|Python]]===
| |||