Spis treści:

Kategoria:AlgorytmyC#


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.Sort()W praktyce stosowana jest szczególna postać algorytmu QuickSort z ograniczeniami rekursji i kopcowaniem (algorytm sortowania przez kopcowanie).), jak i w SQL Server. Sam algorytm może nie jest najszybszy - jest jednak uniwersalny.

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:

//Test metody QuickSort
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ć.

Kategoria:AlgorytmyC#

, 2013-12-20

Brak komentarzy - bądź pierwszy

Dodaj komentarz
Wyślij
Ostatnie komentarze
Dzieki za te informacje. były kluczowe
Dobrze wyjaśnione, dzięki !
a z innej strony - co gdybym ciąg znaków chciał mieć rozbity nie na wiersze a na kolumny? Czyli ciąg ABCD: 1. kolumna: A, 2. kolumna: B, 3. kolumna: C, 4 kolumna: D?
Ciekawy artykuł.
Czy można za pomocą EF wysłać swoje zapytanie?
Czy lepiej do tego użyć ADO.net i DataTable?