>> MARK GROZEN-SMITH: Salut, je suis Mark Grozen-Smith, et c'est Quicksort.
Tout comme le tri par insertion et la bulle tri, tri rapide est un algorithme de
tri d'une liste ou un tableau des choses.
Pour simplifier, supposons que les les choses ne sont que des nombres entiers, mais
sachez que Quicksort travaille pour plus que des chiffres.
Quickstart est un peu plus compliqué que l'insertion ou la bulle, mais il est
également beaucoup plus efficace dans la plupart des cas.
Attendez une seconde.
At-il simplement dire «plus cas, "pas" tous "?
Fait intéressant, aucun.
Tous les cas sont les mêmes.
Ne vous inquiétez pas de ce détail si vous n'ont pas encore vu notation grand O, mais
Quicksort est un O (n carré) algorithme au pire, tout comme
insertion ou tri à bulles.
Cependant, il s'agit généralement beaucoup plus comme un analogue vieux m algorithme.
Pourquoi?
Nous y reviendrons plus tard.
Mais pour l'instant, disons simplement apprendre comment Quicksort fonctionne.
>> Donc, nous allons marcher à travers ce Quicksorting tableau d'entiers de la plus petite
au plus grand.
Ici, nous avons les entiers 6, 5, 1, 3, 8, 4, 7, 9, et 2.
Tout d'abord, nous choisissons l'élément final de ce tableau - dans ce cas, deux -
et appeler cela le «pivot». Ensuite, nous commencer à regarder deux choses -
un, l'indice le plus bas, que j'appellerai pour que de rester à la droite de
au mur, et, deux, la gauche élément, que j'appellerai le «courant
élément. "Ce que nous allons faire est regarder tous les autres éléments, d'autres
que le pivot, et mettre tous les éléments plus petit que le pivot de l'
à gauche de la paroi et tous ceux plus grand que le pivot de l'
droit de la paroi.
Puis, finalement, nous laissons tomber le pivot à droite sur le mur de la mettre entre
tous les nombres inférieurs à ce et tous les nombres plus grands.
>> Alors faisons-le.
Décrochez le 2, mettre le mur à l' début, et appeler le 6 "courant
élément. "Donc, nous voulons regarder notre élément courant, le 6.
Et comme il est plus grand que le 2, nous l'y laisser à la
droit de la paroi.
Ensuite, nous passons à regarder la 5 comme notre élément actuel et voir que cette
est, de nouveau, plus grand que le pivot, de sorte que nous le laisser là où il est sur la bonne
côté de la paroi.
Nous passons.
Notre élément courant est maintenant 1, et - oh.
C'est différent maintenant.
L'élément courant est maintenant plus petit que le pivot, si nous voulons mettre
à la gauche de la paroi.
Pour ce faire, nous allons faire de la commutation élément courant avec l'indice le plus bas
assis juste à la droite de la paroi.
Maintenant, nous passons la paroi d'un indice de sorte que le 1 est sur la gauche
côté du mur maintenant.
>> Attendez.
Je viens confondu les éléments de la côté droit de la paroi, n'ai-je pas?
Ne vous inquiétez pas.
C'est très bien.
La seule chose que nous nous soucions pour l'instant est que tous ces éléments à l'
droit de la paroi sont plus que le pivot.
Pas de commande réelle est encore supposé.
>> Maintenant, retour à trier.
Donc, nous continuons à chercher à le reste des éléments.
Et dans ce cas, nous voyons qu'il ya aucun autre élément de moins que le
pivot, si nous les laissons tous sur Du côté droit de la paroi.
Enfin, nous arrivons à l'élément courant et de voir qu'il est le pivot.
Maintenant, ce qui signifie que nous avons deux les sections de la matrice, la première étant
petit sur le pivot et sur le côté gauche de la paroi, et la seconde étant
plus grand que le pivot de l' côté droit de la paroi.
Nous voulons mettre l'élément de pivot entre les deux, et alors nous saurons
que le pivot est à sa droite lieu triée finale.
Donc, nous passons le premier élément de la côté droit de la paroi avec le pivot,
et nous savons de pivot dans sa position droite.
>> Nous répétons ensuite ce processus pour le sous-réseaux à gauche et à droite du pivot.
Depuis le dernier sous-groupe est seule élément longtemps, nous savons que c'est déjà
trié car comment pouvez-vous être sur commander si vous êtes seulement un élément?
Pour le côté droit du sous-tableau, nous voir que le pivot est 5, et la paroi
est juste à gauche de la 6.
Et l'élément courant aussi commence comme la 6.
Ainsi, la figure 6 est supérieur à 5.
Nous laissons où il est sur le côté droit de la paroi.
Passons maintenant, 3 est inférieure à 5.
Donc nous passons avec le premier élément juste à droite du mur.
Maintenant, je suis passé de la paroi d'un.
Maintenant, passer à la 8.
La figure 8 est supérieur à 5, et si nous laissons.
La figure 4 est inférieur à 5, de sorte que nous commutateur il.
Et sur.
>> Chaque fois que nous répétons le processus sur le les côtés gauche et droit de la matrice. nous
choisir un pivot et faire les comparaisons et créer un autre niveau de gauche et
sous-réseaux droite.
Cet appel récursif se poursuivra jusqu'à nous arrivons à la fin lorsque nous avons
divisé le tableau global en seulement sous-réseaux de longueur 1.
De là, nous savons que le tableau est trié parce que chaque élément a, à
un moment donné, a été un pivot.
En d 'autres termes, pour chaque élément, tout les chiffres à gauche sont moins
valeurs et tous les numéros à l' avoir le droit des valeurs supérieures.
>> Cette méthode fonctionne très bien si l' valeur du pivot choisi est
approximativement au milieu gamme des valeurs de la liste.
Cela signifierait que, après nous allons les éléments autour, là-bas sur le plus grand nombre
des éléments à gauche du pivot car il ya à droite.
Et la nature diviser pour régner de l' algorithme de tri rapide est alors prise
pleinement parti de.
Cela crée un environnement d'exécution de O (n log n), n parce que nous avons à faire n moins 1
comparaisons sur chaque génération et le journal n parce que nous devons diviser la liste
log n fois.
Toutefois, dans le pire des cas, ce algorithme peut effectivement être O (n
carré.) Supposons que chaque génération, le pivot se trouve juste à la
le plus petit ou le plus grand de l' chiffres que nous tri.
Cela signifierait briser la liste n fois et décision n moins 1
comparaisons à chaque fois unique.
Ainsi, n o de carré.
>> Comment pouvons-nous améliorer la méthode?
Une bonne façon d'améliorer la méthode est de réduire la probabilité que
l'exécution est jamais réellement o n de carré.
Rappelez-vous cette pire, le pire des scénarios ne peut se produire lorsque le
pivot choisi est toujours la plus haute ou la plus basse valeur du tableau.
Pour assurer que cela soit moins susceptible de se produire, nous pouvons trouver le pivot par
choix multiples éléments et prenant la valeur médiane.
>> Mon nom est Mark Grozen-Smith, et c'est CS50.
>> Pour simplifier, supposons que les les choses ne sont que des nombres entiers, mais
savoir que QUICKSERT -
QUICKSERT?
Désolé.
>> Ici, nous avons les nombres entiers 6, 5, 1, 3, 8, 4, 9.
>> INTERLOCUTEUR 1: Vraiment?
>> ENCEINTE 2: Ne pas s'arrêter là.
>> INTERLOCUTEUR 1: Vraiment?