Quicksort

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Quicksort

  • Suit le principe diviser pour régner
  • Implémenté dans de nombreux langages de programmation
  • Technique de partition
    • Pivot
    • éléments plus petits que le pivot -> gauche
    • éléments plus grands que le pivot -> droite
  • Les éléments à gauche sont triés récursivement
  • Les éléments à droite sont triés récursivement
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés.

Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu.

  • Partition de Hoare
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le deuxième élément et le droit le dernier.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le troisième élément et le droit le dernier.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le troisième élément et le droit le cinquième.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le troisième élément et le droit le cinquième. Deux flèches indiquent que les troisième et cinquième éléments seront échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le troisième élément et le droit le cinquième. Les troisième et cinquième éléments ont été échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le quatrième élément et le droit le cinquième.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le quatrième élément et le droit le quatrième.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le quatrième élément et le droit le troisième.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu. Deux pointeurs : le gauche vise le quatrième élément et le droit le troisième. Deux flèches indiquent que les premier et troisième éléments seront échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le troisième élément est en bleu. Les premier et troisième éléments ont été échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le troisième élément est en vert.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le troisième élément est en vert et les deux premiers en orange, représentant la partie gauche.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en bleu, le deuxième en orange et le troisième en vert. Les pointeurs gauche et droit visent le deuxième élément.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier est en bleu, le deuxième en orange, le troisième en vert. Les pointeurs visent le deuxième. Deux flèches indiquent que les premier et deuxième éléments seront échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier est en bleu, le deuxième en orange, le troisième en vert. Les pointeurs visent le deuxième. Les premier et deuxième éléments ont été échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Le premier élément est en orange et les deuxième et troisième en vert.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en vert.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les trois premiers éléments sont en vert. La partie droite de la liste est en orange.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les trois premiers éléments sont en vert. Le premier élément de la partie droite est en bleu. Le pointeur gauche vise le deuxième élément de la partie droite et le pointeur droit le dernier.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les trois premiers éléments sont en vert. Le premier élément de la partie droite est en bleu. Les pointeurs visent le deuxième élément de la partie droite.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les trois premiers éléments sont en vert. Le premier élément de la partie droite est en bleu. Le pointeur gauche vise le premier élément de la partie droite et le pointeur droit le deuxième.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en vert, et les cinquième et sixième en orange.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs visent le dernier élément.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs visent le dernier élément. Deux flèches indiquent que les cinquième et sixième éléments seront échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs visent le dernier élément. Les cinquième et sixième éléments ont été échangés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : en action

Schéma d'une liste de nombres non triés. Tous les éléments sont en vert car ils sont triés.

  • Partition de Hoare
    • Avancer le pointeur gauche jusqu'à trouver une valeur plus grande que le pivot
    • Avancer le pointeur droit jusqu'à trouver une valeur plus petite que le pivot
Structures de données et algorithmes en Python

Quicksort : implémentation

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)
Structures de données et algorithmes en Python

Quicksort : implémentation

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
Structures de données et algorithmes en Python

Quicksort : implémentation

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]
Structures de données et algorithmes en Python

Quicksort : complexité

  • Pire cas : $O(n^2)$
  • Très efficace !
    • Cas moyen : $\Theta(n\log{}n)$
    • Meilleur cas : $\Omega(n\log{}n)$
  • Complexité spatiale : $O(n\log{}n)$
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...