Sortowanie przez wybieranie

1. Idea algorytmu

Sortowanie przez wybieranie (selection sort) działa w prosty sposób:

Znajdź najmniejszy element w liście
Zamień go z pierwszym elementem
Powtórz dla reszty listy (bez pierwszego elementu)

Wizualizacja:

[64, 25, 12, 22, 11]
 ↓   ↓   ↓   ↓   ↓
 Szukamy minimum → 11

[11, 25, 12, 22, 64]  ← 11 na początku
     ↓   ↓   ↓   ↓
     Szukamy minimum → 12

[11, 12, 25, 22, 64]  ← 12 na 2. miejscu
         ↓   ↓   ↓
         Szukamy minimum → 22

[11, 12, 22, 25, 64]  ← 22 na 3. miejscu
             ↓   ↓
             Szukamy minimum → 25

[11, 12, 22, 25, 64]  ← POSORTOWANE!

2. Implementacja

3. Krok po kroku z wizualizacją

Wynik:

Start: [64, 25, 12, 22, 11]

Iteracja 1:
  Szukanie minimum od indeksu 0
  Minimum: arr[4] = 11
  Zamiana: arr[0] ↔ arr[4]  (64 ↔ 11)
  Po iteracji: [11, 25, 12, 22, 64]

Iteracja 2:
  Szukanie minimum od indeksu 1
  Minimum: arr[2] = 12
  Zamiana: arr[1] ↔ arr[2]  (25 ↔ 12)
  Po iteracji: [11, 12, 25, 22, 64]

...

4. Złożoność czasowa: O(n²)

Wszystkie przypadki: O(n²)!

Wzór: n(n-1)/2 = O(n²)

Najlepszy = Najgorszy = Średni = O(n²)

Nawet dla już posortowanej listy – zawsze O(n²)!

5. Złożoność pamięciowa: O(1)

Selection sort jest in-place!

6. Stabilność: NIE ❌

Selection sort nie jest stabilny – może zmienić kolejność równych elementów.

Przykład:

Dlaczego? Zamiany na długim dystansie niszczą stabilność.

7. Liczba zamian: O(n)

Kluczowa zaleta: Selection sort wykonuje maksymalnie n-1 zamian!

Porównanie: - Bubble sort: O(n²) zamian - Selection sort: O(n) zamian ← Lepsze!

8. Selection sort vs Bubble sort

Aspekt	Selection Sort	Bubble Sort
Złożoność czasowa	O(n²)	O(n²)
Złożoność pamięciowa	O(1)	O(1)
Stabilność	❌ NIE	✅ TAK
Liczba zamian	O(n)	O(n²)
Adaptywność	❌ NIE	✅ TAK (z opt)

Kiedy selection > bubble: - Gdy zamiany są kosztowne (np. duże obiekty)

Kiedy bubble > selection: - Dane prawie posortowane (z optymalizacją)

9. Wariant: Selection sort malejąco

10. Zastosowanie: K najmniejszych elementów

Złożoność: O(k × n) zamiast O(n log n) dla pełnego sortowania!

11. Benchmark

Selection i Bubble są podobnie wolne (oba O(n²)).

12. Podsumowanie

Selection Sort:

Złożoność czasowa: O(n²) zawsze (NIE adaptywny!)
Złożoność pamięciowa: O(1) in-place
Stabilny: NIE ❌
Liczba zamian: O(n) – niewiele!

Zalety: - Prosty w implementacji - In-place (O(1) pamięci) - Mało zamian O(n) – dobre dla kosztownych zamian

Wady: - O(n²) zawsze – nawet dla posortowanych - Niestabilny - Nie adaptywny

vs Bubble Sort: - Mniej zamian (O(n) vs O(n²)) - Nie adaptywny (bubble tak z optymalizacją) - Podobna wydajność ogólnie

Kiedy używać:

✅ Gdy zamiany są kosztowne (duże obiekty w pamięci) ✅ Gdy potrzebujesz k najmniejszych (zamiast pełnego sortowania) ✅ Małe dane + prostota

❌ W większości przypadków – użyj quick/merge sort!

Co dalej warto poznać:

Insertion Sort (lepszy dla małych/prawie posortowanych)
Heap Sort (podobna idea, ale O(n log n))
Quick Sort (praktyczny wybór)