Nadesłany przez mephisto, 21 sierpnia 2014 15:11
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
HeapSort.java:
/**
* Implementacja sortowania przez kopcowanie.
* www.algorytm.org
*
* @author mephisto
*
* @param <Key>
* typ klucza, rozszerza interfejs Comparable aby mozna go bylo
* swobodnie porownywac. Oczywiste, ze nalezaloby dodac jeszcze
* konstruktor, ktory przyjmuje Comparator, aby mozna bylo przekazac
* dowolny sposob porownywania
*/
public class HeapSort<Key extends Comparable<Key>> {
public void sort(Key[] arr) {
// tworzenie kopca
int size = arr.length;
for (int k = size / 2; k >= 1; k--) {
sink(arr, k, size);
}
// sortowanie
while (size > 1) {
// celowo zamieniamy korzen z ostatnim elementem, aby potem go
// zatopic i tym samym uzyskac najwiekszy element w indeksie 0
exchange(arr, 1, size--);
// zatapiamy korzen i przywracamy strukture kopca
sink(arr, 1, size);
}
}
/**
*
* @param arr
* @return {@code true} jesli tablica jest posortowana, w przeciwnym razie
* {@code false}
*/
public boolean isSorted(Key[] arr) {
for (int i = 1; i < arr.length; i++)
if (less(arr, i, i - 1))
return false;
return true;
}
// metoda do "zatapiania" elementu
private void sink(Key[] arr, int k, int size) {
// k jest indeksem rodzica
while (2 * k <= size) {
// indeks dziecka
int j = 2 * k;
// sprawdzamy, ktore z dzieci jest mniejsze
if (j < size && less(arr, j, j + 1))
j++;
// sprawdzamy czy dziecko jest wieksze od rodzica
if (!less(arr, k, j))
break;
// jest wieksze wiec zamieniamy
exchange(arr, k, j);
// zschodzimy poziom nizej w hierarchi kopca
k = j;
}
}
// zwraca true jesli element tablicy pod indeksem i jest mniejszy od
// elementu pod indeksem j
// celowo przeindeksowane o 1(metoda bedzie dostawac indeks wiekszy o jeden,
// wtedy latwiej obliczac dzieci w kopcu)
private boolean less(Key[] arr, int i, int j) {
return arr[i - 1].compareTo(arr[j - 1]) < 0;
}
// zamienia miejscami dwa elementy w tablicy
// celowo przeindeksowane o 1(metoda bedzie dostawac indeks wiekszy o jeden,
// wtedy latwiej obliczac dzieci w kopcu)
private void exchange(Key[] arr, int i, int j) {
Key tmp = arr[i - 1];
arr[i - 1] = arr[j - 1];
arr[j - 1] = tmp;
}
/**
* Wypisuje cala tablice.
*
* @param arr
* tablica do wypisania
*/
public void printAll(Key[] arr) {
for (Key it : arr) {
System.out.print(it + " ");
}
System.out.println();
}
// klient testowy
public static void main(String[] args) {
Integer[] arr = new Integer[] { -4, 3, 4, 4, 111, -8 };
HeapSort<Integer> instance = new HeapSort<Integer>();
System.out.println("Przed sortowaniem: ");
instance.printAll(arr);
instance.sort(arr);
System.out.println("Po sortowaniu: ");
instance.printAll(arr);
}
}

