Koniec wakacyjnej przerwy! Ten artykuł miał zostać opublikowany ponad tydzień temu – ale wiecie jak to jest z wakacjami 😉 czasem po prostu trzeb a zluzować troszkę! Ale wracam z naładowanymi bateriami! Dziś zajmiemy się implementacją QuickSortu!
01. QuickSort - Użycie wbudowanej implementacji / Bibloteki
Pod poprzednim artykułem, czytelnik zadał pytanie czy istnieje już biblioteka która posiad implementację quicksortu? – jak się można spodziewać, odpowiedź na to pytanie brzmi – oczywiście 😊 żeby było lepiej, implementacja QuickSortu znajduje się w samej Javie! 😊 (od wersji 1.2)
import java.util.Arrays; ... Arrays.sort(array);
I w zasadzie to wystarczy 😊
02. QuickSort- Własna implementacja
Nasza własna implementacja nie jest najbardziej optymalną wersją – jest wersją przedstawionej wcześniej teorii. Opisana implementacja pokrywa się w 100% z opisaną teorią z poprzedniego wpisu, dzięki czemu można porównać co się dokładnie dzieje.
Po pierwsze mamy jeden punkt wejściowy do którego przesyłamy naszą nieposortowaną tablicę:
public static void sort(int[] array) { quickSort(array, 0, array.length-1); }
W ciele metody robimy odesłanie do naszej głównej metody quickSort:
private static void quickSort(int[] array, int firstIndex, int lastIndex) { if(firstIndex < lastIndex) { int partitionIndex = partition(array, firstIndex, lastIndex); quickSort(array, firstIndex, partitionIndex-1); quickSort(array, partitionIndex+1, lastIndex); } }
Pierwszym krokiem jest sprawdzenie na jakich pozycjach są ustawione indexy, index początkowy musi być mniejszy od ostatniego indexu – w przeciwnym wypadku nie podejmujemy żadnych działań.
Główną metodą jest metoda partition która dokonuje sortowania przesłanej tablicy względem pivotu, oraz zwraca również index podziału – dzięki czemu mamy podział na lewą i prawą część tablicy.
Jak możesz zauważyć metoda quickSort, jest metodą rekurencyjną (wywołuje sama siebie), pokrywa się to z sortowaniem lewej oraz prawej części tablicy 😊
Metoda partition wygląda następująco:
private static int partition(int[] array, int firstIndex, int lastIndex) { int pivot = array[lastIndex]; int pIndex = firstIndex; for (int i = firstIndex; i < lastIndex; i++) { if(array[i] <= pivot) { swap(array, i ,pIndex); pIndex++; } } swap(array, pIndex, lastIndex); return pIndex; }
Jest to metoda która sortuje względem wybranego pivotu, oraz zwraca index podziału. Metoda swap jest metodą pomocniczą która zamienia dwa wskazane elementy:
private static void swap(int[] array, int index1, int index2) { int tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; }
Podsumowanie
Metody sortowania mogą być kłopotliwe do zrozumienia, pamiętaj że cały kod dostępny jest na GitHubie! Ściągnij kod – poeksperymentuj z nim, pomoże Ci to w zrozumieniu tego co się dzieje!