Porządkujemy dane i szukamy

Największa liczba i wartownik

Wracamy do programu „Najdłuższy skok” z poprzedniej lekcji.

1. Program wczytuje kolejne długości skoków. Po czym poznaje, że dane się skończyły?
2. Zmienna biggest zaczyna od zera. Co się z nią dzieje po wczytaniu każdej liczby?
3. Do czego służyła tabela śledzenia, którą wypełnialiście na kartce?

Sortowanie to ustawianie według kryterium

Sortowanie danych, zwane też porządkowaniem danych, to ustawianie danych w zadanej kolejności, według określonego kryterium. Tak samo działa segregator w szafie: same kartki się nie zmieniają, zmienia się ich kolejność.

Według czego porządkujemy?

Kryterium wybiera człowiek: w pływaniu wygrywa najkrótszy czas, więc tam porządek jest odwrotny niż w sumie punktów.

Kod pocztowy i numer domu

W obu przykładach numer nie jest przypadkowy: koduje położenie. Dlatego list trafia do właściwej placówki, a nowy listonosz znajduje dom, którego nigdy wcześniej nie widział.

Gdzie komputer porządkuje dane?

Sortowanie to jedna z operacji najczęściej wykonywanych przez komputery.

• Lista plików w katalogu. Zanim system operacyjny pokaże zawartość katalogu, sortuje pliki według wybranego kryterium.
• Arkusz kalkulacyjny i baza danych. Sortowanie ułatwia czytanie tabeli i nadaje danym znaczenie.
• Wyszukiwarki internetowe. Zasoby na serwerach muszą być zindeksowane, żeby wynik pojawił się szybko.
• Grafika komputerowa. Obiekty w grze albo w symulatorze lotu układa się według odległości od obserwatora, żeby wyświetlić je w dobrej kolejności.

Sortowanie przydaje się też przy usuwaniu duplikatów, sprawdzaniu, czy wszystkie wartości są różne, i przy szukaniu dwóch wartości o najmniejszej różnicy.

Znasz adres czy szukasz po kolei?

Dane leżą w pamięci operacyjnej (RAM, ang. random access memory, pamięć o dostępie swobodnym) jako ciąg komórek ponumerowanych kolejnymi liczbami. Gdy procesor zna numer komórki, sięga do niej wprost. Gdy zbiór jest nieuporządkowany, zostaje wyszukiwanie sekwencyjne, czyli przeglądanie komórek w kolejności zapisu, tak jak szuka się kluczy po kolei w każdej kieszeni.

Wyszukiwanie binarne: dzielimy zbiór na pół

Gdy dane są uporządkowane, sprawdzamy środkową komórkę i odrzucamy tę połowę, w której szukanej liczby na pewno nie ma. To wyszukiwanie binarne, zwane też połówkowym, dokładnie jak w zgadywance, gdzie po każdej odpowiedzi „za dużo” albo „za mało” odpada połowa liczb.

Po każdej próbie zostaje mniejszy zbiór i dokładnie to samo zadanie, czyli podproblem tej samej postaci. W podstawie programowej ta technika nazywa się metodą połowienia. Dlatego ten program da się zapisać także rekurencyjnie: sprawdź środek, a z połową, która została, zrób to samo.

Hasła w słowniku szukacie podobnie, choć nie tak samo: nie otwieracie go dokładnie w połowie, tylko zgadujecie stronę po pierwszej literze. To wyszukiwanie interpolacyjne.

Trzy sprawdzenia zamiast dziewięciu

1. Środek zbioru to indeks 11, jest tam liczba 68. To więcej niż 59, więc komórki o indeksach większych od 11 odpadają.
2. Środek reszty to indeks 5, jest tam 51. To mniej niż 59, więc szukamy w komórkach o indeksach od 6 do 10.
3. Trzecia próba to indeks 8. Tam leży liczba 59, koniec.

Środek liczymy tak: lewy plus prawy, dzielone przez 2, bez reszty. Po kolei byłoby 9 sprawdzeń.

Ćwiczenie: szukamy w piętnastu liczbach

indeks   0  1  2  3  4  5  6  7
wartość  4  7 12 15 21 26 33 38
indeks   8  9 10 11 12 13 14
wartość 44 50 57 61 68 72 80

Lewy | Prawy | Środek | Wartość | Decyzja

Dla chętnych (dom): zapisz indeksy i wartości kolejno sprawdzanych komórek przy szukaniu liczby 80 w zbiorze z rys. 9.9.

Trzy pytania na koniec

1. Dlaczego wyszukiwania binarnego nie da się użyć w zbiorze nieuporządkowanym?
2. Liczba ze środka zbioru okazała się większa od szukanej. Co robimy z prawą połową i dlaczego?
3. Czym różni się wyszukiwanie interpolacyjne od binarnego?

A jak to wygląda w produkcji?