Quicksort

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Quicksort

  • Urmează principiul divide și cucerește
  • Implementat în multe limbaje de programare
  • Tehnica de partiționare
    • Pivot
    • elementele mai mici decât pivotul -> stânga
    • elementele mai mari decât pivotul -> dreapta
  • Elementele din stânga sunt sortate recursiv
  • Elementele din dreapta sunt sortate recursiv
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate.

Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru.

  • Partiționarea Hoare
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al doilea element, iar pointerul drept indică ultimul element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al treilea element, iar pointerul drept indică ultimul element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al treilea element, iar pointerul drept indică al cincilea element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al treilea element, iar pointerul drept indică al cincilea element. Există două săgeți care indică că al treilea și al cincilea element vor fi interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al treilea element, iar pointerul drept indică al cincilea element. Al treilea și al cincilea element au fost interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al patrulea element, iar pointerul drept indică al cincilea element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al patrulea element, iar pointerul drept indică al patrulea element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al patrulea element, iar pointerul drept indică al treilea element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru. Există doi pointeri. Pointerul stâng indică al patrulea element, iar pointerul drept indică al treilea element. Există două săgeți care indică că primul și al treilea element vor fi interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Al treilea element este colorat în albastru. Primul și al treilea element au fost interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Al treilea element este colorat în verde.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Al treilea element este colorat în verde, iar primele două elemente în portocaliu, reprezentând partea stângă a listei.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, al doilea în portocaliu și al treilea în verde. Pointerul stâng și cel drept indică al doilea element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, al doilea în portocaliu și al treilea în verde. Pointerul stâng și cel drept indică al doilea element. Există două săgeți care indică că primul și al doilea element vor fi interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, al doilea în portocaliu și al treilea în verde. Pointerul stâng și cel drept indică al doilea element. Primul și al doilea element au fost interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în portocaliu, iar al doilea și al treilea în verde.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în verde.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în verde. Partea dreaptă a listei este colorată în portocaliu.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în verde. Primul element al părții drepte este colorat în albastru. Pointerul stâng indică al doilea element al părții drepte, iar pointerul drept indică ultimul element al părții drepte.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în verde. Primul element al părții drepte este colorat în albastru. Pointerul stâng și cel drept indică al doilea element al părții drepte a listei.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în verde. Primul element al părții drepte este colorat în albastru. Pointerul stâng indică primul element al părții drepte, iar pointerul drept indică al doilea element al părții drepte.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în verde, iar al cincilea și al șaselea în portocaliu.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în verde. Elementul este colorat în albastru. Pointerul stâng și cel drept indică ultimul element.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în verde. Elementul este colorat în albastru. Pointerul stâng și cel drept indică ultimul element. Există două săgeți care indică că al cincilea și al șaselea element vor fi interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în verde. Elementul este colorat în albastru. Pointerul stâng și cel drept indică ultimul element. Al cincilea și al șaselea element au fost interschimbate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - în acțiune

O reprezentare schematică a unei liste cu numere neordonate. Toate elementele sunt colorate în verde deoarece sunt sortate.

  • Partiționarea Hoare
    • Deplasați pointerul stâng până la o valoare mai mare decât pivotul
    • Deplasați pointerul drept până la o valoare mai mică decât pivotul
Structuri de date și algoritmi în Python

Quicksort - implementare

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)
Structuri de date și algoritmi în Python

Quicksort - implementare

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
Structuri de date și algoritmi în Python

Quicksort - implementare

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]
Structuri de date și algoritmi în Python

Quicksort - complexitate

  • Cazul cel mai defavorabil: $O(n^2)$
  • Foarte eficient!
    • Cazul mediu: $\Theta(n\log{}n)$
    • Cazul cel mai favorabil: $\Omega(n\log{}n)$
  • Complexitate spațială: $O(n\log{}n)$
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...