Algorytm QuickSort
Sortowanie szybkie
Algorytm sortowania szybkiego jest chyba najczęściej wykorzystywanym algorytmem sortowania. Tak na marginesie - już sama nazwa sugeruje nam, że jest on szybki. To nie do końca prawda, bo istnieją algorytmy szybsze. Szybsze zawsze, ale dla określonego zestawu danych, ale też szybsze w szczególnych przypadkach. Postanowiłem nieco rozwinąć temat algorytmu QuickSort, bo jest on wykorzystywany zarówno w .NET (metody Array.Sort(), List
Zasada działania algorytmu
Podstawowa zasada jest bardzo prosta: podziel tablicę źródłową na dwie mniejsze tak, aby z jednej strony podziału znajdowały się elementy mniejsze (lub równe), a z drugiej większe (lub równe) elementowi dzielącemu. Każda z podtablic poddawana jest kolejnej operacji sortowania, rekurencyjnie. Gdy tablica o posortowania ma 1 element, rekursja się kończy (czasem ogranicza sie już na poziomie dwóch elementów, które wystarczy zamienić miejscami - w zależności od implementacji. Algorytm QuickSort należy do grupy algorytmów typu dziel i zwyciężaj. Jeżeli operacja do wykonania jest duża, dzielimy ją na mniejsze kawałki. Te mniejsze kawałki dzielimy na jeszcze mniejsze, aż do momentu, gdy problem staje się trywialny (na przykład wspomniane wcześniej sortowanie dwóch elementów). Podobnie działa algorytm sortowania ze scalaniem (więcej na temat praktycznych zastosowań samego algorytmu scalania można znaleźć we wpisie Algorytm merge w praktyce.
Algorytm QuickSort ma złożoność obliczeniową rzędu O(n log(n)) dla przeciętnych przypadków, podczas gdy złożoność pesymistyczna sięga O(n^2). Złożoność taką czasem uzyskuje się dla elementów już posortowanych, czasem dla posortowanych odwrotnie, a czasem dla bardzo specyficznego układu wartościWszystko zależy od sposobu określania elementu wyznaczającego podział. Biblioteka .NET i metoda Array.Sort() za element podziału wybiera środek tablicy. Tak też się dzieje w pokazanej implementacji algorytmu.. Posortowana tablica jest najgorszym przypadkiem, jeżeli element podziału wyznaczany jest pierwszym elementem tej tablicy. Analogicznie, dla tablicy posortowanej odwrotnie, najgorszy efekt uzyskujemy dla elementu podziału ustalonego przez ostatni element. Teoretycznie najlepiej wybierać medianę, ale koszt znalezienia mediany znacznie spowolniłby działanie algorytmu. Algorytm nie nazywałby się QuickSort - szybkie sortowanie.
Przykładowa implementacja w C#
Przyjrzyjmy się zatem przykładowej implementacji pokazanej na poniższym listingu:
static void Main(string[] args)
{
string[] letters = { "k", "a", "r", "a", "c", "z", "a", "n" };
int[] numbers = { 3, 6, 8, 3, 9, 2, 4, 2 };
QuickSort(letters);
PrintArray(letters);
QuickSort(numbers);
PrintArray(numbers);
}
//Wypisz tablicę
public static void PrintArray<T>(T[] unsorted)
{
Console.WriteLine(string.Join<T>(", ", unsorted));
}
//Metoda QuickSort
public static void QuickSort<T>(T[] array)
where T : IComparable
{
QuickSort(array, 0, array.Length - 1);
}
//Prywatna metoda z rekurencyjnymi wartościami ograniczeń
private static void QuickSort<T>(T[] array, int leftBound, int rightBound)
where T : IComparable
{
var left = leftBound;
var right = rightBound;
//Wyznacz element podziału - środek tablicy
var center = array[(leftBound + rightBound) / 2];
while (left < right)
{
//pomiń elementy leżące po właciwej stronie z lewej
while (array[left].CompareTo(center) < 0)
left++;
//pomiń elementy leżące po właciwej stronie z prawej
while (array[right].CompareTo(center) > 0)
right--;
if (left <= right)
{
var temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
//Rekurencja po lewej stronie
if (leftBound < right)
QuickSort(array, leftBound, right);
//Rekurencja po prawej stronie
if (left < rightBound)
QuickSort(array, left, rightBound);
}
}
Wynik działania programu zostanie wypisany w oknie konsoli, a będą to dwie posortowane tablice. Jedna z tablic będzie wypełniona liczbami całkowitymi, druga natomiast łańcuchami znaków. Metoda nadaje się do sortowania wszystkich typów, które implementują interfejs IComparable.
Jakie są problemy z algorytmem?
Istnieje bardzo dużo różnych implementacji i odmian algorytmu QuickSort. To, że algorytm może mieć złożoność kwadratową to jeden problem. Pamiętajmy, że przy każdym rekurencyjnym wywołaniu na stosie odkładane są parametry określające początek i koniec obszaru do posortowania (w przykładzie na stosie leży również referencja do tablicy). Dla pesymistycznego przykładu ten stos będzie miał rozmiar tablicy! To właśnie dlatego stosuje się techniki zagłębiania najpierw w obszary mniejsze, to dlatego obszary krótsze niż kilka, kilkanaście elementów sortuje się innymi algorytmami. Innym problemem jest wyznaczanie punktu środkowego, który powinien być elementem środkowym, czyli medianą. Znając statystyczny rozkład danych można tak dostosować algorytm, aby za punkt podziału brać medianę lub wartość zbliżona do medianySQL Server może gromadzić takie statystyki dla wybranych kolumn..
Pomimo kilku problemów, algorytm najczęściej sprawuje się znakomicie. Trzeba bowiem wiedzieć, że i inne algorytmy nie są pozbawione wad. Czy twórcy .NET skorzystaliby z algorytmu QuickSort, gdyby był zły? Czy gdyby znali lepszy, szybszy, bardziej uniwersalny, nie skorzystaliby z niego?
QuickSort to szybki algorytm uniwersalny, ale istnieją algorytmy, które lepiej sprawdzą się w szczególnych przypadkach. I o nich też należy pamiętać.
Brak komentarzy - bądź pierwszy