Implementacja algorytmu

Implementacja algorytmu w języku Python

Algorytm sortowania szybkiego bazuje na dwóch funkcjach. Są to:

Funkcja odpowiadająca za podział tablicy – wartością zwracaną przez funkcję będzie indeks miejsca podziału tablicy (indeks pivota). W naszym programie funkcja przyjmie nazwę podziel_tablice. Parametry tej funkcji będą identyczne jak w przypadku funkcji sortowanie_szybkie.
Funkcja wywoływana rekurencyjnie – nazwiemy ją sortowanie_szybkie. Funkcja ta będzie przyjmowała trzy parametry:
- tab – tablica zawierająca liczby całkowite do posortowania,
- indeks_poczatkowy – indeks elementu początkowego fragmentu tablicy, od którego chcemy rozpocząć sortowanie tablicy,
- indeks_koncowy – indeks końcowego elementu fragmentu tablicy, na którym chcemy zakończyć sortowanie tablicy.

Oto obie zadeklarowane funkcje:

def podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy):

def sortowanie_szybkie(tab, indeks_poczatkowy, indeks_koncowy):

Zacznijmy od wypełnienia bloku funkcji sortowanie_szybkie. W instrukcji warunkowej sprawdzamy, czy podana jako argument tablica składa się z więcej niż jednego elementu. Jeżeli tak, następuje wywołanie funkcji podziału tablicy – podziel_tablice. Do zmiennej indeks_podzialu zostanie zapisany punkt podziału tablicy (określony przez funkcję podziel_tablice).

Po wywołaniu funkcji podziału następują dwa wywołania rekurencyjne funkcji sortowanie_szybkie():

sortowanie_szybkie(tab, indeks_poczatkowy, indeks_podzialu - 1);
– dla pierwszej (lewej) części tablicy,
sortowanie_szybkie(tab, indeks_podzialu + 1, indeks_koncowy);
– dla drugiej (prawej) części tablicy.

Oto cały blok funkcji sortowanie_szybkie():

def sortowanie_szybkie(tab, indeks_poczatkowy, indeks_koncowy):
    if indeks_poczatkowy < indeks_koncowy:
        indeks_podzialu = podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy)
        sortowanie_szybkie(tab, indeks_poczatkowy, indeks_podzialu - 1)
        sortowanie_szybkie(tab, indeks_podzialu + 1, indeks_koncowy)

Kolejnym krokiem będzie przygotowanie funkcji podziel_tablice.

Tworzymy zmienną pivot, do której zapisujemy wartość ostatniego elementu z sortowanego zakresu tablicy.

Następnym krokiem jest utworzenie zmiennej indeks_elementu_mniejszego_od_pivota, której ustawiamy wartość o 1 mniejszą od tej zapisanej w zmiennej indeks_poczatkowy. Będzie to iterator, spełniający dwa ważne zadania. Po pierwsze będzie wskazywał, na którą pozycję mamy przenieść element, gdy okaże się on mniejszy od pivota. Po drugie pomoże ustalić, w którym miejscu znajdują się elementy mniejsze od pivota. Tę zmienną wykorzystamy przy kolejnych podziałach tablicy.

Tworzymy pętlę for. Dla czytelności iterator sterujący pętlą określimy jako indeks_poszukujacy. Jego zadaniem będzie przejście po wszystkich elementach tablicy tab, które znajdują się w zadanym zakresie.

Wewnątrz pętli tworzymy instrukcję warunkową. Jeżeli wartość elementu tab[indeks_poszukujacy] jest mniejsza od wartości pivot, przenosimy ją na lewą stronę. Zwiększamy indeks_elementu_mniejszego_od_pivota i zamieniamy miejscami element znajdujący się w tablicy tab[indeks_elementu_mniejszego_od_pivot] z elementem tab[indeks_poszukujacy]. Pamiętajmy, że operacja ta jest powtarzana dla każdej komórki w tablicy, której indeks znajduje się w przedziale <indeks_poczatkowy, indeks_koncowy>.

Po przejściu pętli porządkujemy pivota – zamieniamy go miejscami z elementem wskazywanym przez indeks_elementu_mniejszego_od_pivota + 1.

Funkcję kończymy, zwracając indeks wskazujący na miejsce podziału: indeks_elementu_mniejszego_od_pivota + 1.

def podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy):
    pivot = tab[indeks_koncowy]
    indeksElementuMniejszegoOdPivota = indeks_poczatkowy - 1

    for indeksPoszukujacy in range(indeks_poczatkowy, indeks_koncowy):
        if tab[indeksPoszukujacy] < pivot:
            indeksElementuMniejszegoOdPivota += 1
            tab[indeksElementuMniejszegoOdPivota], tab[indeksPoszukujacy] = tab[indeksPoszukujacy], tab[indeksElementuMniejszegoOdPivota]

    tab[indeksElementuMniejszegoOdPivota + 1], tab[indeks_koncowy] = tab[indeks_koncowy], tab[indeksElementuMniejszegoOdPivota + 1]

    return indeksElementuMniejszegoOdPivota + 1

Utworzymy tablicę z liczbami całkowitymi, a następnie wywołamy funkcję sortowanie_szybkie w celu posortowania elementów. Wypiszemy też elementy tablicy przed sortowaniem i po sortowaniu, żeby zobaczyć, czy zostało ono wykonane poprawnie.

tab = [4, 5, 65, 7, 4, 0, 23, 34, 12, 1, 3, 4, 5]
ostatni_element = len(tab)

for i in range(ostatni_element):
    print(tab[i], end="  ")

print()

sortowanie_szybkie(tab, 0, len(tab) - 1)

for i in range(ostatni_element):
    print(tab[i], end="  ")

Oto pełen kod programu:

Linia 1. def sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek. Linia 2. if indeks podkreślnik poczatkowy otwórz nawias ostrokątny indeks podkreślnik koncowy dwukropek. Linia 3. indeks podkreślnik podzialu znak równości podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły. Linia 4. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik podzialu minus 1 zamknij nawias okrągły. Linia 5. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik podzialu plus 1 przecinek indeks podkreślnik koncowy zamknij nawias okrągły. Linia 7. def podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek. Linia 8. pivot znak równości tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy. Linia 9. indeksElementuMniejszegoOdPivota znak równości indeks podkreślnik poczatkowy minus 1. Linia 11. for indeksPoszukujacy in range otwórz nawias okrągły indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek. Linia 12. if tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy otwórz nawias ostrokątny pivot dwukropek. Linia 13. indeksElementuMniejszegoOdPivota plus znak równości 1. Linia 14. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy. Linia 16. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy. Linia 18. return indeksElementuMniejszegoOdPivota plus 1. Linia 20. tab znak równości otwórz nawias kwadratowy 4 przecinek 5 przecinek 65 przecinek 7 przecinek 4 przecinek 0 przecinek 23 przecinek 34 przecinek 12 przecinek 1 przecinek 3 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 21. ostatni podkreślnik element znak równości len otwórz nawias okrągły tab zamknij nawias okrągły. Linia 23. for i in range otwórz nawias okrągły ostatni podkreślnik element zamknij nawias okrągły dwukropek. Linia 24. print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 26. print otwórz nawias okrągły zamknij nawias okrągły. Linia 28. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek 0 przecinek len otwórz nawias okrągły tab zamknij nawias okrągły minus 1 zamknij nawias okrągły. Linia 30. for i in range otwórz nawias okrągły ostatni podkreślnik element zamknij nawias okrągły dwukropek. Linia 31. print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.

def sortowanie_szybkie(tab, indeks_poczatkowy, indeks_koncowy):
    if indeks_poczatkowy < indeks_koncowy:
        indeks_podzialu = podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy)
        sortowanie_szybkie(tab, indeks_poczatkowy, indeks_podzialu - 1)
        sortowanie_szybkie(tab, indeks_podzialu + 1, indeks_koncowy)
        
def podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy):
    pivot = tab[indeks_koncowy]
    indeksElementuMniejszegoOdPivota = indeks_poczatkowy - 1

    for indeksPoszukujacy in range(indeks_poczatkowy, indeks_koncowy):
        if tab[indeksPoszukujacy] < pivot:
            indeksElementuMniejszegoOdPivota += 1
            tab[indeksElementuMniejszegoOdPivota], tab[indeksPoszukujacy] = tab[indeksPoszukujacy], tab[indeksElementuMniejszegoOdPivota]

    tab[indeksElementuMniejszegoOdPivota + 1], tab[indeks_koncowy] = tab[indeks_koncowy], tab[indeksElementuMniejszegoOdPivota + 1]

    return indeksElementuMniejszegoOdPivota + 1

tab = [4, 5, 65, 7, 4, 0, 23, 34, 12, 1, 3, 4, 5]
ostatni_element = len(tab)

for i in range(ostatni_element):
    print(tab[i], end="  ")

print()

sortowanie_szybkie(tab, 0, len(tab) - 1)

for i in range(ostatni_element):
    print(tab[i], end="  ")

Dla zainteresowanych

W języku Python istnieje wbudowana funkcja sorted(list) lub metoda list.sort(), która działa w oparciu o zmodyfikowany algorytm timesort. Więcej o sortowaniu w języku Python można znaleźć na stronie Sorting HOW TO.

Słownik

pivot

element osiowy – element tablicy wybrany wedle ustalonego schematu; jest to element odpowiadający za sposób dzielenia tablicy

rekurencja

proces polegający na wywoływaniu funkcji przez siebie samą do momentu rozwiązania określonego problemu

wywołanie rekurencyjne

sytuacja, w której funkcja wywołuje samą siebie

zasada „dziel i zwyciężaj”

zasada często stosowana przez programistów przy tworzeniu algorytmów opartych o rekurencję, polegająca na tym, że jeden trudny, złożony problem dzielony jest na kilka mniejszych, prostszych do rozwiązania

złożoność czasowa

ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych

złożoność obliczeniowa

złożoność czasowa i złożoność pamięciowa; ilość zasobów komputerowych potrzebnych do wykonania zadania

Złożoność czasowa algorytmu

Strefa wyzwań

Implementacja algorytmu w języku Python

Słownik