Quicksort

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Quicksort

Zasada dziel i zwyciężaj
Stosowany w wielu językach programowania
Technika partycjonowania
- Pivot
- elementy mniejsze od pivotu -> lewo
- elementy większe od pivotu -> prawo
Elementy po lewej sortowane rekurencyjnie
Elementy po prawej sortowane rekurencyjnie

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami.

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko.

Partycja Hoare'a

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje drugi element, prawy wskazuje ostatni element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje trzeci element, prawy wskazuje ostatni element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje trzeci element, prawy wskazuje piąty element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje trzeci element, prawy wskazuje piąty element. Strzałki wskazują zamianę trzeciego i piątego elementu.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje trzeci element, prawy wskazuje piąty element. Trzeci i piąty element zostały zamienione miejscami.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje czwarty element, prawy wskazuje piąty element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy i prawy wskazują czwarty element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje czwarty element, prawy wskazuje trzeci element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko. Dwa wskaźniki: lewy wskazuje czwarty element, prawy wskazuje trzeci element. Strzałki wskazują zamianę pierwszego i trzeciego elementu.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Trzeci element jest zaznaczony na niebiesko. Pierwszy i trzeci element zostały zamienione miejscami.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Trzeci element jest zaznaczony na zielono.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Trzeci element jest zaznaczony na zielono, a pierwsze dwa na pomarańczowo – reprezentują lewą część listy.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na niebiesko, drugi na pomarańczowo, trzeci na zielono. Lewy i prawy wskaźnik wskazują drugi element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy element jest zaznaczony na pomarańczowo, drugi i trzeci na zielono.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi i trzeci element są zaznaczone na zielono.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi i trzeci element są zaznaczone na zielono. Prawa część listy jest zaznaczona na pomarańczowo.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi i trzeci element są zaznaczone na zielono. Pierwszy element prawej części jest zaznaczony na niebiesko. Lewy wskaźnik wskazuje drugi element prawej części, prawy wskaźnik wskazuje ostatni element prawej części.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi i trzeci element są zaznaczone na zielono. Pierwszy element prawej części jest zaznaczony na niebiesko. Lewy i prawy wskaźnik wskazują drugi element prawej części listy.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi i trzeci element są zaznaczone na zielono. Pierwszy element prawej części jest zaznaczony na niebiesko. Lewy wskaźnik wskazuje pierwszy element prawej części, prawy wskaźnik wskazuje drugi element prawej części.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi, trzeci i czwarty element są zaznaczone na zielono, piąty i szósty na pomarańczowo.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Pierwszy, drugi, trzeci i czwarty element są zaznaczone na zielono. Element jest zaznaczony na niebiesko. Lewy i prawy wskaźnik wskazują ostatni element.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – w działaniu

Schematyczne przedstawienie listy z nieuporządkowanymi liczbami. Wszystkie elementy są zaznaczone na zielono, ponieważ są posortowane.

Partycja Hoare'a
- Przesuń wskaźnik lewy, aż znajdzie wartość większą od pivotu
- Przesuń wskaźnik prawy, aż znajdzie wartość mniejszą od pivotu

Quicksort – implementacja

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

Quicksort – implementacja

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

Quicksort – implementacja

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

Quicksort – złożoność

Przypadek pesymistyczny: $O(n^2)$
Bardzo wydajny!
- Przypadek średni: $\Theta(n\log{}n)$
- Przypadek optymistyczny: $\Omega(n\log{}n)$
Złożoność pamięciowa: $O(n\log{}n)$

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie