Quicksort

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Quicksort

  • Suit le principe diviser pour mieux régner
  • Utilisé par nombreux langages de programmation
  • Technique de tri
    • Pivot
    • éléments plus petits que pivot -> gauche
    • éléments plus grands que pivot -> droite
  • Éléments à gauche triés récursivement
  • Éléments à droite triés récursivement
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés.

Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est coloré en bleu.

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

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le deuxième élément et le pointeur de droite pointe vers le dernier élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le troisième élément et le pointeur de droite pointe vers le dernier élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le troisième élément et le pointeur de droite pointe vers le cinquième élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le troisième élément et le pointeur de droite pointe vers le cinquième élément. Il y a deux flèches qui indiquent que le troisième et le cinquième éléments seront échangés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le troisième élément et le pointeur de droite pointe vers le cinquième élément. Les troisième et cinquième éléments ont été intervertis.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le quatrième élément et le pointeur de droite pointe vers le cinquième élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le quatrième élément et le pointeur de droite pointe vers le quatrième élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le quatrième élément et le pointeur de droite pointe vers le troisième élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu. Il existe deux pointeurs. Le pointeur de gauche pointe vers le quatrième élément et le pointeur de droite pointe vers le troisième élément. Il y a deux flèches qui indiquent que le premier et le troisième éléments seront échangés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le troisième élément est coloré en bleu. Les premier et troisième éléments ont été intervertis.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le troisième élément est coloré en vert.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le troisième élément est en vert et les deux premiers éléments en orange, représentant la partie gauche de la liste.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu, le deuxième élément en orange et le troisième élément en vert. Les pointeurs gauche et droit pointent vers le deuxième élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu, le deuxième élément en orange et le troisième élément en vert. Les pointeurs gauche et droit pointent vers le deuxième élément. Il y a deux lignes qui indiquent que le premier et le deuxième éléments seront échangés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu, le deuxième élément en orange et le troisième élément en vert. Les pointeurs gauche et droit pointent vers le deuxième élément. Les premier et deuxième éléments ont été permutés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en orange, et le deuxième et le troisième éléments en vert.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en vert.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en vert. La partie droite de la liste est colorée en orange.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en vert. Le premier élément de la partie droite est coloré en bleu. Le pointeur de gauche pointe vers le deuxième élément de la partie droite et le pointeur de droite vers le dernier élément de la partie droite.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en vert. Le premier élément de la partie droite est coloré en bleu. Les pointeurs gauche et droit pointent vers le deuxième élément de la partie droite de la liste.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en vert. Le premier élément de la partie droite est coloré en bleu. Le pointeur de gauche pointe vers le premier élément de la partie droite et le pointeur de droite vers le deuxième élément de la partie droite.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont en vert, et les cinquième et sixième éléments en orange.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en vert. L'élément est coloré en bleu. Les pointeurs gauche et droit pointent vers le dernier élément.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en vert. L'élément est coloré en bleu. Les pointeurs gauche et droit pointent vers le dernier élément. Il y a deux flèches qui indiquent que le cinquième et le sixième éléments seront échangés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en vert. L'élément est coloré en bleu. Les pointeurs gauche et droit pointent vers le dernier élément. Les cinquième et sixième éléments ont été intervertis.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Tous les éléments sont colorés en vert parce qu’ils sont triés.

  • Tri de Hoare
    • Déplacer pointeur gauche jusqu’à valeur supérieure au pivot
    • Déplacer pointeur droite jusqu’à valeur inférieure au pivot
Structures de données et algorithmes en Python

Quicksort - mise en œuvre

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 - mise en œuvre

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 - mise en œuvre

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...