Algorytmy #3: sortowanie – przykłady

Podstawy

Zagadnienie algorytmów sortowania to jedno z najczęściej zadawanych pytań na rozmowach kwalifikacyjnych. W praktyce rzadko przyda Ci się ta umiejętność, bowiem wszystkie sensowne algorytmy sortowania zostały już dawno opracowane i zaimplementowane. Java także (domyślnie) używa jednego z nich, chodź pozostawia też możliwość implementacji swojego algorytmu sortowania.* Czasami jednak może się okazać, że zajdzie potrzeba napisać proste sortowanie dla potrzeb przetestowania jakieś funkcjonalności. Stąd też poza omówieniem pokrótce jakie najpopularniejsze algorytmy sortowania wyróżnia się w programowaniu, postaram się też wytłumaczyć, na czym polegają dwa najpopularniejsze z nich: bubblesort i quicksort.

Rodzaje algorytmów sortowania

Zanim jednak przejdę do opisu ich implementacji, możesz przejrzeć poniżej krótkie opisy kilku ciekawych algorytmów sortowania.

• Sortowanie przez wstawianie (ang. insertsort)
• Sortowanie bąbelkowe (ang. bubblesort)
• Sortowanie szybkie (ang. quicksort)
• Sortowanie przez kopcowanie (ang. heapsort)
• Sortowanie przez scalanie (ang. mergesort)

Sortowanie bąbelkowe

Spójrz teraz na moją implementację sortowania bąbelkowego:

package algorithms.sorting;

public class BubbleSort {

  public static void main(String args[]) {
    int sampleArray[] = { 14, -36, 32, 11, 89, 11, 91 };
    sort(sampleArray);
  }

  private static void sort(int array[]) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
      System.out.print("Iteration nr: " + i);
      printArray(array);
      for (int j = 0; j < n - i - 1; j++) {
        if (array[j] > array[j + 1]) {
          swapArray(array, j);
        }
      }
    }
  }

  private static void swapArray(int[] array, int j) {
    int temp = array[j];
    array[j] = array[j + 1];
    array[j + 1] = temp;
  }

  private static void printArray(int array[]) {
    System.out.print(": ");
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + ", ");
    }
  }

}

Powyższy algorytm wpierw wczytuje ciąg znaków z tablicy. Jeśli wszystko udało się zaczytać, powinien wpierw dokonać zamiany każdego elementu ze swoim sąsiadem (np. -36 < 14, więc powinno zostać zamienione). Program wykonuje operacje zamiany na wszystkich elementach, zaczynając od pierwszego. Później dokonuje tego samego, ale już rozpoczynając jeden indeks wyżej. Sama zamiana wartości sąsiednich odbywa się w metodzie swapArray. Dodatkowo wypisuję informację o aktualnym stanie elementów w tablicy. Procedura sortowania w tym przypadku nie jest bardzo skomplikowana i przypomina bardzo w jaki sposób ludzie liczą w pamięci.

„Szybkie” sortowanie

Przejdę teraz do omówienia quicksorta (czyli sortowania tzw. szybkiego).

public class QuickSort {
  private static int iterationNumber = 0;

  public static void main(String[] args) {
    int[] sampleArray = { 5, -10, 5, 12, 10, 7, 8};
    sort(sampleArray, 0, sampleArray.length -1);
  }

  private static void sort(int[] array, int left, int right) {
    System.out.print("\nIteration nr: " + iterationNumber++);
    printArray(array);
    int i = left; 
    int j = right;

    int pivot = array[left + (right - left) / 2];

    while (i <= j) {
      while (array[i] < pivot) {
        i++;
      }

      while (array[j] > pivot) {
        j--;
      }

      if (i <= j) {
        swapArray(array, i, j);
        i++;
        j--;
      }
    }

    if (left < j) {
      sort(array, left, j);
    }
      
    if (i < right) {
      sort(array, i, right);
    }     
  }
  
  private static void swapArray(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }


  private static void printArray(int array[]) {
    System.out.print(": ");
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + ", ");
    }
  }
}

„Dziel i rządź” wiecznie żywe

Algorytm ten jest ciekawą realizacją zasady „dziel i rządź”. Program wykonuje podobną dekompozycję w celu uzyskania prostszej (mniejszej) porcji danych do właściwego już sortowania. Ponieważ algorytm ten jest z rodzaju rekurencyjnych, potrzebnymi parametrami funkcji będą dwa indeksy (jeden dla lewej części, drugi dla prawej) oraz tablica do sortowania. Następnie obliczany jest pivot, czyli element znajdujący się 'na środku’ tablicy, wedle którego będzie ona dzielona. Później w pętli 'while’ tablica główna dzielona jest na dwie mniejsze. Jeśli znaleziona wartość w lewej tablicy, jest większa niż pivot i jeśli znaleziona wartość w prawej tablicy, jest mniejsza od pivota, wtedy wartości są zamieniane. Na końcu wywoływana jest rekurencja na obu częściach tablicy.

Obydwa algorytmy nie należą do specjalnie skomplikowanych, dlatego warto je znać. Polecam też Ci przejrzeć w wolnej chwili, jak działają inne sortowania i porównać ich działanie z tymi opisanymi tutaj.

*  Opisywany tu problem dotyczy programowania obiektowego i nie będzie bliżej opisywany w tym wpisie

Więcej informacji odnośnie algorytmów sortowania: https://www.geeksforgeeks.org/sorting-algorithms/

Lekcja odnośnie samej idei „dziel i rządź”: https://developeronthego.pl/algorytmy-dla-poczatkujacych-2-dziel-i-rzadz/