Selection Sort w C# — mechanika i złożoność

Kąt widzenia: edukacyjny/analityczny — jak dokładnie działa algorytm, dlaczego O(n²), i w czym różni się od Bubble Sort i Insertion Sort
Przykład przewodni: sortowanie wyników graczy w leaderboardzie gry

Czym jest Selection Sort

Selection Sort rozwiązuje sortowanie przez powtarzanie jednej prostej operacji: znajdź minimum w nieposortowanej części, przenieś je na jej początek.

Intuicja: wyobraź sobie tasowanie kart. Przeglądasz wszystkie karty w ręce, wyciągasz najniższą i kładziesz na stole. Potem przeglądasz to, co zostało, wyciągasz kolejną najniższą — i tak dalej, aż sterta na stole jest gotowa.

Różnica od Bubble Sort: Bubble Sort porównuje sąsiednie elementy i zamienia je „w locie”. Selection Sort najpierw szuka minimum przez cały przebieg nieposortowanej tablicy, potem dokonuje dokładnie jednej zamiany na końcu każdej iteracji zewnętrznej pętli.

Wizualizacja krok po kroku

Sortujemy wyniki graczy: [89, 43, 7, 55, 21]

Iteracja 0 — szukamy minimum w całej tablicy [0..4]:

[89, 43, 7, 55, 21]
       ↑
   minimum to 7 (index 2)
zamiana arr[0] ↔ arr[2]
wynik: [7, 43, 89, 55, 21]
✓ posortowane: [7]

Iteracja 1 — szukamy minimum w [1..4]:

[7, 43, 89, 55, 21]
        ↑
   minimum to 21 (index 4)
zamiana arr[1] ↔ arr[4]
wynik: [7, 21, 89, 55, 43]
✓ posortowane: [7, 21]

Iteracja 2 — szukamy minimum w [2..4]:

[7, 21, 89, 55, 43]
                ↑
   minimum to 43 (index 4)
zamiana arr[2] ↔ arr[4]
wynik: [7, 21, 43, 55, 89]
✓ posortowane: [7, 21, 43]

Iteracja 3 — szukamy minimum w [3..4]:

[7, 21, 43, 55, 89]
            ↑
   minimum to 55 (index 3) — już na miejscu, zamiana z samym sobą
wynik: [7, 21, 43, 55, 89]
✓ posortowane: [7, 21, 43, 55]

Po n-1 iteracjach ostatni element jest automatycznie na właściwym miejscu. Razem: 4 iteracje zewnętrzne dla 5 elementów.

Implementacja w C#

Wersja podstawowa — int[]

public static class SelectionSort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)
        {
            // Znajdź indeks minimum w nieposortowanej części [i..n-1]
            int minIndex = i;
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }

            // Zamień tylko jeśli minimum nie jest już na właściwym miejscu
            if (minIndex != i)
                (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
        }
    }
}

Optymalizacja if (minIndex != i) unika niepotrzebnej zamiany, gdy element jest już na właściwym miejscu. Nie zmienia złożoności asymptotycznej, ale redukuje operacje w praktyce.

Wersja z logowaniem kroków — do nauki

public static void SortWithTrace(int[] arr)
{
    int n = arr.Length;

    Console.WriteLine($"Start: [{string.Join(", ", arr)}]");

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

        if (minIndex != i)
        {
            Console.WriteLine(
                $"Iter {i}: minimum={arr[minIndex]} (idx={minIndex}), " +
                $"zamieniam z idx={i} (wartość={arr[i]})");
            (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
        }
        else
        {
            Console.WriteLine($"Iter {i}: minimum już na pozycji {i}, brak zamiany");
        }

        Console.WriteLine($"       [{string.Join(", ", arr)}]");
    }
}

Analiza złożoności — skąd O(n²)

Zliczanie operacji

Zewnętrzna pętla wykonuje n-1 iteracji. W iteracji i wewnętrzna pętla wykonuje n - i - 1 porównań.

Całkowita liczba porównań:

(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2

Dla n=100: 4 950 porównań. Dla n=1 000: 499 500 porównań. Dla n=10 000: 49 995 000 porównań.

To jest O(n²) — podwojenie n czterokrotnie zwiększa czas.

Porównanie liczby zamian

To jest kluczowa różnica Selection Sort od Bubble Sort:

Selection Sort robi co najwyżej n-1 zamian — dokładnie jedną na każdą iterację zewnętrznej pętli. To czyni go optymalnym gdy zamiana elementów jest kosztowna — np. gdy elementy to duże struktury kopiowane przez wartość, lub gdy piszesz na wolne medium (np. Flash/EEPROM gdzie każdy zapis skraca żywotność).

Złożoność pamięciowa

O(1) — sortowanie w miejscu, bez dodatkowej tablicy. Jedyna dodatkowa zmienna to minIndex i temp.

Przykład z modelem domenowym — leaderboard graczy

public record PlayerScore(string Name, int Score, DateTimeOffset AchievedAt);

public static class PlayerLeaderboard
{
    // Sortowanie rosnąco po Score — Selection Sort dla małych turniejów
    public static void SortByScore(PlayerScore[] players)
    {
        int n = players.Length;

        for (int i = 0; i < n - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < n; j++)
            {
                // Porównanie po Score, przy równych — wcześniejszy wynik lepszy
                if (players[j].Score < players[minIdx].Score ||
                   (players[j].Score == players[minIdx].Score &&
                    players[j].AchievedAt < players[minIdx].AchievedAt))
                {
                    minIdx = j;
                }
            }

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

Używamy tutaj porównania złożonego: główny klucz to Score, a w przypadku remisu — starszy wynik (mniejszy AchievedAt) ma pierwszeństwo.

Stabilność — ważna właściwość, którą Selection Sort traci

Algorytm jest niestabilny — może zmieniać kolejność elementów o równych kluczach.

Przykład:

Wejście:  [A:5, B:3, C:5, D:1]  // A i C mają ten sam wynik 5
Oczekiwane (stabilne): [D:1, B:3, A:5, C:5]  // A przed C — jak w oryginale
Selection Sort może dać: [D:1, B:3, C:5, A:5]  // C przed A — zmiana kolejności!

Dlaczego? Bo w iteracji 2 szukamy minimum w [A:5, C:5] — jeśli C jest znaleziony jako minIdx i wymieniony z A, kolejność A, C się odwraca.

Dla leaderboardu to może być problem: dwa wyniki “100 punktów” mogą podskoczyć w kolejności. Jeśli stabilność jest wymagana — użyj Merge Sort lub Array.Sort z LINQ OrderBy (stabilny od .NET 4.5+).

Porównanie z sąsiadami w module algorytmów

Kluczowy wniosek: Selection Sort wyróżnia się minimalną liczbą zamian. Ale w przypadku prawie posortowanej tablicy — Insertion Sort jest szybszy (O(n) w best case). Selection Sort zawsze robi O(n²) porównań bez względu na wejście.

Unit testy

public class SelectionSortTests
{
    [Fact]
    public void Sort_ShouldProduceSortedArray()
    {
        int[] input = [89, 43, 7, 55, 21];
        SelectionSort.Sort(input);
        Assert.Equal([7, 21, 43, 55, 89], input);
    }

    [Fact]
    public void Sort_AlreadySorted_ShouldNotChange()
    {
        int[] input = [1, 2, 3, 4, 5];
        SelectionSort.Sort(input);
        Assert.Equal([1, 2, 3, 4, 5], input);
    }

    [Fact]
    public void Sort_ReverseSorted_ShouldSort()
    {
        int[] input = [5, 4, 3, 2, 1];
        SelectionSort.Sort(input);
        Assert.Equal([1, 2, 3, 4, 5], input);
    }

    [Fact]
    public void Sort_SingleElement_ShouldNotThrow()
    {
        int[] input = [42];
        SelectionSort.Sort(input);
        Assert.Equal([42], input);
    }

    [Fact]
    public void Sort_WithDuplicates_ShouldSort()
    {
        int[] input = [3, 1, 4, 1, 5, 9, 2, 6, 5];
        SelectionSort.Sort(input);
        Assert.Equal([1, 1, 2, 3, 4, 5, 5, 6, 9], input);
    }

    [Fact]
    public void Sort_Empty_ShouldNotThrow()
    {
        int[] input = [];
        SelectionSort.Sort(input); // n-1 = -1 — pętla nie wykonuje się
        Assert.Empty(input);
    }
}

Kiedy Selection Sort ma sens

Używaj Selection Sort gdy:

• Dane wejściowe mają ≤50 elementów i prostota kodu jest ważna
• Zamiana elementów jest kosztowna (duże struktury kopiowane przez wartość, zapis na trwałe medium)
• Uczysz się algorytmów — jego mechanika jest prosta do śledzenia krok po kroku

Nie używaj gdy:

• n > 100 — użyj Array.Sort() (Timsort, O(n log n))
• Tablica jest prawie posortowana — Insertion Sort jest lepszy
• Potrzebujesz stabilnego sortowania — użyj Merge Sort lub LINQ OrderBy

Podsumowanie

Selection Sort = znajdź minimum, przenieś na przód, powtórz. Złożoność zawsze O(n²) bez względu na wejście. Wyróżnia się minimalną liczbą zamian (dokładnie n-1) — czyni go użytecznym gdy operacja zamiany jest droga. Niestabilny — równe elementy mogą zmienić kolejność.

Kluczowy insight dla rozmowy rekrutacyjnej: nie wybierasz Selection Sort dla wydajności, lecz dla minimalnej liczby zamian w specyficznych warunkach.

Następny post: Selection Sort w C# — Warianty, Generyki i Granice Użyteczności — implementacja generyczna z Comparison<T>, dwukierunkowe sortowanie przez wybór, i kiedy Selection Sort przegrywa z Array.Sort.

Powiązane: porównaj z innymi prostymi sortowaniami: Bubble Sort i sortowaniem przez wstawianie.