Qu'est-ce que Quicksort?

Quicksort est l'un des algorithmes de tri efficaces. L'algorithme effectue le tri en appliquant le paradigme de division et de conquête. Considérez un tableau a [1… n] de n éléments. L'algorithme divise le tableau A sur un index Q de telle sorte que tous les éléments de la gauche à gauche de l'index sont moins que l'élément de l'index Q (A [Q]), et tous les éléments du sous-réseau droit sont supérieurs à un [Q]. Maintenant, l'algorithme trie récursivement les deux sous-charges A [1… Q-1] et un [Q + 1… n] en place en appelant la fonction Quicksort. Pour obtenir l'index Q, l'algorithme utilise une fonction de partition.

La fonction de partition est une fonction qui prend un tableau a [l… u] comme entrée. Ici, l est la limite inférieure, et u est la limite supérieure du tableau. L'algorithme trouve un index q de sorte que tous les éléments inférieurs à un [q] tombent dans le sous-réseau a [l… q-1], et tous les éléments supérieurs à une [Q] tombent dans la sous-bande A [Q + 1… U]. La fonction de partition y parvient en utilisant un élément pivot et deux pointeurs - Pointer I et pointeur J vers le tableau.

Le pointeur J pointe vers le premier élément du tableau, et le pointeur I est initialisé sous le nom de J-1. La fonction itère dans le tableau à l'aide du pointeur j. Pour l'élément A [J], l'élément peut être supérieur à l'élément pivot ou inférieur à l'élément pivot. Si l'élément est supérieur à l'élément pivot, le pointeur J est incrémenté, pointant vers l'élément suivant. Si l'élément A [J] est inférieur à l'élément de pivot, nous incrémentons pointeur I, échangez un [i] et a [j]. L'échange des éléments aide à maintenir le pointeur I de telle sorte que les éléments jusqu'à l'élément pointé par le pointeur I sont inférieurs à l'élément pivot. Comme étape finale, la fonction de partition échange l'élément de pivot avec l'élément à l'index I + 1, déplaçant ainsi l'élément de pivot dans la position correcte dans le tableau partitionné.

Code source

Def partition (Arr, LB, UB):
# Le dernier élément du tableau est pris
# pour être un élément pivot
pivot_elt = arr [ub-1]
i = lb - 1
pour J dans la gamme (lb, ub):
# Si l'élément est inférieur à l'élément pivot
Si arr [j] # Échanger les éléments afin que les éléments
# arr [lb… i] est toujours inférieur à l'élément pivot
i = i + 1
arr [i], arr [j] = arr [j], arr [i]
# Échange final de l'élément pivot et arr [i + 1]
# pour mettre l'élément pivot en place
arr [i + 1], arr [ub-1] = arr [ub-1], arr [i + 1]
retour i + 1
def Quick_sort (Arr, LB, UB):
si (lb# Tri récursivement le tableau
Q = partition (arr, lb, ub)
arr = Quick_sort (arr, lb, q)
arr = Quick_sort (arr, q + 1, ub)
retourr arr
Si __name__ == "__main__":
arr = [3, 7, 9, 2, 5, 0]
n = len (arr)
arr = Quick_sort (arr, 0, n)
imprimer (arr)

La complexité temporelle de la meilleure cas de Quicksort est O (n log n). Dans le meilleur cas, dans chaque appel à l'algorithme, l'algorithme divise le problème en deux sous-problèmes de taille égale. La pire complexité de temps de l'algorithme Quicksort est O (n ^ 2). Cela se produit lorsque l'élément de partition est toujours choisi comme dernier élément, et le tableau est déjà trié.