Quicksort

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Quicksort

  • Suit le principe de division et conquête
  • Implémenté par de nombreux langages
  • Technique de partition
    • Pivot
    • éléments < au pivot -> gauche
    • éléments > au pivot -> droite
  • La partie gauche est triée récursivement
  • La partie droite est triée 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 pointe le deuxième élément et le droit le dernier.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au 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 pointe le troisième élément et le droit le dernier.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au 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 pointe le troisième élément, le droit le cinquième.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le troisième élément, le droit le cinquième. Deux flèches indiquent l’échange des troisième et cinquième éléments.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le troisième élément, le droit le cinquième. Les troisième et cinquième éléments ont été échangés.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le quatrième élément et le droit le cinquième.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le quatrième élément et le droit le quatrième.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le quatrième élément et le droit le troisième.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le quatrième élément et le droit le troisième. Deux flèches indiquent l’échange des premier et troisième éléments.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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, le troisième en vert. Les pointeurs gauche et droit pointent le deuxième élément.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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, le troisième en vert. Les pointeurs gauche et droit pointent le deuxième élément. Deux flèches indiquent l’échange des premier et deuxième éléments.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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, le troisième en vert. Les pointeurs gauche et droit pointent le deuxième élément. Les premier et deuxième éléments ont été échangés.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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, les deuxième et troisième en vert.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le deuxième élément de la partie droite et le pointeur droit le dernier.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 gauche et droit pointent le deuxième élément de la partie droite.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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 pointe le premier élément de la partie droite et le pointeur droit le deuxième.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au pivot
Structures de données et algorithmes en Python

Quicksort - en action

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

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Schéma d’une liste de nombres non triés. Les premier à quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs gauche et droit pointent le dernier élément.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Schéma d’une liste de nombres non triés. Les premier à quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs gauche et droit pointent le dernier élément. Deux flèches indiquent l’échange des cinquième et sixième éléments.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au pivot
Structures de données et algorithmes en Python

Quicksort - en action

Schéma d’une liste de nombres non triés. Les premier à quatrième éléments sont en vert. Un élément est en bleu. Les pointeurs gauche et droit pointent le dernier élément. Les cinquième et sixième éléments ont été échangés.

  • Partition de Hoare
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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
    • Déplacer le pointeur gauche jusqu’à trouver une valeur > au pivot
    • Déplacer le pointeur droit jusqu’à trouver une valeur < au 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...