[C#|.NET] Sortowanie szybkie (quicksort)

Sortowanie szybkie (quicksort) to jeden z najbardziej popularnych algorytmów sortowania stosowanych w informatyce. Jest on oparty na strategii "dziel i zwyciężaj", która polega na podziale problemu na mniejsze części, rozwiązaniu ich osobno, a następnie połączeniu otrzymanych wyników.

Algorytm sortowania szybkiego działa na zasadzie wybierania elementu osiowego (pivot) z tablicy i porównywania pozostałych elementów z pivotem. Elementy mniejsze od pivota są umieszczane po lewej stronie, a większe po prawej stronie. Następnie sortowanie szybkie jest rekurencyjnie stosowane do obu podtablic - lewej i prawej.

Kluczowym elementem sortowania szybkiego jest wybór odpowiedniego pivota. W przypadku złego wyboru pivota (np. gdy jest on największym lub najmniejszym elementem) może nastąpić degeneracja algorytmu i jego wydajność może znacznie się pogorszyć. Dlatego istnieje wiele strategii wyboru pivota, takich jak wybór losowego elementu, mediany z trzech elementów lub mediany z pięciu elementów.

Sortowanie szybkie ma wiele zalet. Jest to algorytm o złożoności czasowej O(n log n), co oznacza, że jest bardzo wydajny dla dużych zbiorów danych. Ponadto, sortowanie szybkie jest in-place, co oznacza, że nie wymaga dodatkowej pamięci do przechowywania tymczasowych danych. Jest to istotne w przypadku sortowania dużych zbiorów danych, gdzie zarządzanie pamięcią może być trudne.

Jednak sortowanie szybkie ma również pewne wady. Jedną z nich jest to, że jest on wrażliwy na dane wejściowe, zwłaszcza na dane posortowane w odwrotnej kolejności. W takim przypadku sortowanie szybkie może mieć złożoność czasową O(n^2), co jest mniej efektywne niż inne algorytmy sortowania. Jednak wiele implementacji sortowania szybkiego stosuje różne optymalizacje, takie jak losowe wybieranie pivota lub sortowanie przez scalanie dla małych podtablic, aby uniknąć tej sytuacji.

Mimo tych wad, sortowanie szybkie jest szeroko stosowane w praktyce ze względu na swoją wydajność i prostotę implementacji. Jest często używane w bibliotekach programistycznych i frameworkach do sortowania danych.

Przykład

Poniższy program sortuje tablicę liczb całkowitych za pomocą algorytmu sortowania szybkiego. Algorytm jest implementowany rekurencyjnie poprzez podział tablicy na podtablice i porównywanie elementów z wybranym elementem osiowym (pivotem). Tablica jest sortowana w miejscu, bez tworzenia nowych tablic.

using System;

class Program {

    static void Main() {
    
        int[] numbers = { 5, 8, 2, 1, 6, 3, 9, 4, 7 };
        
        Console.WriteLine("Przed sortowaniem:");
        
        PrintArray(numbers);

        QuickSort(numbers, 0, numbers.Length - 1);

        Console.WriteLine("Po sortowaniu:");
        
        PrintArray(numbers);
        
    }

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

    static int Partition(int[] array, int low, int high) {
    
        int pivot = array[high];
        int i = low - 1;

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

        Swap(array, i + 1, high);

        return i + 1;
        
    }

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

    static void PrintArray(int[] array) {
    
        foreach (int number in array) {
        
            Console.Write(number + " ");
            
        }
        
        Console.WriteLine();
        
    }
    
}