Wybiera minimum z nieposortowanej części i umieszcza je na właściwej pozycji. O(n²).
Sortowanie przez wybór to prosty algorytm działający według intuicyjnej zasady: znajdujemy najmniejszy element w tablicy i zamieniamy go z elementem pierwszym. Następnie szukamy najmniejszego w pozostałej części (od drugiego elementu) i zamieniamy z drugim. Powtarzamy do końca tablicy.
Uwaga: sortowanie przez wybór jest niestabilne – może zmienić względną kolejność elementów o tej samej wartości. Przy większych zbiorach danych przegrywa też czasowo z szybszymi algorytmami, jak sortowanie szybkie czy sortowanie przez scalanie (patrz sekcja „Złożoność").
Zalety: to często pierwszy algorytm sortujący, jaki się poznaje – jest prosty do zrozumienia i samodzielnie zaimplementować. Wykonuje też mało zamian, więc dobrze sprawdza się tam, gdzie sam zapis do pamięci jest operacją kosztowną (dokładne liczby – patrz sekcja „Złożoność").
Zastosowania: sortowanie przez wybór ma sens przy małych tablicach, gdzie narzut bardziej złożonych algorytmów się nie opłaca, oraz wszędzie tam, gdzie liczy się przede wszystkim liczba zapisów do pamięci, a nie liczba porównań.
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 (in-place) 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.
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.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: