Sortowanie przez wybieranie w Pythonie i C++

Sortowanie przez wybieranie (ang. selection sort) to zwykle pierwszy algorytm sortowania, jaki poznaje się w szkole. Robi dokładnie to, co zrobiłby człowiek z kartkami z liczbami: znajduje najmniejszą, odkłada ją na początek, potem szuka najmniejszej z pozostałych i tak dalej. Algorytm jest krótki, łatwy do zapamiętania i dobrze pokazuje, czym są pętle zagnieżdżone.

Na tej stronie znajdziesz ideę algorytmu, kod w Pythonie i C++, tabelę przebiegów, liczenie porównań i zamian oraz porównanie z dwoma innymi prostymi sortowaniami. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź sortowanie przez wybieranie krok po kroku

Idea: wybierz minimum i postaw je na początku

Lista dzieli się na dwie części: posortowaną z lewej (na początku pustą) i nieposortowaną z prawej. Jeden przebieg wygląda tak:

1. Zakładamy, że najmniejszy element części nieposortowanej stoi na jej początku (indeks i), i zapamiętujemy ten indeks w zmiennej min_i.
2. Przeglądamy resztę listy. Gdy trafimy na mniejszy element, zapamiętujemy jego indeks jako nowe min_i.
3. Po przejrzeniu reszty zamieniamy element i z elementem min_i.

Po pierwszym przebiegu na pozycji 0 stoi najmniejszy element całej listy, po drugim na pozycji 1 drugi najmniejszy itd. Ostatni element nie wymaga osobnego przebiegu: gdy n - 1 elementów stoi na swoich miejscach, ostatni też musi stać na swoim. Dlatego zewnętrzna pętla wykonuje się n - 1 razy.

Sortowanie przez wybieranie w Pythonie

dane = [29, 10, 14, 37, 13]
n = len(dane)
for i in range(n - 1):
    min_i = i
    for j in range(i + 1, n):
        if dane[j] < dane[min_i]:
            min_i = j
    dane[i], dane[min_i] = dane[min_i], dane[i]
    print("przebieg", i + 1, dane)

przebieg 1 [10, 29, 14, 37, 13]
przebieg 2 [10, 13, 14, 37, 29]
przebieg 3 [10, 13, 14, 37, 29]
przebieg 4 [10, 13, 14, 29, 37]

Zewnętrzna pętla (i) wyznacza miejsce, na które trafi kolejne minimum. Wewnętrzna (j) szuka minimum w części nieposortowanej, czyli od i + 1 do końca. Zamiana dane[i], dane[min_i] = dane[min_i], dane[i] to w Pythonie jedno przypisanie krotki: prawa strona liczy się w całości, zanim cokolwiek zostanie nadpisane.

Tabela przebiegów

Prześledźmy, co dzieje się w każdym przebiegu dla listy [29, 10, 14, 37, 13]:

W trzecim przebiegu minimum (14) stało już na swoim miejscu, więc min_i równa się i i “zamiana” niczego nie zmienia. Lista nie zmieniła się, ale algorytm i tak przejrzał całą resztę: sortowanie przez wybieranie nie wie, że dane są już ułożone.

Krokuj ten przykład i patrz, jak wędruje min_i

Ile porównań, ile zamian?

Policzmy pracę algorytmu licznikami. Funkcja zwraca parę: liczbę porównań i liczbę zamian (zamieniamy tylko wtedy, gdy minimum nie stało na miejscu):

def sortuj(dane):
    porownania = 0
    zamiany = 0
    n = len(dane)
    for i in range(n - 1):
        min_i = i
        for j in range(i + 1, n):
            porownania += 1
            if dane[j] < dane[min_i]:
                min_i = j
        if min_i != i:
            dane[i], dane[min_i] = dane[min_i], dane[i]
            zamiany += 1
    return porownania, zamiany


print(sortuj([5, 4, 3, 2, 1]))
print(sortuj([1, 2, 3, 4, 5]))

(10, 2)
(10, 0)

Porównań jest zawsze tyle samo: (n - 1) + (n - 2) + … + 1 = n(n-1)/2, czyli 10 dla pięciu elementów, niezależnie od tego, czy lista jest odwrócona, czy już posortowana. Zamian jest najwyżej n - 1. Dla odwróconej listy [5, 4, 3, 2, 1] wystarczyły dwie, bo jedna zamiana (5 z 1) ustawia od razu dwa elementy.

Krokuj licznik porównań i zamian

Sortowanie przez wybieranie w C++

W C++ tablicę przekazujemy do funkcji razem z jej rozmiarem, a zamianę piszemy ręcznie przez zmienną pomocniczą:

#include <iostream>
using namespace std;

void sortuj(int t[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int min_i = i;
    for (int j = i + 1; j < n; j++) {
      if (t[j] < t[min_i]) {
        min_i = j;
      }
    }
    int tmp = t[i];
    t[i] = t[min_i];
    t[min_i] = tmp;
  }
}

int main() {
  int t[5] = {29, 10, 14, 37, 13};
  sortuj(t, 5);
  for (int i = 0; i < 5; i++) {
    cout << t[i] << endl;
  }
  return 0;
}

10
13
14
29
37

Sortowanie malejąco wymaga zmiany jednego znaku: szukamy maksimum zamiast minimum, więc porównanie < zamieniamy na >. Poniżej wersja, która wypisuje tablicę po każdym przebiegu:

#include <iostream>
using namespace std;

void wypisz(int t[], int n) {
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      cout << " ";
    }
    cout << t[i];
  }
  cout << endl;
}

int main() {
  int t[5] = {29, 10, 14, 37, 13};
  int n = 5;
  for (int i = 0; i < n - 1; i++) {
    int max_i = i;
    for (int j = i + 1; j < n; j++) {
      if (t[j] > t[max_i]) {
        max_i = j;
      }
    }
    int tmp = t[i];
    t[i] = t[max_i];
    t[max_i] = tmp;
    wypisz(t, n);
  }
  return 0;
}

37 10 14 29 13
37 29 14 10 13
37 29 14 10 13
37 29 14 13 10

Złożoność i porównanie z innymi sortowaniami

Sortowanie przez wybieranie ma złożoność czasową O(n²) i pamięciową O(1) (sortuje w miejscu). Dwa pozostałe proste sortowania, które pojawiają się w szkole, mają tę samą złożoność w najgorszym przypadku, ale zachowują się inaczej. Tabela pokazuje liczbę porównań i zamian (dla wstawiania: przesunięć) dla list 8-elementowych, przy czym sortowanie bąbelkowe ma flagę kończącą pracę, gdy w przebiegu nie było zamian:

Wniosek: przez wybieranie zawsze porównuje 28 razy, ale zamienia najmniej. Przydaje się więc tam, gdzie przestawienie elementu jest drogie. Dla danych prawie posortowanych lepsze są sortowanie bąbelkowe z flagą i sortowanie przez wstawianie, które wtedy działają prawie liniowo.

W praktyce w Pythonie używa się sorted() i list.sort(), a w C++ funkcji sort z biblioteki standardowej. Na sprawdzianie i w zadaniach maturalnych oczekuje się jednak, że uczeń umie zapisać algorytm sam.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Sortowanie przez wybieranie

Specyfikacja. Dane: tablica T[1..n]. Wynik: tablica T posortowana rosnąco.

Lista kroków:

1. Wczytaj n i tablicę T[1..n]. Ustaw i = 1.
2. Jeśli i = n, wypisz T i zakończ.
3. Znajdź pozycję m najmniejszego z elementów T[i], T[i + 1], …, T[n].
4. Zamień miejscami T[i] i T[m]. Zwiększ i o 1 i wróć do kroku 2.

Pseudokod:

wczytaj n, T
dla i = 1, 2, ..., n - 1 wykonuj
  m ← i
  dla j = i + 1, i + 2, ..., n wykonuj
    jeżeli T[j] < T[m] to
      m ← j
  zamień T[i] z T[m]
wypisz T

Schemat blokowy:

Drzewo decyzyjne sortowania trzech liczb. Drzewo pokazuje wszystkie możliwe przebiegi algorytmu dla trzech różnych liczb a, b, c ułożonych w tablicy w tej kolejności. Każdy węzeł to porównanie wykonane przez algorytm, a liść to ustalona kolejność od najmniejszej liczby. Algorytm wykonuje 3 porównania. Węzeł z jedną gałęzią to porównanie, którego wynik wynika już z wcześniejszych porównań: algorytm i tak je wykonuje.

Najczęstsze błędy

• Zamiana wewnątrz pętli j. Jeśli zamieniasz od razu przy każdym znalezionym mniejszym elemencie, wychodzi inne sortowanie, z dużo większą liczbą zamian. Zamiana należy do pętli i, po zakończeniu pętli j.
• Porównanie z dane[i] zamiast z dane[min_i]. Warunek dane[j] < dane[i] znajduje ostatni element mniejszy od dane[i], a nie najmniejszy. Porównujemy z dotychczasowym minimum.
• Zły zakres pętli wewnętrznej. Pętla j zaczyna się od i + 1, nie od 0: początek listy jest już posortowany i nie wolno go ruszać.
• Zamiana w C++ bez zmiennej pomocniczej. t[i] = t[min_i]; t[min_i] = t[i]; gubi jedną wartość. Potrzebna jest zmienna tmp.
• Zapomniane min_i = i na początku przebiegu. Bez tego minimum z poprzedniego przebiegu “przechodzi” do następnego.

Ćwicz w przeglądarce

W temacie “Sortowanie przez wybieranie” kursu Algorytmy z podstawy programowej czekają dwa przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• sortowanie przez wybieranie rosnąco (własna funkcja, bez sort() i sorted()),
• sortowanie malejąco przez wybieranie maksimum,
• sortowanie imion alfabetycznie (napisy porównuje się tak samo jak liczby).

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości i, j, min_i i całej listy. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Dalsze algorytmy z tego samego kursu: algorytm Euklidesa oraz wyszukiwanie liniowe i binarne, które działa właśnie na posortowanej liście. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Sortowanie przez wybieranie to dobry moment, żeby pokazać uczniom pętle zagnieżdżone i policzyć pracę algorytmu: licznik porównań daje zawsze ten sam wynik, a licznik zamian zależy od danych. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.