Sortowanie przez wybór i przez wstawianie
Informatyka, klasa 8 · Algorytmy
Najważniejsze w skrócie
Sortowanie przez wybór (selection sort) w każdym kroku szuka najmniejszego elementu w nieposortowanej części listy i zamienia go z pierwszym elementem tej części. Po pierwszym przejściu minimum stoi na początku, po drugim — dwa najmniejsze elementy, i tak dalej. Dla listy [5, 3, 8, 1] kolejne stany to [1, 3, 8, 5], [1, 3, 8, 5] i [1, 3, 5, 8].
Sortowanie przez wstawianie (insertion sort) działa jak układanie kart w ręce: bierzemy kolejny element i przesuwamy go w lewo, aż trafi za mniejszy od siebie. Dla [5, 3, 8, 1] dostajemy kolejno [3, 5, 8, 1], [3, 5, 8, 1] i [1, 3, 5, 8]. Gdy lista jest prawie posortowana, ta metoda kończy pracę bardzo szybko.
Obie metody wykonują w najgorszym razie około n² / 2 porównań — dla 4 elementów to 6, ale dla 1000 elementów już prawie pół miliona. Dlatego w prawdziwych programach w Pythonie używamy sorted(lista) albo lista.sort(), które korzystają z szybkiego algorytmu Timsort. Proste metody uczymy się po to, by zrozumieć, jak komputer porządkuje dane.
Ważne daty
- wybór — znajdź minimum reszty i zamień z pierwszym nieposortowanym
- wstawianie — weź kolejny element i przesuń go w lewo na właściwe miejsce
- n·(n−1)/2 — liczba porównań w sortowaniu przez wybór (dla n = 4 to 6)
- sorted(t) — zwraca nową, posortowaną listę; t zostaje bez zmian
- t.sort() — sortuje listę t w miejscu i zwraca None
Ważne postacie
- Tim Peters — autor algorytmu Timsort, którego używa sorted() w Pythonie
- Donald Knuth — opisał algorytmy sortowania w „Sztuce programowania”
- Minimum — element wybierany w każdym przejściu sortowania przez wybór
- Karty w ręce — obraz, który najlepiej tłumaczy sortowanie przez wstawianie
Pojęcia
- Na czym polega sortowanie przez wybór?
- W każdym przejściu wybieramy najmniejszy element z nieposortowanej części i stawiamy go na jej początku.
- Na czym polega sortowanie przez wstawianie?
- Kolejny element wstawiamy na właściwe miejsce w już uporządkowanej części listy, przesuwając większe w prawo.
- Jak wygląda lista [5, 3, 8, 1] po pierwszym przejściu sortowania przez wybór?
- [1, 3, 8, 5] — minimum 1 zamieniło się miejscem z 5.
- Jak wygląda lista [5, 3, 8, 1] po pierwszym kroku sortowania przez wstawianie?
- [3, 5, 8, 1] — trójka trafiła przed piątkę.
- Ile porównań wykona sortowanie przez wybór dla 4 elementów?
- 6, bo 3 + 2 + 1 = 6.
- Ile porównań wykona sortowanie przez wybór dla 10 elementów?
- 45, bo 9 + 8 + … + 1 = 45.
- Ile zamian wykona co najwyżej sortowanie przez wybór dla n elementów?
- n − 1 — po jednej w każdym przejściu.
- Kiedy sortowanie przez wstawianie działa najszybciej?
- Gdy lista jest już posortowana lub prawie posortowana — wystarczy około n porównań.
- Kiedy sortowanie przez wstawianie działa najwolniej?
- Gdy lista jest posortowana odwrotnie — każdy element trzeba przesunąć na sam początek.
- Czym różni się sorted(t) od t.sort()?
- sorted(t) tworzy nową listę, a t.sort() zmienia samą listę t i zwraca None.
- Jak w Pythonie posortować listę malejąco?
- sorted(t, reverse=True) albo t.sort(reverse=True).
- Jakiego algorytmu używa sorted() w Pythonie?
- Timsortu — połączenia sortowania przez scalanie i przez wstawianie.
Sprawdź się
1. Co robi sortowanie przez wybór w każdym przejściu?
- Zamienia ze sobą każdą parę sąsiednich elementów
- Dzieli listę na dwie połowy i sortuje każdą osobno
- Szuka minimum reszty i stawia je na początku reszty
- Wstawia kolejny element w posortowaną część listy
Pokaż odpowiedź
C. Szuka minimum reszty i stawia je na początku reszty — Wybieramy najmniejszy element z nieposortowanej części i zamieniamy go z jej pierwszym elementem. Zamiana sąsiadów to sortowanie bąbelkowe, a wstawianie to inna metoda.
2. Ile porównań wykona sortowanie przez wybór dla listy 5 elementów?
- 5
- 25
- 10
- 20
Pokaż odpowiedź
C. 10 — W kolejnych przejściach porównujemy 4, 3, 2 i 1 raz, co razem daje 10. Wzór n·(n−1)/2 dla n = 5 daje ten sam wynik.
3. Dlaczego sortowanie przez wybór ma złożoność kwadratową?
- Bo w każdym przejściu przegląda całą resztę listy
- Bo wykonuje dokładnie tyle zamian, ile jest elementów
- Bo działa tylko na liczbach całkowitych
- Bo używa dwóch list zamiast jednej
Pokaż odpowiedź
A. Bo w każdym przejściu przegląda całą resztę listy — Zewnętrzna pętla wykonuje się około n razy, a wewnętrzna za każdym razem przegląda resztę listy, więc porównań jest około n²/2.
4. Jak w Pythonie otrzymać listę t posortowaną malejąco?
- sorted(t, descending=True)
- sorted(t, reverse=True)
- t.sort(-1)
- reversed(t)
Pokaż odpowiedź
B. sorted(t, reverse=True) — Parametr reverse=True odwraca kolejność sortowania. Samo reversed(t) tylko czyta listę od końca, niczego nie porządkując.
5. Jaki będzie stan listy [4, 1, 3, 2] po dwóch przejściach sortowania przez wybór?
- [1, 4, 3, 2]
- [1, 2, 4, 3]
- [1, 2, 3, 4]
- [1, 3, 4, 2]
Pokaż odpowiedź
C. [1, 2, 3, 4] — Pierwsze przejście zamienia 4 z 1 i daje [1, 4, 3, 2]. Drugie znajduje w reszcie minimum 2 i zamienia je z czwórką, więc trójka przypadkiem od razu trafia na swoje miejsce.
Więcej pytań — razem 50 fiszek, pytań i zdań prawda/fałsz — czeka w ćwiczeniach.
▶ Ćwicz ten temat fiszki, quiz i prawda/fałsz — z wynikiem i powtórkami