Wyszukiwanie elementu w zbiorze posortowanym i nieposortowanym

Zaprezentujmy na przykładzie, jak ważne jest sortowanie elementów i jak bardzo może usprawnić pracę programu. Porównajmy liczbę operacji, jakie będą musiały zostać wykonane podczas wyszukiwania elementu w zbiorze zarówno posortowanym, jak i nieposortowanym.

Specyfikacja problemu:

Dane:

• tab – przeszukiwana tablica liczb

• szukana_liczba – liczba której szukamy

Wynik:

• informacja, czy szukana_liczba znajduje się w tablicy tab

By porównać przykładową liczbę operacji, działanie programu przetestujemy dla tablicy, w skład której wchodzą następujące liczby: 30, 3, 20, 28, 21, 18, 5, 6, 1, 14.

Będziemy szukać liczby 18.

Wyszukiwanie liniowe – wyszukiwanie w zbiorze nieposortowanym.  Ten algorytm realizowany jest liniowo – element po elemencie. Algorytm będzie prezentował się w następujący sposób:

funkcja wyszukiwanie_liniowe(tab, szukana_liczba)
    znaleziono ← fałsz
    i ← 0
    dopóki znaleziono != prawda oraz i < długość(tab) wykonuj:
        j


    jeśli znaleziono = fałsz
        wypisz "Nie znaleziono szukanej liczby"

Przebieg algorytmu dla podanych danych:

• Inicjalizujemy zmienne.

• Rozpoczynamy pętlę:

  • tab[0] = 30 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 1 porównanie.

  • tab[1] = 3 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 2 porównania.

  • tab[2] = 20 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 3 porównania

  • tab[5] = 18 - jest to szukana liczba. Wypisujemy Znaleziono liczbę na pozycji: 5. Ustawiamy znaleziono <-- prawda. Wykonaliśmy 6 porównań. Kończymy działanie algorytmu.

Podsumowując, wykonaliśmy 6 porównań wewnątrz pętli i żadnego porównania po pętli.

Wyszukiwanie liniowe z wartownikiem – na końcu przeszukiwanego zbioru dodajemy element równy poszukiwanemu.

Algorytm będzie prezentował się w następujący sposób:

funkcja wyszukiwanie_liniowe_wartownik(tab, szukana_liczba)
    tab[długość(tab)] ← szukana_liczba
    i ← 0

    dopóki tab[i] != szukana_liczba wykonuj:
        i ← i + 1

    jeśli i < długość(tab) - 1:
        wypisz "Znaleziono liczbę na pozycji:" i
    w przeciwnym przypadku:
        wypisz "Nie znaleziono szukanej liczby"

Przebieg algorytmu dla podanych danych:

• Inicjalizujemy zmienne (pamiętamy o dodaniu wartownika).

• Rozpoczynamy pętlę:

  • tab[0] = 30 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 1 porównanie.

  • tab[1] = 3 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 2 porównania.

  • tab[2] = 20 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 3 porównania.

  • tab[3] = 28 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 4 porównania.

  • tab[4] = 21 - nie jest to szukana liczba, zwiększamy i o 1. Wykonaliśmy 5 porównania.

  • tab[5] = 18 - jest to szukana liczba. Wykonaliśmy 6 porównań.

• Po wyjściu z pętli:

  • sprawdzamy warunek i < długość(tab) - 1:

    • i = 5

    • długość(tab) - 1 = 10 (ponieważ długość tablicy wynosi 11 po dodaniu wartownika)

    • Ponieważ 5 < 10, więc wypisujemy Znaleziono liczbę na pozycji: 5.

Podsumowując, wykonaliśmy 6 porównań wewnątrz pętli i 1 porównanie po pętli (porównanie wartości i z wartością długość(tab) - 1).

Wyszukiwanie binarne – wyszukiwanie w zbiorze posortowanym. Pierwszym krokiem, jaki musimy wykonać, jest posortowanie zbioru. Jest to wymóg zastosowania wyszukiwania binarnego.

Posortowany zbiór będzie wyglądał następująco: {1, 3, 5, 6, 14, 18, 20, 21, 28, 30}.

Następnie wykonujemy algorytm wyszukiwania binarnego:

funkcja wyszukiwanie_binarne(tab, szukana_liczba)
    lewo ← 0
    prawo ← długość(tab) - 1

    dopóki lewo <= prawo wykonuj:
        i ← (prawo + lewo) // 2
        jeżeli tab[i] < szukana_liczba
            lewo ← i + 1
        w innym przypadku
            jeżeli tab[i] > szukana_liczba
                prawo <- i - 1
            w innym przypadku
                wypisz "Znaleziono liczbę na pozycji:" i

    jeżeli lewo > prawo:
        wypisz "Nie znaleziono liczby"

Przebieg algorytmu dla podanych danych:

• Inicjalizujemy zmienne (pamiętamy o dodaniu wartownika).

• Rozpoczynamy pętlę:

  • i <-- (9 + 0) // 2 to 4,czyli tab[4] = 14.

    • 14 < 18 zatem wykonujemy lewo <-- i + 1, co daje lewo <-- 5. Wykonaliśmy 1 porównanie.

  • i <-- (9 + 5) / 2 to 7. Czyli tab[7] = 21.

    • 21 < 18 zatem wykonujemy prawo <-- i - 1, co daje prawo <-- 6. Wykonaliśmy 2 porównania.

  • i <-- (6 + 5) // 2 to 5,czyli tab[5] = 18. Wypisujemy Znaleziono liczbę na pozycji: 5.

Podsumowując, wykonaliśmy 3 porównania (podziały) wewnątrz pętli.

Jak widzimy, algorytm wyszukiwania binarnego zadziałał szybciej niż algorytm liniowy.

Aby można było skorzystać z algorytmu wyszukiwania binarnego, zbiór danych musi być posortowany. W sytuacji, gdy zbiór, w którym jest niewiele elementów, nie będzie często przeszukiwany (np. chcemy wyłącznie raz sprawdzić, czy znajduje się w nim dany element), metoda liniowa (czyli taka, która nie wymaga od nas wcześniejszego posortowania zbioru) może okazać się w zupełności wystarczająca.

Warto jednak pamiętać, że utrzymywanie dużego posortowanego zbioru danych, w którym często szukamy informacji, jest znacznie korzystniejsze ze względu na czas, jaki zajmuje każde wyszukanie. Nawet jeżeli sam proces sortowania okaże się czasochłonny – wykonamy go tylko raz, za to zaoszczędzimy sporo czasu na wielokrotnym przeszukiwaniu zbioru. Dlatego też tak ważna jest znajomość i umiejętność skutecznego użycia podstawowych algorytmów sortowania.