Selection Sort w C# — Warianty, Generyki i Granice Użyteczności

Kąt widzenia: praktyczny/rozszerzenia — implementacja generyczna, warianty algorytmu, benchmark vs Array.Sort, kiedy Selection Sort odpada
Przykład przewodni: sortowanie zamówień e-commerce po wielu kryteriach

Od int[] do generycznej implementacji

Bazowa implementacja z poprzedniego posta działa tylko dla int. W realnym projekcie sortujemy obiekty domenowe. Dwa podejścia — przez IComparable<T> lub przez Comparison<T> delegate.

Wariant 1: ograniczenie generyczne IComparable<T>

public static class SelectionSort
{
    public static void Sort<T>(T[] arr) where T : IComparable<T>
    {
        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < n; j++)
            {
                // CompareTo: ujemna wartość = j jest mniejsze od minIdx
                if (arr[j].CompareTo(arr[minIdx]) < 0)
                    minIdx = j;
            }

            if (minIdx != i)
                (arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
        }
    }
}

Działa dla wszystkich typów, które implementują IComparable<T>: int, string, decimal, DateTime, i dowolne klasy/rekordy z tą implementacją.

Wariant 2: Comparison<T> delegate — elastyczność bez modyfikacji typów

public static void Sort<T>(T[] arr, Comparison<T> compare)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (compare(arr[j], arr[minIdx]) < 0)
                minIdx = j;
        }

        if (minIdx != i)
            (arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
    }
}

Ten wariant jest bardziej użyteczny w praktyce, bo:

• Nie wymaga modyfikacji klasy (nie musisz implementować IComparable<T>)
• Możesz posortować po dowolnym polu przez lambdę
• Możesz odwrócić kierunek bez tworzenia IComparer<T>

Przykład domenowy: zamówienia e-commerce

public record Order(
    Guid Id,
    string CustomerName,
    decimal TotalAmount,
    DateTimeOffset CreatedAt,
    OrderPriority Priority);

public enum OrderPriority { Standard = 0, Express = 1, VIP = 2 }

Trzy różne sortowania tego samego zbioru danych przez zmianę Comparison<T>:

var orders = new Order[]
{
    new(Guid.NewGuid(), "Kowalski",  150.00m, DateTimeOffset.Now.AddHours(-3), OrderPriority.Standard),
    new(Guid.NewGuid(), "Nowak",     890.50m, DateTimeOffset.Now.AddHours(-1), OrderPriority.VIP),
    new(Guid.NewGuid(), "Wiśniewska", 45.00m, DateTimeOffset.Now.AddHours(-5), OrderPriority.Express),
    new(Guid.NewGuid(), "Zając",     340.00m, DateTimeOffset.Now.AddHours(-2), OrderPriority.VIP),
};

// Sortowanie po wartości zamówienia (rosnąco)
SelectionSort.Sort(orders, (a, b) => a.TotalAmount.CompareTo(b.TotalAmount));

// Sortowanie po priorytecie (malejąco) — VIP pierwsze
SelectionSort.Sort(orders, (a, b) => b.Priority.CompareTo(a.Priority));

// Sortowanie złożone: najpierw priorytet (malejąco), przy równych — data (rosnąco)
SelectionSort.Sort(orders, (a, b) =>
{
    int priorityCompare = b.Priority.CompareTo(a.Priority);
    return priorityCompare != 0
        ? priorityCompare
        : a.CreatedAt.CompareTo(b.CreatedAt);
});

Sortowanie złożone bez żadnej modyfikacji klasy Order i bez tworzenia osobnych klas IComparer<T>.

Wariant algorytmu: dwukierunkowy Selection Sort

Standardowy Selection Sort szuka minimum w każdej iteracji. Wariant bidirectional szuka jednocześnie minimum i maksimum — potrzebuje połowy iteracji zewnętrznej pętli.

public static void BidirectionalSort<T>(T[] arr, Comparison<T> compare)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left < right)
    {
        int minIdx = left;
        int maxIdx = right;

        for (int j = left; j <= right; j++)
        {
            if (compare(arr[j], arr[minIdx]) < 0)
                minIdx = j;

            if (compare(arr[j], arr[maxIdx]) > 0)
                maxIdx = j;
        }

        // Umieść minimum na lewym końcu
        if (minIdx != left)
            (arr[left], arr[minIdx]) = (arr[minIdx], arr[left]);

        // Jeśli maximum było na pozycji `left` — teraz jest na `minIdx` po zamianie
        if (maxIdx == left)
            maxIdx = minIdx;

        // Umieść maximum na prawym końcu
        if (maxIdx != right)
            (arr[right], arr[maxIdx]) = (arr[maxIdx], arr[right]);

        left++;
        right--;
    }
}

Kluczowy edge case (linia z komentarzem): jeśli maksimum siedziało na pozycji left, po pierwszej zamianie trafia na minIdx. Przed drugą zamianą musimy zaktualizować maxIdx = minIdx.

Czy to faktycznie szybsze?

Zmniejsza liczbę iteracji zewnętrznej pętli o połowę (n/2 zamiast n-1). Ale wewnętrzna pętla nadal przegląda wszystkie elementy między left a right. Całkowita liczba porównań pozostaje O(n²).

W praktyce: BenchmarkDotNet pokaże marginalną różnicę — głównie z powodu mniejszej liczby wywołań zewnętrznej pętli. Nie jest to przełom wydajnościowy, ale pokazuje ciekawy wariant algorytmu.

Benchmark: Selection Sort vs Array.Sort

[MemoryDiagnoser]
[SimpleJob(RuntimeMoniker.Net90)]
public class SortingBenchmarks
{
    private int[] _data = [];

    [Params(10, 100, 1000, 10_000)]
    public int N { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        _data = Enumerable.Range(0, N)
            .Select(_ => Random.Shared.Next(0, 10_000))
            .ToArray();
    }

    [Benchmark(Baseline = true)]
    public void ArraySort()
    {
        var copy = (int[])_data.Clone();
        Array.Sort(copy);
    }

    [Benchmark]
    public void SelectionSortBasic()
    {
        var copy = (int[])_data.Clone();
        SelectionSort.Sort(copy);
    }

    [Benchmark]
    public void BidirectionalSelectionSort()
    {
        var copy = (int[])_data.Clone();
        SelectionSort.BidirectionalSort(copy, (a, b) => a.CompareTo(b));
    }
}

Reprezentatywne wyniki (orientacyjne — rzeczywiste zależą od maszyny):

Array.Sort to Introsort — hybryd QuickSort + HeapSort + Insertion Sort. Dla n=10 000 jest ~250× szybszy od Selection Sort. Różnica rośnie kwadratowo: podwojenie n = czterokrotnie wolniejszy Selection Sort, ale tylko ~2× wolniejszy Array.Sort.

Wniosek: po n≈50 Array.Sort wygrywa dla danych losowych bez wyjątku.

Kiedy Selection Sort odpada i co zamiast

Duże kolekcje — Array.Sort lub List<T>.Sort

// Prosta tablica wartości — Array.Sort z Comparison<T>
Array.Sort(orders, (a, b) => a.TotalAmount.CompareTo(b.TotalAmount));

// Lista — List<T>.Sort
orderList.Sort((a, b) => a.TotalAmount.CompareTo(b.TotalAmount));

Array.Sort i List<T>.Sort to ten sam Introsort pod spodem — O(n log n), stabilny od .NET 4.5 dla typów referencyjnych.

LINQ — gdy potrzebujesz nowej kolekcji bez modyfikacji oryginału

// Nie modyfikuje tablicy — zwraca IOrderedEnumerable<Order>
var sortedOrders = orders
    .OrderByDescending(o => o.Priority)
    .ThenBy(o => o.CreatedAt)
    .ToList();

LINQ OrderBy jest stabilny i obsługuje sortowanie złożone elegancko przez chaining. Dla IQueryable<T> (EF Core) generuje SQL ORDER BY — sortowanie dzieje się w bazie, nie w pamięci.

Prawie posortowane dane — Insertion Sort

// Insertion Sort ma O(n) dla prawie posortowanych danych
// Selection Sort zawsze O(n²) — nie "widzi" że tablica jest prawie gotowa

Selection Sort w .NET — gdzie faktycznie jest używany

Wbrew pozorom Selection Sort nie jest tylko algorytmem do nauki. Introsort (używany przez Array.Sort) przełącza się na Insertion Sort dla podtablic poniżej 16 elementów. Selection Sort nigdy nie był popularny w implementacjach bibliotecznych — właśnie przez niestabilność i brak adaptacji do danych wejściowych.

Realne scenariusze gdzie Selection Sort jest rozsądnym wyborem:

Embedded/IoT z ograniczoną pamięcią Flash: każda operacja zapisu na Flash skraca żywotność. Selection Sort = n-1 zamian (niezależnie od danych). Inne algorytmy mogą robić O(n²) zamian.

Sortowanie małych zbiorów gdzie prostota > wydajność: masz 5-10 elementów, kod jest pisany w stylu edukacyjnym lub demonstracyjnym. Selection Sort jest prosty do napisania z pamięci i wytłumaczenia.

Algorytm do nauki i weryfikacji: w testach jednostkowych sortowania można użyć Selection Sort jako „oracle” — mały, prosty, łatwy do weryfikacji poprawności.

Rozszerzenie: wersja zwracająca nową kolekcję (immutable)

Bazowa wersja modyfikuje tablicę in-place. Czasem chcesz sortować bez modyfikowania oryginału:

public static T[] SortedCopy<T>(IEnumerable<T> source, Comparison<T> compare)
{
    // ToArray() materializuje i kopiuje dane
    var arr = source.ToArray();
    Sort(arr, compare);
    return arr;
}

// Użycie
Order[] originalOrders = GetOrders();
Order[] sortedByAmount = SelectionSort.SortedCopy(
    originalOrders,
    (a, b) => a.TotalAmount.CompareTo(b.TotalAmount));

// originalOrders niezmienione

W praktyce dla tego scenariusza LINQ .OrderBy(...).ToArray() jest czytelniejszy i szybszy — ale jeśli z jakiegoś powodu musisz użyć Selection Sort, ta forma jest bezpieczna.

Testy generycznej wersji

public class SelectionSortGenericTests
{
    [Fact]
    public void Sort_Strings_ShouldSortAlphabetically()
    {
        string[] names = ["Zając", "Kowalski", "Nowak", "Adamski"];
        SelectionSort.Sort<string>(names, string.Compare);
        Assert.Equal(["Adamski", "Kowalski", "Nowak", "Zając"], names);
    }

    [Fact]
    public void Sort_ByDecimalDescending_ShouldWork()
    {
        decimal[] prices = [9.99m, 1.50m, 45.00m, 3.75m];
        // Odwracamy porównanie dla malejącego
        SelectionSort.Sort(prices, (a, b) => b.CompareTo(a));
        Assert.Equal([45.00m, 9.99m, 3.75m, 1.50m], prices);
    }

    [Fact]
    public void Sort_Orders_ByPriorityThenDate()
    {
        var now = DateTimeOffset.UtcNow;
        var orders = new Order[]
        {
            new(Guid.NewGuid(), "A", 100m, now.AddHours(-1), OrderPriority.Standard),
            new(Guid.NewGuid(), "B", 200m, now.AddHours(-3), OrderPriority.VIP),
            new(Guid.NewGuid(), "C", 300m, now.AddHours(-2), OrderPriority.VIP),
        };

        SelectionSort.Sort(orders, (a, b) =>
        {
            int p = b.Priority.CompareTo(a.Priority); // VIP pierwsze
            return p != 0 ? p : a.CreatedAt.CompareTo(b.CreatedAt);
        });

        // VIP: C (2h temu) przed B (3h temu)? Nie — B jest starsze, więc CreatedAt B < C
        // Więc kolejność VIP: B (AddHours(-3)) przed C (AddHours(-2))
        Assert.Equal("B", orders[0].CustomerName);
        Assert.Equal("C", orders[1].CustomerName);
        Assert.Equal("A", orders[2].CustomerName);
    }

    [Fact]
    public void BidirectionalSort_ShouldProduceSameResultAsBasic()
    {
        int[] arr1 = [5, 3, 8, 1, 9, 2, 7, 4, 6];
        int[] arr2 = (int[])arr1.Clone();

        SelectionSort.Sort<int>(arr1, (a, b) => a.CompareTo(b));
        SelectionSort.BidirectionalSort(arr2, (a, b) => a.CompareTo(b));

        Assert.Equal(arr1, arr2);
    }
}

Podsumowanie

Generyczna wersja z Comparison<T> to najbardziej użyteczna forma dla kodu produkcyjnego. Ale pamiętaj: jeśli n > kilkadziesiąt i czas ma znaczenie — Array.Sort jest 10–250× szybszy i nie wymaga pisania własnego algorytmu.

Poprzedni post: Selection Sort w C# — Mechanika, Złożoność i Analiza Krok po Kroku — dokładna wizualizacja kroków algorytmu, analiza O(n²), i porównanie z Bubble Sort i Insertion Sort.