Kolejny wpis z cyklu JavaByExample. W poprzednim wpisie rozpisałem jak wygląda rekurencja – jeśli potrzebujesz to wróć do tego wpisu, dziś po raz kolejny użyjemy tej techniki!

Dzisiejsze zadanie jest kolejnym klasykiem – algorytmami sortującymi wykładowcy meczą studentów od zawsze, i pewnie już nigdy nie przestaną 😉

Zaimplementuj algorytm sortujący QuickSort

Okej, jak wygląda ten algorytm? Powiem szczerze – jest naprawdę wiele wersji tego algorytmu. Jest ich tak wiele ze względu na proces optymalizacji jaką przechodził ten algorytm. My zajmiemy się dziś jedną z podstawowych wersji algorytmu QuickSort 😊

Ogólna założenia algorytmu: Wybierany jest element  według którego sortujemy (pivot), wszystkie elementy mniejsze, umieszczamy po jego lewej stronie a elementy większe – po jego prawej stronie.
Następnie powtarzamy tą czynność dla lewej i prawej strony, do momentu aż wszystkie elementy będą posortowane.

Daną wejściową jest nieposortowana tablica np.:

Pierwszym krokiem jest wybór elementu według którego będziemy sortować, potocznie ten element jest nazywany pivotem – dla uproszczenie można wybrać ostatni index tablicy wejściowej.

Zaczynamy nasze sortowanie. Iterujemy w pętli po elementach na pozycjach mniejszych niż nasz pivot. Będziemy potrzebować dodatkowego wskaźnika który będzie nam wskazywać na element z którym będziemy przestawiać elementy, nazwijmy sobie go pIndex.

Mamy nasze początkowe ustawienie. Sprawdzamy czy element na który wskazuje index pętli jest mniejszy od naszego pivot’u (4), jeśli tak zamieniamy element na który wskazuje index pętli z elementem na który wskazuje pIndex. Po zamianie zwiększamy pIndex.

W naszym przypadku 7 jest większy od wybranego pivotu (4) – nie podejmujemy żadnej akcji, przechodzimy w pętli do kolejnego elementu:

Czy element na który wskazuje index pętli (2) jest mniejszy od naszego pivotu (4) jest mniejszy? Tak! Zamieniamy zatem elementy znajdujące się na miejscach na który wskazuje index pętli oraz wskaźnik pIndex

Po zamianie zwiększamy pIndex:

Przestawiliśmy jeden element. Jedziemy dalej według tego samego schematu 😉

Przestawiamy elementy -> zwiększamy pIndex -> przchodzimy do kolejnego elementu w pętli

Przedstawiamy elementy -> zwiększamy pIndex -> index pętli nie zostanie zwiększony, doszliśmy do ostatniego sprawdzanego elementu:

W momencie gdy doszliśmy do ostatniego sprawdzanego elementu, dokonujemy dodatkowej zamiany, pIndexu z naszym pivotem:

Ufffff! Właśnie ustawiliśmy pierwszy element! Wszystkie elementy mniejsze od naszego wybranego pivotu znajdują się po jego lewej stronie, a wszystkie większe elementy po jego prawej stronie! Teraz to samo robimy z lewą stroną oraz prawą stroną 🙂

Ze względu że artykuł wyszedł dość obszerny, został podzielony na dwie części – teoria, dostępna w tym wpisie, oraz implementację – która zostanie omówiona w kolejnym wpisie. Jeśli chcesz sprawdzić implementację już teraz, jest ona dostępna na GitHubie!