Meilleure réponse
Comme vous avez suffisamment de connaissances sur le fonctionnement du tri rapide, comme trouver un pivot, diviser le tableau actuel et recommencer de même pour chaque sous-tableau, il est facile danalyser la complexité temporelle en tenant compte de ces éléments:
Pire cas:
Le pire cas se produit lorsque, à chaque récursion, nous obtenons le prochain pivot pour séparer les tableaux se trouve à la fin du tableau.
Si N est la longueur du tableau et ayant le pivot actuel à la position de départ du tableau,
le pivot au dernier index est identifié uniquement en parcourant le tableau du début à la fin. Après avoir corrigé le pivot et divisé les sous-tableaux résultants de longueur sont (N-1), 1 .
Encore une fois, ceci (N-1) le sous-tableau trouve le prochain pivot au dernier index des partitions de tableau résultant avec des longueurs (N-2), 1 .
Ce processus se répète jusquà ce que les longueurs finales des sous-tableaux soient à la fois 1,1 .
Donc, ceci peut être dessiné mathématiquement sur papier comme
à létape 1: avec N éléments, la complexité temporelle de cette partition est
T (N) = N + T (N-1)
Où T (N-1) est la complexité temporelle de la partition pour être traités de manière récursive et N est le temps nécessaire pour comparer N éléments avec un pivot fixe.
à létape 2: avec N-1 éléments ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0 car le temps de partitionner le tableau de longueur 1 est égal à 0 sans partitions
Par conséquent,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Cas moyen :
Dans la casse moyenne, le prochain pivot divise le tableau en deux longueurs égales (N / 2) en comparant tous les éléments qui résultent de la complexité du temps N.
T (N) = 2 * T (N / 2) + N
divise les deux côtés par N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Par conséquent, T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
Comme T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) termes
Donc T (N) / N = log N
T (N) = NlogN
Answer
QuickSort est un algorithme Divide and Conquer. Il sélectionne un élément comme pivot et partitionne le tableau donné autour du pivot sélectionné. Il existe de nombreuses versions différentes de quickSort qui choisissent le pivot de différentes manières.
- Toujours choisir le premier élément comme pivot.
- Toujours choisir le dernier élément comme pivot (implémenté ci-dessous)
- Choisissez un élément aléatoire comme pivot.
- Choisissez la médiane comme pivot.
Le processus clé dans quickSort est une partition ( ). La cible des partitions est, étant donné un tableau et un élément x du tableau comme pivot, mettre x à sa position correcte dans un tableau trié et mettre tous les éléments plus petits (plus petits que x) avant x, et mettre tous les éléments plus grands (plus que x) après x. Tout cela doit être fait en temps linéaire.
Les étapes du tri rapide sont:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implémentation du tri rapide:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Complexité temporelle du tri rapide:
Pire Cas: Le pire des cas se produit lorsque le processus de partition sélectionne toujours le plus grand ou le plus petit élément comme pivot. Si nous considérons la stratégie de partition ci-dessus où le dernier élément est toujours choisi comme pivot, le pire des cas se produirait lorsque le tableau est déjà trié par ordre croissant ou décroissant. Voici la récurrence dans le pire des cas.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
La complexité de la récurrence ci-dessus est de n carré
Meilleur cas: Le meilleur cas se produit lorsque le processus de partition sélectionne toujours lélément central comme pivot. Voici une récurrence pour le meilleur des cas.
T(n) = 2T(n/2) + (n)
La complexité de la récurrence ci-dessus est nLogn
Cas moyen: Pour faire une analyse de cas moyen, nous devons considérer toutes les permutations possibles du tableau et calculer le temps pris par chaque permutation qui ne semble pas facile. Nous pouvons avoir une idée du cas moyen en considérant le cas où la partition met O (n / 9) éléments dans un ensemble et O (9n / 10) éléments dans dautres ensembles. Voici une récurrence pour ce cas.
T(n) = T(n/9) + T(9n/10) + (n)
La complexité de la récurrence ci-dessus est nLogn
Complexité spatiale du tri rapide :
Lespace utilisé par quicksort dépend de la version utilisée.
La version sur place de quicksort a une complexité spatiale de O (log n), même dans le pire des cas, lorsquil est soigneusement implémenté en utilisant les stratégies suivantes:
- le partitionnement sur place est utilisé. Cette partition instable nécessite un espace O (1).
- Après le partitionnement, la partition avec le moins déléments est (récursivement) triée en premier, nécessitant au plus O (log n) espace. Ensuite, lautre partition est triée en utilisant la récursivité ou litération de queue, qui najoute pas à la pile dappels. Cette idée, comme discuté ci-dessus, a été décrite par R. Sedgewick, et maintient la profondeur de pile limitée par O (log n). / li>