Bąbelkowe i przez wstawianie

Po co komu porządek?

Wracamy do poprzedniej lekcji, tej o wyszukiwaniu sekwencyjnym i binarnym.

1. Wyszukiwanie sekwencyjne sprawdza komórki po kolei, od pierwszej. Co robi zamiast tego wyszukiwanie binarne?
2. Wyszukiwanie binarne działa tylko wtedy, gdy zbiór spełnia jeden warunek. Jaki to warunek?
3. Uporządkowanie danych kosztuje czas. Dlaczego mimo to często się opłaca?

Porównaj sąsiadów i zamień

Porządkowanie (sortowanie) to problem, dla którego opisano co najmniej kilkanaście algorytmów. Żaden z nich nie jest najszybszy w każdej sytuacji. Zaczynamy od najprostszego.

Sortowanie bąbelkowe (ang. bubble sort) porównuje parę sąsiednich elementów, zaczynając od pierwszej pary na liście, i zamienia je miejscami, gdy stoją w niewłaściwej kolejności. Taka zamiana sąsiadów to operacja prostej zamiany, dlatego metodę nazywa się też sortowaniem przez prostą zamianę.

Ciekawostka: sortowanie da się zatańczyć. Na kanale AlgoRythmics w serwisie YouTube węgierski zespół folkowy pokazuje algorytmy w tańcu, na przykład w filmie „Bubble-sort with Hungarian (Csángó) folk dance”.

Pięć liczb, cztery etapy

Porządkujemy listę 6, 4, 9, 1, 5 niemalejąco, czyli tak, żeby każda kolejna liczba była większa od poprzedniej albo jej równa. Pierwszy etap ustawia największą liczbę na ostatniej pozycji. W drugim etapie pomijamy już ostatni element, w trzecim dwa ostatnie, w czwartym trzy.

Dwie pętle, jedna w drugiej

1. def bubble_sort(A):
2.     n = len(A)
3.     for i in range(1, n):
4.         for j in range(0, n-i):
5.             if A[j] > A[j+1]:
6.                 A[j], A[j+1] = A[j+1], A[j]

Pętle zagnieżdżone (ang. nested loops) to pętle umieszczone wewnątrz innych pętli. Zewnętrzna liczy etapy i wykonuje się n-1 razy, wewnętrzna robi porównania w jednym etapie. Każdy etap ustawia jedną liczbę na docelowym miejscu, więc w następnym etapie porównań jest o jedno mniej.

Jak zamienić dwie wartości?

Dwóch wartości nie da się zamienić wprost: jeśli od razu wpiszemy 4 do A[j], to szóstka przepadnie. Dlatego najpierw chowamy jedną z nich w zmiennej pomocniczej.

W linii 6. kodu Python robi to samo krócej: A[j], A[j+1] = A[j+1], A[j]. Po prawej stronie znaku równości powstaje krotka (ang. tuple), czyli odpowiednik listy, którego nie da się zmieniać. Python zapamiętuje w niej obie wartości i dopiero potem wpisuje je na zamienione miejsca. Rada z podręcznika: żeby porządkować nierosnąco, zmieńcie w warunku znak „>” na „<”.

Jak układacie karty w ręku?

Sortowanie przez wstawianie (ang. insertion sort) przegląda kolejne elementy listy od lewej i przenosi je w odpowiednie miejsce uporządkowanego już fragmentu po lewej stronie. Dokładnie tak układa się karty do gry: kartę podniesioną ze stołu wsuwacie między te, które już macie ułożone.

Funkcja insertion_sort

1. def insertion_sort(A):
2.     n = len(A)
3.     for i in range(1, n):
4.         temp = A[i]
5.         j = i - 1
6.         while j >= 0 and A[j] > temp:
7.             A[j+1] = A[j]
8.             j -= 1
9.         A[j+1] = temp

Oba algorytmy sortują w miejscu: nie budują drugiej listy na wynik.

Ćwiczenie: sortujesz ręcznie

Etap | Lista po etapie | Por. | Zam.
  1  |                 |      |
  2  |                 |      |
  3  |                 |      |
  4  |                 |      |
  5  |                 |      |
Razem|                 |      |

Dla chętnych (dom): zapisz funkcję bubble_sort ze slajdu 5 w pliku sorting.py i uruchom ją na własnej liście.

Gdzie to wróci po szkole?

To ostatnia lekcja rozdziału o algorytmice. Podręcznik zamyka go czterema scenariuszami zawodowymi.

• Inżynier geodeta. Na pierwszym roku politechniki masz zajęcia z programowania. Znasz ze szkoły konstrukcje programistyczne, typy danych i proste struktury danych, więc rozumiesz omawiane algorytmy, choć język jest inny.
• Inżynier pożarnictwa. Piszesz instrukcje na wypadek pożaru w biurowcu. Muszą być precyzyjne, więc zapisujesz je jako listę kroków, znaną Ci z lekcji programowania.
• Staż w kancelarii adwokackiej. Akta nie są posegregowane. W uporządkowanym zbiorze łatwiej wyszukiwać, więc sortujesz je: najpierw chronologicznie, potem alfabetycznie.
• Firma meblarska. Na szkoleniu z systemu ze sztuczną inteligencją pokazują model sztucznego neuronu z kodem źródłowym. Do zrozumienia go wystarcza wiedza o instrukcji warunkowej i pętlach.

Trzy pytania na koniec

1. Na czym polega operacja prostej zamiany i dlaczego sortowanie bąbelkowe bierze od niej drugą nazwę?
2. Skąd w funkcji bubble_sort biorą się dwie pętle, jedna w drugiej, i dlaczego wewnętrzna robi w każdym kolejnym etapie o jedno porównanie mniej?
3. Po co sortowaniu przez wstawianie zmienna pomocnicza temp? Co stałoby się bez niej?

A jak to wygląda w produkcji?