Algorytm sortowania przez wybieranie

Sortowanie przez wybieranie (ang. selection sort) to kolejny podstawowy algorytm sortujący omawiany na maturze rozszerzonej z informatyki, często zestawiany z sortowaniem bąbelkowym w celu porównania efektywności różnych podejść do tego samego problemu. Jego zasada polega na iteracyjnym wyszukiwaniu najmniejszego elementu w nieposortowanej części tablicy i zamianie go z pierwszym elementem tej części.

Lekcja szczegółowo analizuje przebieg algorytmu na konkretnych przykładach — na przykład dla tablicy $[5,2,9,1]$ uczeń oblicza, ile porównań potrzeba, by znaleźć minimum w pierwszej fazie ($n-1$ porównań), a dla tablicy $[4,3,2,1]$ śledzi krok po kroku, jak w kolejnych iteracjach algorytm zawęża obszar poszukiwań do coraz mniejszej podtablicy.

Kluczowym tematem jest porównanie selection sort z sortowaniem bąbelkowym: selection sort wykonuje zawsze dokładnie $\frac{n(n-1)}{2}$ porównań niezależnie od danych wejściowych, ale za to znacznie mniej operacji zamiany (maksymalnie $n-1$) niż sortowanie bąbelkowe. W przeciwieństwie do bąbelkowego, selection sort nie posiada mechanizmu wczesnego zakończenia — nawet jeśli tablica jest już posortowana, algorytm i tak wykona pełną liczbę porównań.

Materiał obejmuje też złożoność obliczeniową — $O(n^2)$ zarówno w przypadku najlepszym, jak i najgorszym (co odróżnia go od sortowania bąbelkowego, które w najlepszym przypadku osiąga $O(n)$) — oraz kwestię stabilności: standardowa implementacja selection sort NIE jest stabilna, ponieważ bezpośrednia zamiana elementów może zmienić względną kolejność elementów o tej samej wartości.

Uczeń poznaje też, że liczba wykonanych zamian zależy od danych wejściowych — jeśli minimum w danej iteracji już znajduje się na właściwej pozycji, zamiana nie jest wykonywana, mimo że porównania nadal się odbywają. To subtelna różnica między "liczbą porównań" (zawsze stałą dla danego $n$) a "liczbą zamian" (zmienną).

Ten zestaw pytań i fiszek pomaga utrwalić mechanikę algorytmu, umiejętność ręcznego śledzenia jego kroków oraz świadome porównywanie różnych algorytmów sortujących pod kątem liczby operacji i złożoności — kompetencję kluczową na egzaminie maturalnym z informatyki.

• Uczeń opisuje zasadę działania algorytmu sortowania przez wybieranie (selection sort)
• Uczeń oblicza liczbę porównań potrzebnych do znalezienia minimum w danej iteracji
• Uczeń porównuje selection sort z sortowaniem bąbelkowym pod względem liczby zamian i możliwości wczesnego zakończenia
• Uczeń wie, że złożoność czasowa selection sort wynosi O(n²) niezależnie od przypadku
• Uczeń rozumie, dlaczego standardowa implementacja selection sort nie jest stabilna
• Uczeń rozróżnia liczbę porównań (stałą) od liczby zamian (zależnej od danych)
• Uczeń potrafi ręcznie prześledzić kolejne iteracje algorytmu dla konkretnej tablicy liczb

Materiał tematyczny (bez dokumentu źródłowego): algorytm sortowania przez wybieranie (selection sort) — zasada działania, kolejne kroki sortowania przykładowego ciągu liczb, liczba porównań, złożoność obliczeniowa, porównanie z sortowaniem bąbelkowym, zgodnie z zakresem matury rozszerzonej z informatyki.