Algorytmy sortowania
Poniższe zestawienie obejmuje najpopularniejsze i najbardziej znane algorytmy. Oczywiście istnieje ich dużo więcej, można także ‚mieszać’ różne podejścia w zależności od potrzeb, ale poniższe są pewnym kanonem wiedzy, który warto znać.
Sortowanie bąbelkowe (Bubble sort)
Nazwa pochodzi od obrazowego przedstawienia zasady działania – w każdym ‚przebiegu’ kolejna wartość w kolejności ‚wypływa’ jak bąbelek powietrza na powierzchnie wody.
W algorytmie tym w celu posortowania n elementów wykonujemy n-1 przebiegów. W każdym przebiegu zaczynamy od początku zbioru, bierzemy dwa elementy i zamieniamy je miejscami tak, aby większy był ‚wyżej’ (lub z większym indeksem itp). W pierwszym kroku robimy to dla elementów 1 i 2, w drugim kroku dla 2 i 3 itd. Każdy przebieg ‚wyciąga’ do góry kolejny element w kolejności, po wykonaniu wszystkich przebiegów nasz zbiór jest posortowany.
Algorytm ten jest najmniej optymalny z tych podstawowych i bardzo nieefektywny obliczeniowo – złożoność to O(n^2). Ma on jednak złożoność pamięciową O(1) (oznacza to, że poza miejscem potrzebnym do przechowywania sortowanego zbioru, nie wymaga dodatkowej pamięci).
Zaletą jest trywialna implementacja i przewidywalna ilość operacji, identyczna dla przypadku optymistycznego jak i pesymistycznego.
Przykładowy kod:
public void bubbleSort(int[] kolekcja) {
for (int i = 0; i<kolekcja.length; i++) {
for (int j = 1; j<kolekcja.length; j++) {
if (kolekcja[j]<kolekcja[j-1]) {
int wieksza = kolekcja[j-1];
kolekcja[j-1] = kolekcja[j];
kolekcja[j] = wieksza;
}
}
}
}
Możliwe jest wprowadzenie optymalizacji, które nie zmieniają złożoności, ale przyspieszają działanie algorytmu w każdym przypadku:
- w i’tym przebiegu można go zakończyć po n-i krokach, ponieważ pozostałe elementy są już posortowane; skróci to czas działania algorytmu o połowę.
Sortowanie szybkie (Quicksort)
Algorytm ten jest najpopularniejszy, jeśli chodzi o ilość zastosowań, ponieważ w ogólnym i uśrednionym przypadku jest on najbardziej optymalny, a jednocześnie prosty w implementacji. Jego wadą jest negatywny przypadek, kiedy to złożoność wynosi n^2 .
Algorytm jest rekursywny, tj. odwołuje się do samego siebie i jest przykładem podejścia dziel i zwyciężaj (divide and conquer). W każdym kroku ze zbioru elementów wybieramy dowolny element (nazywany pivot; może to być po prostu pierwszy z brzegu lub losowy, dla nieuporządkowanych danych nie ma to znaczenia) a następnie dzielimy pozostałe elementy na dwie grupy – te mniejsze od wybranego elementu (‚przed nim’) oraz większe od niego (‚za nim’). Każdą z tych grup sortujemy w ten sam sposób.
Algorytm ten jest stosunkowo prosty w implementacji, a jego wydajność jest zdecydowanie wystarczająca w ogólnym przypadku. Uśredniona złożoność obliczeniowa to O(n*log n), pamięciowa O(log n), ale w najgorszym przypadku złożoność obliczeniowa może wynieść O(n^2) – jest to zależne zarówno od danych wejściowych jak i sposobu doboru punktu pivot.
Przykładowa implementacja (nieoptymalna, możliwe jest wykorzystanie tylko jednej struktury, tutaj tworzymy nowe dla zwiększenia czytelności):
public List quicksort(List kolekcja) {
if (kolekcja.size()<=1) {return kolekcja;}
List wynik = new ArrayList();
List mniejsze = new ArrayList();
List wieksze = new ArrayList();
Integer pivot = kolekcja.remove(kolekcja.length/2);
for (Integer obiekt : kolekcja) {
if (obiekt<pivot) {
mniejsze.add(obiekt);
} else {
wieksze.add(obiekt);
}
}
mniejsze = quicksort(mniejsze);
wieksze = quicksort(wieksze);
wynik.addAll(mniejsze);
wynik.add(pivot);
wynik.addAll(wieksze);
}
Możliwa jest optymalizacja w niektórych przypadkach, np. sprawdzając warunki wstępne lub zamieniając sortowanie zbiorów o określonym rozmiarze na np. sortowanie kubełkowe, ale nie powodują one przyspieszenia w każdym przypadku.
Sortowanie przez zliczanie (bucket sort; czasem nazywane także sortowaniem kubełkowym)
Ten rodzaj sortowania jest najszybszy obliczeniowo, ale ma bardzo dużą złożoność pamięciową rzędu O(m), gdzie m to ilość możliwych wartości, bliższe optymalnego jest O(n), gdzie n to liczba różnych wartości wejścia. W wersji ‚ortodoksyjnej’ polega na stworzeniu mapy pomiędzy możliwymi wartościami, a ilością ich wystąpień w zbiorze, po czym odtworzeniu zbioru na tej podstawie.
Ponieważ takie podejście jest możliwe właściwie tylko dla liczb i to w określonym zakresie, często stosowane jest połączenie tego podejścia oraz innego algorytmu – sortowanie przez zliczanie służy do pogrupowania wstępnego, a następnie w każdej grupie korzystając z innego algorytmu wykonujemy właściwe sortowane. Przykładem może być sortowanie ciągów znaków – grupujemy je najpierw wg pierwszej litery w 26 grup i każdą z nich sortujemy osobno, następnie scalając wyniki.
Przykładowa implementacja (wersja ‚dosłowna’ – z odtwarzaniem wartości; założenie: wejście to tylko liczby z zakresu 0-ZAKRES_WARTOSCI_MAX):
public int[] przezZliczanie(int[] kolekcja) {
int[] zliczenia = new int[ZAKRES_WARTOSCI_MAX];
for (int obiekt : kolekcja) {
zliczenia[obiekt]++;
}
int wynik = new int[kolekcja.length];
for (int i=0, j=0; i<ZAKRES_WARTOSCI_MAX; i++) {
while (zliczenia[i]>0) {
wynik[j] = i;
j++;
}
}
return wynik;
}
Algorytm ten koncepcyjnie jest podobny do hashowania (więcej znajdziesz w materiale kontrakt hashCode equals), ale wymaga możliwości rekonstrukcji obiektu na podstawie wartości hash (co w praktycznych zastosowaniach jest mało użyteczne).
Sortowanie przez scalanie (Merge sort)
Jest to kolejny przykład podejścia dziel i rządź – w tym wypadku polega on na podziale zbioru na n równych podzbiorów (najczęściej jednoelementowych) a następnie scalaniu ich ze sobą uzyskując większe, posortowane podzbiory. Najprostsza implementacja jest rekurencyjna, ale nie wynika to bezpośrednio z samego algorytmu – scalanie może się odbywać iteracyjnie, dołączając kolejne podzbiory do jednego ‚posortowanego’. Dużą zaletą tego algorytmu jest możliwość zrównoleglenia – operacje sortowania można wykonywać na kilku wątkach lub nawet na wielu różnych maszynach w tym samym czasie.
Przykładowa implementacja (ponownie, nie jest to implementacja optymalna, ale zgodna z definicją i obrazująca koncepcje).
public int[] scalDwie(int[] pierwsza, int[] druga) {
int[] wynik = new int[pierwsza.length + druga.length];
int indeksWynik = 0;
int indeksPierwszy = 0, indeksDrugi = 0;
while (indeksPierwszyif ((indeksPierwszyelse {
wynik[indeksWynik] = druga[indeksDrugi];
indeksDrugi++;
}
indeksWynik++;
}
return wynik;
}
public int[] sortowaniePrzezScalanie(int[] kolekcja) {
int podzial = kolekcja.length/2;
int[] prawa = sortowaniePrzezScalanie(Arrays.copyOfRange(kolekcja, 0, podzial));
int[] lewa = sortowaniePrzezScalanie(Arrays.copyOfRange(kolekcja, podzial, kolekcja.length));
return scalDwie(prawa, lewa);
}
Sortowanie kopcowe (heap sort; funkcjonuje także nazwa sortowanie przez kopcowanie)
Sortowanie przez kopcowanie (częściej spotykaną nazwą, także w polskiej literaturze, jest heap sort) to kolejny z algorytmów mający praktyczne zastosowanie – jego wydajność jest najczęściej minimalnie mniejsza niż QuickSort, ale wydajność pesymistyczna jest zdecydowanie lepsza. Polega on na budowaniu kopca – czyli struktury, w której elementy są posortowane w określonym porządku – a następnie iteracyjnym dodawaniu kolejnych elementów zbioru. Po każdym dodaniu konieczne jest przywrócenie właściwości kopca, tzn. uporządkowanie elementów.
Kopiec jest strukturą podobną do drzewa – pod kątem złożoności wstawienie jednego elementu wymaga maksymalnie log(n) operacji. Dlatego złożoność w pesymistycznym przypadku wynosi tyle samo, co w ogólnym przypadku i jest równa nlog n. Z punktu widzenia tego algorytmu nie ma pesymistycznych przypadków, nie ma też optymistycznych przypadków – jego złożoność jest przewidywalna co czyni go preferowanym w niektórych zastosowaniach, szczególnie przy obliczeniach czasu rzeczywistego (np. w sterowaniu procesami produkcyjnymi, systemach krytycznych takich jak podsystemy w samolotach itp). Algorytm ten ma złożoność pamięciową O(1), obliczeniową O(n log n).
Poniższy przykład wykorzystuje tablicę do reprezentacji kopca.
public void sort(int arr[])
{
buildHeap(arr);
for (int i = arr.length-1; i > 0; i--)
{
swap(arr, 0, i);
buildMaxHeap(arr, 0, i-1);
}
}
public static void buildHeap(int arr[])
{
for (int i = (arr.length-1)/2; i >= 0; i--)
buildMaxHeap(arr, i, arr.length-1);
}
public static void buildMaxHeap(int arr[], int i, int N)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i)
{
swap(arr, i, max);
buildMaxHeap(arr, max, N);
}
}
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}