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.

▶ Ćwicz ten temat fiszki, quiz i prawda/fałsz — z wynikiem i powtórkami

Ważne daty

Ważne postacie

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?

  1. Zamienia ze sobą każdą parę sąsiednich elementów
  2. Dzieli listę na dwie połowy i sortuje każdą osobno
  3. Szuka minimum reszty i stawia je na początku reszty
  4. 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?

  1. 5
  2. 25
  3. 10
  4. 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ą?

  1. Bo w każdym przejściu przegląda całą resztę listy
  2. Bo wykonuje dokładnie tyle zamian, ile jest elementów
  3. Bo działa tylko na liczbach całkowitych
  4. 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?

  1. sorted(t, descending=True)
  2. sorted(t, reverse=True)
  3. t.sort(-1)
  4. 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. [1, 4, 3, 2]
  2. [1, 2, 4, 3]
  3. [1, 2, 3, 4]
  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