Algorytmy sortowania – właściwości

Mówiąc o algorytmach sortowaniasortowanie stabilnesortowania, powinniśmy pamiętać o tym, jak można je scharakteryzować oraz ze względu na co podzielić.

Możemy wyróżnić działania, na których bazuje większość algorytmów sortowania, które poznamy – są to np.: wstawianie, zamiana, wybór oraz łączenie. Algorytmy najczęściej wykorzystują kilka z nich.

Sortowanie w miejscu

Algorytmy sortowania, które sortują w miejscu (in situ) to takie algorytmy, które niezależnie od tego, jaki jest rozmiar danych wejściowych, do wykonania sortowania potrzebują stałej ilości pamięci komputera.

Algorytmy iteracyjne i rekurencyjne

Niektóre z algorytmów sortowania wykorzystują rekurencję. Może to powodować sytuację, w której ich wykorzystanie jest ograniczone, np. dla przypadku pesymistycznego algorytm sortowania szybkiego ma kwadratową złożoność.

Inne algorytmy wykorzystują techniki iteracyjne, to jest pętle, których celem jest powtarzanie bloków instrukcji aż do spełnienia pewnego warunku.

Algorytmy liniowe i wykorzystujące metodę „dziel i zwyciężaj”

Algorytmy wykorzystujące metodę „dziel i zwyciężaj” składają się z trzech etapów – najpierw należy podzielić problem na podproblemy, następnie znaleźć rozwiązanie dla każdego problemu, a następnie połączyć rozwiązania poszczególnych podproblemów w rozwiązanie problemu głównego. Metoda została dokładniej omówiona w e‑materiale Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”Pv0IXD75RRozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”.

Algorytmy liniowe natomiast przechodzą przez dane sekwencyjnie (element po elemencie) w celu uporządkowania ich w odpowiedniej kolejności

Algorytmy oparte na porównywaniu i zliczaniu

Wyróżnia się algorytmy sortowania bazujące na porównywaniu elementów oraz zliczaniu ich.

Algorytmy bazujące na porównywaniu elementów określają, czy dany element jest większy, mniejszy od danego innego elementu czy mu równy. Na tej podstawie elementy są zamieniane miejscami, by uporządkować je w odpowiedniej kolejności

Algorytmy wykorzystując zliczanie działają w taki sposób, że zliczają wystąpienia poszczególnych wartości, zamiast porównywać je bezpośrednio. Na podstawie informacji o liczbie wystąpień wartości, elementy są umieszczane na odpowiednich pozycjach.

Stabilność

Algorytmy sortowania stabilnego to takie algorytmy, w których elementy o takiej samej wartości podczas sortowania nie zmieniają kolejności względem siebie.

Złożoność obliczeniowa i pamięciowa

Informacje na temat złożoności obliczeniowej oraz pamięciowej znajdziesz w e‑materiałach Jak wybrać odpowiedni algorytm sortowania?PzdpKUcTTJak wybrać odpowiedni algorytm sortowania? oraz Porównanie algorytmów sortowaniaP173pmQg7Porównanie algorytmów sortowania.

Sposób sortowania elementów

Wyrazy sortowanego zbioru mogą być sortowane rosnąco, niemalejąco, malejąco lub nierosnąco. Domyślnym przypadkiem jest sortowanie niemalejące lub rosnące.

Chociaż terminy kolejność niemalejąca i rosnąca oraz nierosnąca i malejąca bywają używane zamiennie, ich znaczenia nie są tożsame.

O sortowaniu rosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy od poprzedniego – nie ma równych elementów.

0 2 5 7 13 16 34 37 51 61

O sortowaniu niemalejącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy lub równy poprzedniemu (w zbiorze są równe sobie elementy).

0 2 5 7 7 16 34 51 51 61

O sortowaniu malejącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy od poprzedniego – nie ma równych elementów.

61 51 37 34 16 13 7 5 2 0

O sortowaniu nierosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy lub równy poprzedniemu (w zbiorze są równe sobie elementy).

61 51 51 34 16 7 7 5 2 0

Podsumowanie

Większość wspomnianych algorytmów opisujemy w e‑materiałach.

Różne właściwości algorytmów mogą być powiązane w różny sposób, a wiele algorytmów można przypisać do kilku kategorii, np. sortowanie szybkie (quicksort) jest algorytmem porównawczym, który wykorzystuje technikę dziel i zwyciężaj i może być zaimplementowany za pomocą iteracji lub rekurencji (choć w e‑materiałach przedstawimy jego rekurencyjną implementację).

Często decyzja o wyborze strategii zależy od konkretnych wymagań i ograniczeń problemu, który próbujemy rozwiązać. O tym, w jaki sposób dobrać algorytm sortowania, przeczytasz w e‑materiale Jak wybrać odpowiedni algorytm sortowania?PzdpKUcTTJak wybrać odpowiedni algorytm sortowania?.

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:
        jeśli tab[i] = szukana_liczba
            wypisz "Znaleziono liczbę na pozycji:" i
            znaleziono ← prawda
            zakończ działanie algorytmu
        i ← i + 1


    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[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. 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 binarneP1BaMcr5iWyszukiwanie 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.

Zadanie typu maturalnego, które wymaga odnalezienia konkretnego elementu, w którym wykorzystujemy wyszukiwanie liniowego oraz binarne, znajdziesz w e‑materiale Przerywanie pętli – zadania maturalnePHkbTufMAPrzerywanie pętli – zadania maturalne.

Jak widzimy, algorytm wyszukiwania binarnego zadziałał szybciej niż algorytm liniowyPiVb7f8s2algorytm 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.

Słownik