Szukanie i sortowanie

Wyszukiwanie liniowe sprawdza elementy po kolei od początku. Jest proste, ale przy 1000 elementach może wymagać 1000 sprawdzeń.

Wyszukiwanie binarne działa tylko na uporządkowanym zbiorze: sprawdzamy element w środku i odrzucamy połowę, w której szukanej wartości być nie może. Przy 1000 elementach wystarczy około 10 kroków.

Sortowanie przez wybór szuka najmniejszego elementu i przenosi go na początek, potem powtarza to dla reszty. Sortowanie bąbelkowe porównuje sąsiednie pary i zamienia je miejscami, aż nic nie trzeba zamieniać.

• Liniowe — sprawdza po kolei, do 1000 kroków
• Binarne — połowi zbiór, ok. 10 kroków na 1000
• Warunek binarnego — zbiór musi być posortowany
• Przez wybór — szukaj najmniejszego, przenieś na początek
• Bąbelkowe — zamieniaj sąsiednie pary

• Wyszukiwanie liniowe — prosty przegląd po kolei
• Wyszukiwanie binarne — dzielenie zbioru na pół
• Sortowanie bąbelkowe — zamiana sąsiadów
• Sortowanie przez wybór — wybieranie najmniejszego

Jak działa wyszukiwanie liniowe?

Sprawdza elementy po kolei od początku do końca.

Jak działa wyszukiwanie binarne?

Sprawdza środek zbioru i odrzuca połowę, w której elementu być nie może.

Jaki warunek musi spełniać wyszukiwanie binarne?

Zbiór musi być posortowany.

Ile kroków binarnego dla 1000 elementów?

Około 10.

Jak działa sortowanie przez wybór?

Szuka najmniejszego elementu i przenosi go na początek, potem powtarza.

Jak działa sortowanie bąbelkowe?

Porównuje sąsiednie pary i zamienia je, aż nic nie trzeba zamieniać.

Które wyszukiwanie jest szybsze?

Binarne — ale wymaga uporządkowanych danych.

Po co porządkować dane?

Żeby móc szukać znacznie szybciej.

Ile elementów odrzuca wyszukiwanie binarne po jednym kroku?

Połowę pozostałych elementów.

Dlaczego sortowanie bąbelkowe tak się nazywa?

Bo największe wartości stopniowo „wypływają” na koniec listy.

Czego wymaga zamiana miejscami dwóch elementów?

Zmiennej pomocniczej, w której odkładamy pierwszą wartość.

Kiedy szczególnie opłaca się posortować dane?

Gdy będziemy w nich wielokrotnie wyszukiwać.

1. Wyszukiwanie binarne wymaga, aby dane były…

1. Kolorowe
2. Posortowane
3. Liczbami
4. Zapisane w arkuszu

2. Sortowanie przez wybór zaczyna od…

1. Znalezienia największego elementu
2. Znalezienia najmniejszego
3. Środka zbioru
4. Losowego elementu

3. Sortowanie bąbelkowe nazwano tak, bo…

1. Używa okrągłych liczb
2. Największe wartości „wypływają” na koniec listy
3. Działa tylko na małych zbiorach okrągłych liczb
4. Dzieli listę na pół

4. Sortowanie danych opłaca się szczególnie wtedy, gdy…

1. Danych jest bardzo mało
2. Będziemy w nich wielokrotnie wyszukiwać
3. Dane są tekstem
4. Nie planujemy już nigdy więcej ich używać

5. Sortowanie bąbelkowe porównuje:

1. sąsiednie elementy
2. pierwszy z ostatnim
3. losowe pary
4. tylko liczby parzyste