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!

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 😊

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;
}

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!