Wybiera minimum z nieposortowanej części i umieszcza je na właściwej pozycji. O(n²).
Sortowanie przez wybór układa liczby, szukając za każdym razem najmniejszej. Najpierw znajdujesz najmniejszą liczbę w całej tablicy i stawiasz ją na początku. Potem szukasz najmniejszej z tego, co zostało, i stawiasz ją na drugim miejscu. I tak dalej, aż wszystko będzie po kolei.
Ważna cecha: w każdym przejściu robisz tylko jedną zamianę – dopiero gdy już wiesz, gdzie leży najmniejsza liczba. Dlatego zamian jest bardzo mało, nawet jeśli porównań dużo.
Kiedy się przydaje: przy małych tablicach albo tam, gdzie zależy nam, żeby jak najrzadziej przestawiać elementy (bo samo przestawianie bywa kosztowne).
Na maturze: zwykle chodzi o policzenie, ile jest porównań, a ile zamian – i właśnie tu widać, że zamian jest mało.
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja sortuj_przez_wybor(T, n): dla i od 0 do n - 2: min_idx ← i // szukamy najmniejszego w niesortowanej części dla j od i + 1 do n - 1: jeżeli T[j] < T[min_idx]: min_idx ← j // zamieniamy znaleziony minimalny z elementem na pozycji i pomocnicza ← T[i] T[i] ← T[min_idx] T[min_idx] ← pomocnicza zwróć T
def sortowanie_przez_wybor(tablica):
n = len(tablica)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if tablica[j] < tablica[min_idx]:
min_idx = j
# zamiana elementów
tablica[i], tablica[min_idx] = tablica[min_idx], tablica[i]
return tablica
# Przykład użycia
dane = [64, 25, 12, 22, 11]
print(sortowanie_przez_wybor(dane))
# Wynik: [11, 12, 22, 25, 64]#include <vector>
#include <iostream>
using namespace std;
void sortowanie_przez_wybor(vector<int>& t) {
int n = t.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (t[j] < t[min_idx]) min_idx = j;
}
swap(t[i], t[min_idx]);
}
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11};
sortowanie_przez_wybor(dane);
for (int x : dane) cout << x << " ";
// Wynik: 11 12 22 25 64
}Nie – to algorytm niestabilny. Zamiana odbywa się od razu z elementem znalezionym jako minimum, bez sprawdzania, czy nie przeskakuje przy tym nad innym elementem o tej samej wartości, więc ich pierwotna kolejność może się zmienić.
O(n²) – zarówno w najgorszym, średnim, jak i najlepszym przypadku. Liczba porównań (n(n-1)/2) nie zależy od tego, jak ułożone są dane wejściowe – algorytm zawsze przeszukuje całą nieposortowaną część tablicy w poszukiwaniu minimum.
Nie – sortuje w miejscu i potrzebuje tylko O(1) dodatkowej pamięci, czyli jednej zmiennej pomocniczej do zamiany dwóch elementów.
Przy małych zbiorach danych, w celach edukacyjnych albo gdy zależy nam na jak najmniejszej liczbie zamian – wykonuje ich co najwyżej n - 1, co ma znaczenie, gdy sama operacja zamiany jest kosztowna.
Sortowanie przez wybór szuka minimum w nieposortowanej części i przenosi je na właściwe miejsce jedną zamianą na przebieg, więc zamian jest mało. Sortowanie bąbelkowe zamienia natomiast sąsiednie elementy wielokrotnie w trakcie każdego przebiegu, więc zamian bywa znacznie więcej.
Przeanalizuj sortowanie przez wybór i wpisz wyniki, potem kliknij Sprawdź.
Sortujemy rosnąco tablicę [5, 3, 8, 1, 2] (5 elementów). Algorytm wykonuje przebiegi (pętla zewnętrzna), a w pierwszym przebiegu (szukanie minimum całej tablicy) robi porównania. Znalezionym minimum jest liczba , więc po pierwszej zamianie tablica wygląda tak: .
Łączna liczba porównań przy sortowaniu tej 5-elementowej tablicy to , a zamian jest co najwyżej .
Uzupełnij tabelę (n to liczba elementów):
| Liczba elementów n | Łączna liczba porównań |
|---|---|
| 4 | |
| 6 | |
| 8 |
Złożoność czasowa sortowania przez wybór w każdym przypadku to , a pamięciowa to .
O(n²)O(n²)O(1)Czasowa to zawsze O(n²) – niezależnie od przypadku (najgorszy, średni, najlepszy). Wynika to z dwóch zagnieżdżonych pętli: zewnętrzna wybiera kolejno pozycję do uzupełnienia (n przebiegów), a wewnętrzna przy każdym z nich przeszukuje całą pozostałą, nieposortowaną część tablicy w poszukiwaniu minimum (znowu do n porównań). O(n) razy O(n) daje O(n²) bez względu na to, czy dane wejściowe są już posortowane, czy ułożone od tyłu – liczba porównań jest stała i wynosi n(n-1)/2.
Zamian jest natomiast mało – co najwyżej n - 1. W przeciwieństwie do porównań, zamianę wykonujemy tylko raz na przebieg, dopiero po znalezieniu minimum, a nie przy każdym porównaniu. To mniej niż w większości klasycznych algorytmów sortujących – mniej zamian wykonuje tylko rzadko spotykane sortowanie cykliczne.
Pamięć O(1). Sortujemy w miejscu, w obrębie tej samej tablicy – potrzebna jest tylko jedna zmienna pomocnicza do zamiany dwóch elementów.
Dla większych zbiorów danych O(n²) wyraźnie przegrywa z algorytmami działającymi w czasie O(n log n), jak sortowanie szybkie czy sortowanie przez scalanie – różnica robi się odczuwalna już przy tablicach liczących tysiące elementów.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: