Sortowanie szybkie – algorytm i implementacja w C++

Oto wpis którego nie może zabraknąć w piątek. W kolejnej części „Piątku z sortowaniem”, dowiemy się jak działa oraz jak zaimplementować algorytm sortowania szybkiego. Tak więc, bez zbędnego przedłużania, zaczynajmy.

Algorytm

Sortowanie szybkie (quick sort), to algorytm rekurencyjny opierający na metodzie dziel i zwyciężaj. Dzielimy w nim tablicę wejściową, na mniejsze podtablice. Wykonujemy to, wyznaczając podział z wykorzystaniem punktu osiowego (pivot), zwanego inaczej elementem rozdzielającym.

Istnieje kilka wersji algorytmu sortowania szybkiego, które różnią się od siebie sposobem wyboru punktu osiowego. My wybierzemy wersję, w której punkt osiowy jest zawsze pierwszym elementem tablicy. Jak wyglądają kroku tego algorytmu?

  1. Jeżeli rozmiar rozpatrywanej tablicy jest równy jeden, kończymy algorytm.
  2. Wyznaczamy punkt osiowy, który w naszym przypadku jest pierwszym elementem tablicy.
  3. Dokonujemy wstępnego przesortowania. Przechodzimy kolejno przez elementy tablicy, przyrównując je do wartości punktu osiowego. Jeśli rozpatrywany element jest większy, pozostawiamy go na miejscu, jeżeli jest mniejszy, bądź równy zamieniamy go miejscami z pierwszym elementem większym od punktu osiowego. Jeśli nie ma elementów większych, pozostawiamy element mniejszy na miejscu.
  4. Gdy przejdziemy przez całą tablicę, zamieniamy miejscami punkt osiowy, z ostatnim elementem mniejszym od niego. W ten sposób punkt osiowy znajduje się pomiędzy elementami mniejszymi, a większymi o niego. Elementy w podtablicach nie są jeszcze posortowane.
  5. Ponownie rozpatrujemy algorytm (zaczynając od kroku pierwszego) dla lewej i prawej części tablicy.

Przykład

Nic bardziej nie ułatwi zrozumienie działania algorytmu jak prosty przykład. Weźmy zbiór:

{5, 3, 6, 1, 7, 2}

Naszym punktem osiowym jest element 5. Zaczynamy więc wstępne przesortowanie. W pierwszym kroku porównywania napotykamy element mniejszy od punktu osiowego, jako że brak jest elementów większych pozostawiamy go na miejscu. 6 jest większe, więc również pozostaje na miejscu. Pierwsza zmiana elementów miejscami następuje w przypadku 1, które zostaje zamienione miejscami z 6 dając nam:

{5, 3, 1, 6, 7, 2}

Kolorami zaznaczone zostały rozpatrzone elementy – kolor żółty odpowiada elementom mniejszym od punktu osiowego, a czerwony większym. W kolejnych krokach pozostawiamy element 7 na miejscu, a element 2, zamieniamy miejscami z elementem 6, otrzymując:

{5, 3, 1, 2, 7, 6}

Ostatnim krokiem przed rozpatrzeniem algorytmu dla podtablic, jest zamiana miejscami punktu osiowego, z ostatnim elementem mniejszym od niego. Daje nam to zbiór w postaci:

{2, 3, 1, 5, 7, 6}

Widzimy, że wstępne posortowanie zostało wykonane poprawnie, ponieważ elementy mniejsze znajdują się na lewo od punktu osiowego, a elementy większe, na prawo. Ponownie rozpatrujemy więc algorytm, dla podtablic {2,3,1} oraz {7,6}. Resztę kroków tego przykładu, możecie zobaczyć na animacji poniżej:G

Sortowanie szybkie – Implementacja w C++

Teoria

To co można zauważyć w pierwszej kolejności, chociażby przez nazwę algorytmu, to jego wydajność. Złożoność obliczeniowa plasuje się na poziomie O(nlogn). Szybkość tego algorytmu, zależy głównie od doboru punktu osiowego – im bliżej mediany jest pivot, tym lepej. Jeśli podział jest w miarę zrównoważony, szybkość algorytmu jest naprawdę wysoka. W przypadku przeciętnym złożoność rośnie do O(2nlnn), co wciąż jest dobrym wynikiem. W przypadku pesymistycznym osiąga on złożoność obliczeniową O(n2), czyli taką samą jak chociażby sortowanie przez wybieranie.

Możemy usprawnić działanie algorytmu, w celu przybliżenia go do złożoności O(nlogn). Dokonamy tego chociażby poprzez losowanie elementu osiowego, dzięki czemu zmniejszymy prawdopodobieństwo trafienia na element największy lub najmniejszy.

Co ciekawe mimo swojej nazwy, algorytm sortowania nie jest najszybszym z wszystkich dostępnych algorytmów. Owszem w przypadku optymistycznym, jest bardzo wydajny, jednakże prawdopodobieństwo natrafienia na przypadek pesymistyczny lub pośredni, jest dość duże. Szybszym od niego jest chociażby sortowanie przez kopcowanie, które ma zawsze gwarantowaną złożoność O(nlogn). Algorytm ten, omówimy w przyszłości.

Podsumowanie

Sortowanie szybkie jest ważnym osiągnięciem, w rozwijaniu naszej wiedzy algorytmicznej. Jest to pierwszy z algorytmów o złożoności O(nlogn), który wspólnie poznaliśmy. Właśnie takie algorytmy, są zazwyczaj wykorzystywane w praktyce.

grupa wsparcia matura z informatyki

Jeśli wciąż jesteście głodni wiedzy, lub chcecie jeszcze lepiej przygotować się na maturę z informatyki, zapraszam was do naszej grupy wsparcia na Facebooku. Znajdziecie tam różnorodne materiały, do przygotowania się na maturę z informatyki.

You Might Also Like
Dodaj komentarz