Jason. Cała informatyka w jednym miejscu!

Zaczynamy kolejny artykuł z algorytmiki! Zapoznam Was teraz z częścią jak funkcjonuje sortowanie szybkie. Kolejny dodatek do kolekcji algorytmów sortujących, a ten nawet jest szybszy od sortowania przez wybieranie! Prosimy do środka!

SORTOWANIE SZYBKIE, ALE NA JAKIEJ PODSTAWIE "SZYBKIE"?

Możesz pomyśleć: "a co, w takim razie reszta algorytmów jest wolna, czy co?". To nie chodzi o nazwę, tylko o sposób działania. "Quicksort" nazywany po polsku "sortowaniem szybkim" to algorytm sortujący elementy w danym zbiorze wejściowym charakteryzujący się niziutką złożonością obliczeniową według notacji dużego O (nazwa pochodzi stąd, iż jest to najszybszy algorytm sortujący), choć nie zawsze może być taka sama! W tym przypadku mamy wyjątkową sytuację, ponieważ złożoność obliczeniowa w najlepszym razie może wynosić O(n*log(n)) (a już wiecie co to oznacza ;)), ale przy złym zaimplementowaniu algorytmu sortowania szybkiego możemy się spodziewać złożoności O(n2)! Dobra wiadomość jest taka, że mamy na to realny wpływ w którą stronę pójdzie algorytm. Jak to możliwe i od czego to zależy, to potem. Zajmijmy się wpierw wytłumaczeniem postępowania krok po kroku.

Problem: uporządkowanie zbioru elementów w kolejności rosnącej / malejącej wg ustalonego kryterium (tak, znowu)

GENIUSZ TKWI W...DZIELENIU

Mamy pewien zbiór liczb całkowitych i mamy za zadanie go posortować, powiedzmy w kolejności rosnącej. Stosując sortowanie szybkie wykorzystujemy technikę "dziel i rządź" celem sprowadzenia do przypadku podstawowego, jakim będzie skrócenie zbioru danych góra do dwóch elementów. Żeby tego dokonać, algorytm dzieli za każdym razem zbiór liczbowy na dwie połowy stosując się do wybranego "punktu osiowego" (ang. "pivot"). Dzielenie na połówki objawia się tym, że po lewej stronie lądują liczby MNIEJSZE od punktu osiowego, a po prawej stronie wszystkie liczby WIĘKSZE od punktu osiowego. I nie ma żadnych wyjątków od tej zasady!

Przypadek podstawowy "poradzi sobie" z dwuelementowym, jednoelementowym oraz pustym zbiorem danych. Mając do dyspozycji tylko dwa elementy, to sortowanie sprowadza się do instrukcji warunkowej czy liczba w drugiej komórce (indeks równy 1) jest mniejsza od liczby w pierwszej komórce (indeks równy zero). Jeśli to prawda, to zamieniamy miejscami, zwracamy na wyjściu i gitara. "Sortowanie" ukończone. Kiedy jest jeden element albo nie ma żadnego, to zwracamy to co jest i "finito". W wyniku rekurencyjnego "powracania" do początku stosu wywołań metody, program skleja wszystkie części posortowanych zbiorów i tak oto powstaje pełny posortowany zbiór, a my jesteśmy "happy". Z tego powodu wszystkie elementy muszą przestrzegać hierarchii według wyznaczonego punktu osiowego, czyli mniejsze po lewej, większe po prawej.

Sortowanie szybkie

"Quicksort" czyli sortowanie szybkie, polega na konsekwentnym dzieleniu zbioru danych na mniejsze części, aż ustalenie kolejności stanie się trywialne (rozmiar <= 2).

ZŁOŻONOŚĆ ZALEŻY OD CIEBIE

Jeszcze tylko wyjaśnię dlaczego sortowanie szybkie charakteryzuje się "chwiejną" złożonością obliczeniową i przedstawiam kod źródłowy. Najpierw najważniejsze: o wszystkim decyduje dobór punktu osiowego. Jeżeli wybierzemy pierwszą lepszą liczbę z początku lub końca, to takie podejście będzie skutkować tą gorszą złożonością obliczeniową. To ma swoje uargumentowanie dlaczego tak się dzieje. Otóż wynika to z działania rekurencji. Powtórzę się, że rekursja tworzy "pod maską" stos wywołań tej samej metody. Za każdym razem gdy musimy podzielić zbiór danych na mniejsze kawałeczki aż do doprowadzenia do dwóch lub mniej elementów, kosztuje to dodatkowy cykl. Im większa głębokość stosu, tym większa złożoność i więcej pracy dla procesora. Stąd wniosek nasuwa się tylko jeden: aby zmniejszyć liczbę cykli rekurencyjnych, musimy zmniejszyć stos wywołań. Możemy to zrobić poprzez wybranie odpowiedniego punktu osiowego, tak aby podzielone zbiory miały elementy rozłożone w miarę równomiernie. Czy jest jakaś tajemna receptura na to?

Nie! Wystarczy wybierać punkt...pseudolosowo!!! I to wystarczy. Czemu? Bo sortowanie szybkie ma to do siebie, że przypadek optymistyczny złożoności obliczeniowej jest równy przypadkowi średniemu (pomijając wartości stałe), jakim jest O(n*log(n)), czyli rozmiar danych przemnożony przez głębokość stosu wywołań rekurencyjnych (logarytm pochodzi stąd, że w najlepszym przypadku rozmiar danych jest zawsze dzielony przez dwa). Chociaż można dobrać punkt osiowy jeszcze lepiej (najlepiej byłoby znaleźć medianę spośród wszystkich liczb), to pseudolosowanie takiego punktu "na pałę" daje zazwyczaj dobre rezultaty i wtedy złożoność obliczeniowa jest o wiele mniejsza.

KOD ŹRÓDŁOWY

Moi mili, a teraz kod źródłowy w Javie ukazujący sortowanie szybkie w akcji!

KLASA "MAIN"
public class Main {
	public static void main(String[] args) {
		new Quicksort();
	}
}
KLASA "QUICKSORT"
import java. util.Arrays;
import java. util.Random;
import java. util.ArrayList;
import java. util.Collections;

public class Quicksort
{
	public Quicksort() {
		ArrayList<Integer> inputNumbers = new ArrayList<>(Arrays.asList(56, -5, -70, 78, 2));

		System.out.println(sortedNumbers(inputNumbers));
	}

	private ArrayList<Integer> sortedNumbers(ArrayList<Integer> numbers) {
		if(numbers.size() <= 1) {
			return numbers;
		}
		else if(numbers.size() == 2) {
			if(numbers.get(1) < numbers.get(0)) {
				Collections.swap(numbers, 0, 1);
			}

			return numbers;
		}
		else {
			Random random = new Random();
			int randomIndex = random.nextInt(0, numbers.size());
			int pivot = numbers.get(randomIndex);
			ArrayList<Integer> lowerNumbers = numbersLowerThanPivot(numbers, pivot);
			ArrayList<Integer> higherNumbers = numbersHigherThanPivot(numbers, pivot);
			ArrayList<Integer> result = new ArrayList<>(sortedNumbers(lowerNumbers));

			result.add(pivot);
			result.addAll(sortedNumbers(higherNumbers));

			return result;
		}
	}

	private ArrayList<Integer> numbersLowerThanPivot(ArrayList<Integer> input, int pivot) {
		ArrayList<Integer> numbers = new ArrayList<>();

		for (int i : input) {
			if(i < pivot) {
				numbers.add(i);
			}
		}

		return numbers;
	}

	private ArrayList<Integer> numbersHigherThanPivot(ArrayList<Integer> input, int pivot) {
		ArrayList<Integer> numbers = new ArrayList<>();

		for (int i : input) {
			if(i > pivot) {
				numbers.add(i);
			}
		}

		return numbers;
	}
}

Idea jest dosyć przejrzysta. Wprowadzamy do metody sortującej pewien zbiór liczb całkowitych, a wewnątrz treści "sortedNumbers" mamy serię przypadków jakie musimy rozpatrzeć używając instrukcji warunkowych:

  • Pierwszy przypadek: zbiór jest pusty lub zawiera jeden element
    • Wtedy sprawa jest oczywista, nic nie robimy tylko oddajemy zbiór z powrotem.
  • Drugi przypadek: zbiór jest dwuelementowy
    • Sprawdzamy czy element drugi jest mniejszy od elementu pierwszego. Jeżeli tak, to zamieniamy je miejscami i tu pozwoliłem sobie skorzystać z wygodnej metody statycznej "swap" z klasy "Collections", która to elegancko mi zamienia elementy miejscami po podaniu kolekcji, indeksu pierwszego elementu i indeksu drugiego elementu. Na końcu, zwrot zbioru.
  • Trzeci przypadek: zbiór ma więcej niż dwa elementy
    • I tu się robi najciekawiej, drodzy Państwo. Najpierw tworzymy sobie zmienną lokalną dla generatora liczb pseudolosowych. Potem losujemy liczbę całkowitą dla indeksu elementu jaki zostanie naszym punktem osiowym ("randomIndex"). Metoda "nextInt" losuje liczbę całkowitą z przedziału od wartości w pierwszym parametrze włącznie do wartości w drugim parametrze wyłącznie (nawias okrągły domykania przedziału w matematyce). Pobieramy odniesienie liczby całkowitej o podanym indeksie i to staje się naszym punktem osiowym nazywanym po angielsku "pivot". Definiujemy sobie aż trzy nowe zbiory liczb całkowitych: dla liczb po lewej stronie, dla liczb po prawej stronie oraz dla samego punktu osiowego (Java nie zezwala na tworzenie list wprowadzając jednocześnie inne listy i pojedyncze dane). Nie trzeba tłumaczyć metod wyszukujących liczb całkowitych mniejszych i większych od podanej. Dochodzimy w ten sposób do "sklejenia" wszystkich wartości w liście "result" zaczynając od liczb po lewej stronie, przechodząc przez dodanie samego punktu osiowego ("add"), aż skończywszy na uzupełnieniu o liczby znalezione po prawej stronie i bach, instrukcja "return" i zwracamy tak "sklejoną" listę z danymi. Na tym sortowanie szybkie się kończy.

Instrukcje mogą nie odzwierciedlać zasady działania w podany sposób, natomiast język Java jest rygorystyczny i nie udostępnia abstrakcyjnych zapisów jakie znaleźlibyśmy w Pythonie (jak choćby "zwróć [lewy podzbiór] + [punkt osiowy] + [prawy podzbiór]"). Jeżeli się przyjrzycie tym instrukcjom, to zobaczycie że kod w całości odpowiada temu, co napisałem na samym początku.


Zakończyłem wątek sortowania szybkiego. On ma swoje wady, może wymagać kilkunastogodzinnych posiedzeń przy wyświetlaczu, jednak kiedy raz wpadnie do głowy rozumienie, to już w tej głowie zostanie i będziecie wiedzieć jak działa "qsort" w języku C ;). Pozdro!

PODOBNE ARTYKUŁY