Sortowanie szybkie - QuickSort

Sortowanie szybkie działa na zasadzie podziału tablicy na dwie części. Jedna z nich zawiera elementy o wartościach mniejszych, a druga elementy o wartościach większych od wartości elementu dzielącego (ang. pivot). Jako element dzielący można wybrać element środkowy, element pierwszy lub element ostatni. Każda z części tak podzielonej tablicy jest poddawana od nowa algorytmowi sortowania szybkiego.

/**
 * Sortowanie szybkie - QuickSort
 * @author kodatnik.blogspot.com 
 */ 
public class SortowanieSzybkie {
 // metoda zamienia miejscami elementy o indeksach i oraz j
 // w tablicy przekazanej jako parametr
 private static void zamien(int[] wejscie, int i, int j) {
  int temp = wejscie[i];
  wejscie[i] = wejscie[j];
  wejscie[j] = temp;
 }  
 
 // metoda dzieli tablicę (od indeksu p do indeksu k) na dwie części
 // - elementy mniejsze od wybranego elementu
 // - elementy większe od wybranego elementu
 private static int podzial(int[] wejscie, int p, int k) {
 
  // wybieramy element wg którego będziemy dzielić
  // np. element ostatni
  int element = wejscie[k];
  
  // ustalamy zakres na którym będziemy operować
  int i = p; 
  int j = k - 1;
  
  // pętla wyszukuje kolejne elementy większe i mniejsze od 
  // elementu dzielącego (zmienna element)
  while(i <= j) {
   while (wejscie[i] <= element && i < k) i++;
   while (wejscie[j] > element && j > p) j--;
   
   // jeśli elementy są na niewłaściwych pozycjach zamieniamy je
   if (i < j) zamien(wejscie, i, j);
   // jeśli indeksy się zrównają kończymy pętlę
   if (i == j) break;
  }
   
  // na końcu wstawiamy element dzielący na właściwą pozycję
  zamien(wejscie, i, k);
    
  // i zwracamy tę pozycję
  return i;
 } 
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 // dodatkowo w jej wywołaniu podajemy indeks pierwszego i ostatniego elementu
 public static void sortowanieSzybkie(int[] wejscie, int i, int j) {

  // jeśli indeksy są równe lub niepoprawne zakończ działanie
  if ( j <= i ) return;

  // dzielimy tablicę na części, indeks miejsca podziału zapisujemy w zmiennej os (oś)
  int os = podzial(wejscie, i, j);
  
  // rekurencyjnie dokonujemy posortowania lewej i prawej części naszej tablicy
  sortowanieSzybkie(wejscie, i, os-1);
  sortowanieSzybkie(wejscie, os+1, j);  
 }   
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowanieSzybkie(tablica, 0, tablica.length-1);
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}

Optymalizacja algorytmu polega na właściwym doborze elementu dzielącego. Najczęściej dokonuje się tego poprzez jego losowy wybór, bądź też wyznaczenie mediany z rozpatrywanych elementów.

Uruchomiona aplikacja:

4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9