Quick Sort

Quick Sort to jedno z najszybszych i najczęściej używanych algorytmów sortowania. Jest to algorytm oparty na strategii “dziel i zwyciężaj”. Działa poprzez wybór elementu zwanego “pivotem”. Podział kolekcji na elementy mniejsze i większe od pivota. Następnie sortowanie tych dwóch pod kolekcji. Dzięki temu, że pivot jest umieszczany na właściwej pozycji w posortowanej kolekcji. Proces jest rekurencyjnie powtarzany, aż cała kolekcja zostanie posortowana.

Oto kroki działania algorytmu Quick Sort:

1. Wybór pivota: Wybieramy jeden element z kolekcji jako pivot. Może to być np. pierwszy, ostatni lub losowo wybrany element.
2. Podział kolekcji: Przechodzimy przez kolekcję i umieszczamy elementy mniejsze od pivota po jego lewej stronie, a większe po prawej stronie.
3. Rekurencyjne sortowanie: Wywołujemy rekurencyjnie Quick Sort dla dwóch podkolekcji: lewej (z elementami mniejszymi od pivota) i prawej (z elementami większymi od pivota).
4. Łączenie podkolekcji: Po posortowaniu podkolekcji, elementy mniejsze od pivota (z lewej) znajdują się już w odpowiedniej kolejności względem siebie, tak samo jak elementy większe od pivota (z prawej). Możemy teraz połączyć te podkolekcje w jedną posortowaną kolekcję.

Algorytm Quick Sort jest wydajny dla dużej ilości danych i często jest preferowany ze względu na swoją przeciętną złożoność czasową O(n log n). Niemniej jednak, jego wydajność może zmniejszyć się w przypadku, gdy wybór pivota nie jest odpowiednio zrównoważony, co może prowadzić do najgorszego przypadku o złożoności O(n^2).

Dlatego też wiele implementacji Quick Sort stosuje różne techniki wyboru pivota, takie jak wybór mediany z trzech losowych elementów, aby minimalizować ryzyko tego scenariusza.

Implementacja algorytmu

using System;

class QuickSort
{
    static int Partition(int[] array, int low, int high)
    {
        int pivotIndex = ChoosePivot(array, low, high);
        int pivotValue = array[pivotIndex];

        // Przenoszenie pivota na koniec tablicy
        Swap(array, pivotIndex, high);

        int leftIndex = low;

        for (int i = low; i < high; i++)
        {
            if (array[i] < pivotValue)
            {
                Swap(array, i, leftIndex);
                leftIndex++;
            }
        }

        // Przenoszenie pivota na właściwą pozycję
        Swap(array, leftIndex, high);

        return leftIndex;
    }

    static int ChoosePivot(int[] array, int low, int high)
    {
        // Wybieramy trzy losowe elementy
        int a = new Random().Next(low, high + 1);
        int b = new Random().Next(low, high + 1);
        int c = new Random().Next(low, high + 1);

        // Zwracamy medianę z trzech losowych elementów
        return Math.Max(Math.Min(a, b), Math.Min(Math.Max(a, b), c));
    }

    static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    static void QuickSortAlgorithm(int[] array, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(array, low, high);
            QuickSortAlgorithm(array, low, pivotIndex - 1);
            QuickSortAlgorithm(array, pivotIndex + 1, high);
        }
    }

    static void QuickSortWrapper(int[] array)
    {
        QuickSortAlgorithm(array, 0, array.Length - 1);
    }

    static void Main(string[] args)
    {
        int[] numbers = { 12, 45, 7, 23, 56, 34, 67, 89 };

        QuickSortWrapper(numbers);

        Console.WriteLine("Posortowana tablica:");
        foreach (int num in numbers)
        {
            Console.Write(num + " ");
        }
    }
}

W tej implementacji używamy funkcji Partition, aby podzielić kolekcję na elementy mniejsze i większe od pivota. Wybór pivota jest oparty na wyborze mediany z trzech losowych elementów. Implementacja jest rekurencyjna i sortuje podkolekcje aż do osiągnięcia jednoelementowych podkolekcji.

Podczas implementacji algorytmu Quick Sort w C# i w rzeczywistych projektach programistycznych warto zwrócić uwagę na kilka istotnych aspektów, które pomogą zapewnić poprawność działania i wydajność kodu:

1. Poprawność algorytmu: Upewnij się, że algorytm Quick Sort działa poprawnie i sortuje elementy w odpowiedniej kolejności. Testuj go na różnych zestawach danych, w tym na danych posortowanych, odwrotnie posortowanych oraz losowych.
2. Wybór pivota: Wartościowy wybór pivota ma ogromny wpływ na wydajność algorytmu. Wybierz strategię wyboru pivota, która minimalizuje ryzyko najgorszego przypadku. Wybór mediany z trzech losowych elementów jest popularną opcją.
3. Obsługa duplikatów: Algorytm Quick Sort w bazowej wersji może nie radzić sobie dobrze z dużą liczbą powtarzających się elementów w kolekcji. W takim przypadku, rozważenie strategii radzenia sobie z duplikatami lub wyboru innego algorytmu sortowania może być uzasadnione.
4. Optymalizacja rekursji: W przypadku bardzo dużych kolekcji, rekursja może prowadzić do przepełnienia stosu. Rozważanie optymalizacji poprzez użycie tzw. “tail recursion optimization” lub iteracyjnej wersji algorytmu.
5. Testowanie i profilowanie: Regularne testowanie algorytmu na różnych zestawach danych jest kluczowe. Użyj narzędzi do profilowania, aby ocenić wydajność algorytmu w zależności od różnych danych wejściowych.
6. Ochrona przed przepełnieniem: Upewnij się, że algorytm jest zabezpieczony przed przepełnieniem przy wykonywaniu operacji indeksowania i zamiany elementów.
7. Komunikacja: Jeśli kod jest częścią większego projektu, komentuj go w sposób klarowny i dostarczający zrozumienia innym programistom.
8. Złożoność czasowa i pamięciowa: Pamiętaj, że Quick Sort ma przeciętną złożoność czasową O(n log n), ale jego złożoność pamięciowa może być wyższa niż w niektórych innych algorytmach sortowania.
9. Zarządzanie pamięcią: W języku C#, nie musisz bezpośrednio zarządzać pamięcią, ale upewnij się, że nie dochodzi do wycieków pamięci i że zbędne obiekty są prawidłowo usuwane przez garbage collector.
10. Równoległe sortowanie: W pewnych przypadkach, warto rozważyć równoległe sortowanie, gdzie można podzielić kolekcję na mniejsze fragmenty i sortować je równolegle, co może poprawić wydajność.

Zwracając uwagę na te aspekty, możesz skonstruować dobrze działający i wydajny algorytm Quick Sort w swoim projekcie w C#.