Quicksort

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Quicksort

Využívá princip rozděl a panuj
Implementován v mnoha programovacích jazycích
Technika dělení
- Pivot
- prvky menší než pivot -> vlevo
- prvky větší než pivot -> vpravo
Prvky vlevo jsou seřazeny rekurzivně
Prvky vpravo jsou seřazeny rekurzivně

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly.

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn.

Hoareovo dělení

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na druhý prvek a pravý ukazatel na poslední prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na třetí prvek a pravý ukazatel na poslední prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na třetí prvek a pravý ukazatel na pátý prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na třetí prvek a pravý ukazatel na pátý prvek. Dvě šipky znázorňují, že třetí a pátý prvek budou prohozeny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na čtvrtý prvek a pravý ukazatel na pátý prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý i pravý ukazatel míří na čtvrtý prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn. Jsou zde dva ukazatele. Levý ukazatel míří na čtvrtý prvek a pravý ukazatel na třetí prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. Třetí prvek je modře zvýrazněn. První a třetí prvek byly prohozeny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. Třetí prvek je zeleně zvýrazněn.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. Třetí prvek je zeleně zvýrazněn a první dva prvky jsou oranžově zvýrazněny, což znázorňuje levou část seznamu.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn, druhý oranžově a třetí zeleně. Levý i pravý ukazatel míří na druhý prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn, druhý oranžově a třetí zeleně. Levý i pravý ukazatel míří na druhý prvek. Dvě šipky znázorňují, že první a druhý prvek budou prohozeny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je modře zvýrazněn, druhý oranžově a třetí zeleně. Levý i pravý ukazatel míří na druhý prvek. První a druhý prvek byly prohozeny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První prvek je oranžově zvýrazněn a druhý a třetí prvek zeleně.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý a třetí prvek jsou zeleně zvýrazněny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý a třetí prvek jsou zeleně zvýrazněny. Pravá část seznamu je oranžově zvýrazněna.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý a třetí prvek jsou zeleně zvýrazněny. První prvek pravé části je modře zvýrazněn. Levý ukazatel míří na druhý prvek pravé části a pravý ukazatel na poslední prvek pravé části.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý a třetí prvek jsou zeleně zvýrazněny. První prvek pravé části je modře zvýrazněn. Levý i pravý ukazatel míří na druhý prvek pravé části.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý a třetí prvek jsou zeleně zvýrazněny. První prvek pravé části je modře zvýrazněn. Levý ukazatel míří na první prvek pravé části a pravý ukazatel na druhý prvek pravé části.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý, třetí a čtvrtý prvek jsou zeleně zvýrazněny a pátý a šestý prvek oranžově.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. První, druhý, třetí a čtvrtý prvek jsou zeleně zvýrazněny. Prvek je modře zvýrazněn. Levý i pravý ukazatel míří na poslední prvek.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – v akci

Schématické znázornění seznamu s neuspořádanými čísly. Všechny prvky jsou zeleně zvýrazněny, protože jsou seřazeny.

Hoareovo dělení
- Posouvejte levý ukazatel, dokud nenaleznete hodnotu větší než pivot
- Posouvejte pravý ukazatel, dokud nenaleznete hodnotu menší než pivot

Quicksort – implementace

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 – implementace

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 – implementace

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 – složitost

Nejhorší případ: $O(n^2)$
Velmi efektivní!
- Průměrný případ: $\Theta(n\log{}n)$
- Nejlepší případ: $\Omega(n\log{}n)$
Prostorová složitost: $O(n\log{}n)$

Pojďme si procvičit!

Datové struktury a algoritmy v Pythonu