1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Salut, je suis Mark
Grozen-Smith, et c'est Quicksort.

3
00:00:10,390 --> 00:00:13,520
Tout comme le tri par insertion et la bulle
tri, tri rapide est un algorithme de

4
00:00:13,520 --> 00:00:15,720
tri d'une liste ou un tableau des choses.

5
00:00:15,720 --> 00:00:19,080
Pour simplifier, supposons que les
les choses ne sont que des nombres entiers, mais

6
00:00:19,080 --> 00:00:22,060
sachez que Quicksort travaille pour
plus que des chiffres.

7
00:00:22,060 --> 00:00:24,720
Quickstart est un peu plus compliqué
que l'insertion ou la bulle, mais il est

8
00:00:24,720 --> 00:00:27,560
également beaucoup plus efficace
dans la plupart des cas.

9
00:00:27,560 --> 00:00:28,150
Attendez une seconde.

10
00:00:28,150 --> 00:00:30,760
At-il simplement dire «plus
cas, "pas" tous "?

11
00:00:30,760 --> 00:00:31,710
Fait intéressant, aucun.

12
00:00:31,710 --> 00:00:33,560
Tous les cas sont les mêmes.

13
00:00:33,560 --> 00:00:36,650
Ne vous inquiétez pas de ce détail si vous
n'ont pas encore vu notation grand O, mais

14
00:00:36,650 --> 00:00:39,730
Quicksort est un O (n carré) algorithme
au pire, tout comme

15
00:00:39,730 --> 00:00:41,430
insertion ou tri à bulles.

16
00:00:41,430 --> 00:00:44,950
Cependant, il s'agit généralement beaucoup plus
comme un analogue vieux m algorithme.

17
00:00:44,950 --> 00:00:45,750
Pourquoi?

18
00:00:45,750 --> 00:00:46,810
Nous y reviendrons plus tard.

19
00:00:46,810 --> 00:00:49,610
Mais pour l'instant, disons simplement apprendre
comment Quicksort fonctionne.

20
00:00:49,610 --> 00:00:53,080
>> Donc, nous allons marcher à travers ce Quicksorting
tableau d'entiers de la plus petite

21
00:00:53,080 --> 00:00:54,260
au plus grand.

22
00:00:54,260 --> 00:01:00,110
Ici, nous avons les entiers 6,
5, 1, 3, 8, 4, 7, 9, et 2.

23
00:01:00,110 --> 00:01:03,480
Tout d'abord, nous choisissons l'élément final de
ce tableau - dans ce cas, deux -

24
00:01:03,480 --> 00:01:06,870
et appeler cela le «pivot». Ensuite, nous
commencer à regarder deux choses -

25
00:01:06,870 --> 00:01:10,220
un, l'indice le plus bas, que j'appellerai
pour que de rester à la droite de

26
00:01:10,220 --> 00:01:13,970
au mur, et, deux, la gauche
élément, que j'appellerai le «courant

27
00:01:13,970 --> 00:01:17,260
élément. "Ce que nous allons faire est
regarder tous les autres éléments, d'autres

28
00:01:17,260 --> 00:01:20,930
que le pivot, et mettre tous les éléments
plus petit que le pivot de l'

29
00:01:20,930 --> 00:01:24,140
à gauche de la paroi et tous ceux
plus grand que le pivot de l'

30
00:01:24,140 --> 00:01:25,570
droit de la paroi.

31
00:01:25,570 --> 00:01:29,560
Puis, finalement, nous laissons tomber le pivot
à droite sur le mur de la mettre entre

32
00:01:29,560 --> 00:01:32,970
tous les nombres inférieurs à ce
et tous les nombres plus grands.

33
00:01:32,970 --> 00:01:34,460
>> Alors faisons-le.

34
00:01:34,460 --> 00:01:38,540
Décrochez le 2, mettre le mur à l'
début, et appeler le 6 "courant

35
00:01:38,540 --> 00:01:41,590
élément. "Donc, nous voulons regarder
notre élément courant, le 6.

36
00:01:41,590 --> 00:01:44,200
Et comme il est plus grand que le
2, nous l'y laisser à la

37
00:01:44,200 --> 00:01:45,610
droit de la paroi.

38
00:01:45,610 --> 00:01:48,980
Ensuite, nous passons à regarder la 5 comme notre
élément actuel et voir que cette

39
00:01:48,980 --> 00:01:51,840
est, de nouveau, plus grand que le pivot, de sorte que nous
le laisser là où il est sur la bonne

40
00:01:51,840 --> 00:01:53,190
côté de la paroi.

41
00:01:53,190 --> 00:01:53,880
Nous passons.

42
00:01:53,880 --> 00:01:56,750
Notre élément courant est
maintenant 1, et - oh.

43
00:01:56,750 --> 00:01:58,030
C'est différent maintenant.

44
00:01:58,030 --> 00:02:00,890
L'élément courant est maintenant plus petit que
le pivot, si nous voulons mettre

45
00:02:00,890 --> 00:02:02,570
à la gauche de la paroi.

46
00:02:02,570 --> 00:02:06,555
Pour ce faire, nous allons faire de la commutation
élément courant avec l'indice le plus bas

47
00:02:06,555 --> 00:02:07,970
assis juste à la droite de la paroi.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Maintenant, nous passons la paroi d'un indice
de sorte que le 1 est sur la gauche

50
00:02:17,570 --> 00:02:19,750
côté du mur maintenant.

51
00:02:19,750 --> 00:02:20,310
>> Attendez.

52
00:02:20,310 --> 00:02:23,450
Je viens confondu les éléments de la
côté droit de la paroi, n'ai-je pas?

53
00:02:23,450 --> 00:02:23,890
Ne vous inquiétez pas.

54
00:02:23,890 --> 00:02:24,930
C'est très bien.

55
00:02:24,930 --> 00:02:27,570
La seule chose que nous nous soucions pour l'instant
est que tous ces éléments à l'

56
00:02:27,570 --> 00:02:29,570
droit de la paroi sont plus
que le pivot.

57
00:02:29,570 --> 00:02:31,760
Pas de commande réelle est encore supposé.

58
00:02:31,760 --> 00:02:33,200
>> Maintenant, retour à trier.

59
00:02:33,200 --> 00:02:35,840
Donc, nous continuons à chercher à
le reste des éléments.

60
00:02:35,840 --> 00:02:39,075
Et dans ce cas, nous voyons qu'il ya
aucun autre élément de moins que le

61
00:02:39,075 --> 00:02:42,100
pivot, si nous les laissons tous sur
Du côté droit de la paroi.

62
00:02:42,100 --> 00:02:45,980
Enfin, nous arrivons à l'élément courant
et de voir qu'il est le pivot.

63
00:02:45,980 --> 00:02:48,830
Maintenant, ce qui signifie que nous avons deux
les sections de la matrice, la première étant

64
00:02:48,830 --> 00:02:51,820
petit sur le pivot et sur le côté gauche
de la paroi, et la seconde étant

65
00:02:51,820 --> 00:02:54,500
plus grand que le pivot de l'
côté droit de la paroi.

66
00:02:54,500 --> 00:02:57,040
Nous voulons mettre l'élément de pivot entre
les deux, et alors nous saurons

67
00:02:57,040 --> 00:03:01,000
que le pivot est à sa droite
lieu triée finale.

68
00:03:01,000 --> 00:03:04,980
Donc, nous passons le premier élément de la
côté droit de la paroi avec le pivot,

69
00:03:04,980 --> 00:03:06,410
et nous savons de pivot
dans sa position droite.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Nous répétons ensuite ce processus pour le
sous-réseaux à gauche et à droite du pivot.

72
00:03:15,650 --> 00:03:18,700
Depuis le dernier sous-groupe est seule
élément longtemps, nous savons que c'est déjà

73
00:03:18,700 --> 00:03:22,480
trié car comment pouvez-vous être sur
commander si vous êtes seulement un élément?

74
00:03:22,480 --> 00:03:28,860
Pour le côté droit du sous-tableau, nous
voir que le pivot est 5, et la paroi

75
00:03:28,860 --> 00:03:32,250
est juste à gauche de la 6.

76
00:03:32,250 --> 00:03:34,970
Et l'élément courant aussi
commence comme la 6.

77
00:03:34,970 --> 00:03:36,200
Ainsi, la figure 6 est supérieur à 5.

78
00:03:36,200 --> 00:03:38,590
Nous laissons où il est sur le
côté droit de la paroi.

79
00:03:38,590 --> 00:03:41,060
Passons maintenant, 3 est inférieure à 5.

80
00:03:41,060 --> 00:03:44,160
Donc nous passons avec le premier élément
juste à droite du mur.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Maintenant, je suis passé de la paroi d'un.

83
00:03:50,750 --> 00:03:53,010
Maintenant, passer à la 8.

84
00:03:53,010 --> 00:03:56,480
La figure 8 est supérieur à 5,
et si nous laissons.

85
00:03:56,480 --> 00:03:58,720
La figure 4 est inférieur à 5, de sorte que nous commutateur il.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
Et sur.

88
00:04:03,570 --> 00:04:04,820
Et sur.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Chaque fois que nous répétons le processus sur le
les côtés gauche et droit de la matrice. nous

91
00:04:13,670 --> 00:04:17,010
choisir un pivot et faire les comparaisons
et créer un autre niveau de gauche et

92
00:04:17,010 --> 00:04:18,240
sous-réseaux droite.

93
00:04:18,240 --> 00:04:21,500
Cet appel récursif se poursuivra jusqu'à
nous arrivons à la fin lorsque nous avons

94
00:04:21,500 --> 00:04:25,290
divisé le tableau global en
seulement sous-réseaux de longueur 1.

95
00:04:25,290 --> 00:04:28,060
De là, nous savons que le tableau est trié
parce que chaque élément a, à

96
00:04:28,060 --> 00:04:29,330
un moment donné, a été un pivot.

97
00:04:29,330 --> 00:04:32,720
En d 'autres termes, pour chaque élément, tout
les chiffres à gauche sont moins

98
00:04:32,720 --> 00:04:36,420
valeurs et tous les numéros à l'
avoir le droit des valeurs supérieures.

99
00:04:36,420 --> 00:04:38,980
>> Cette méthode fonctionne très bien si l'
valeur du pivot choisi est

100
00:04:38,980 --> 00:04:41,930
approximativement au milieu
gamme des valeurs de la liste.

101
00:04:41,930 --> 00:04:45,630
Cela signifierait que, après nous allons
les éléments autour, là-bas sur le plus grand nombre

102
00:04:45,630 --> 00:04:48,390
des éléments à gauche du pivot
car il ya à droite.

103
00:04:48,390 --> 00:04:52,380
Et la nature diviser pour régner de l'
algorithme de tri rapide est alors prise

104
00:04:52,380 --> 00:04:53,850
pleinement parti de.

105
00:04:53,850 --> 00:04:57,500
Cela crée un environnement d'exécution de O (n log n),
n parce que nous avons à faire n moins 1

106
00:04:57,500 --> 00:05:01,640
comparaisons sur chaque génération et le journal
n parce que nous devons diviser la liste

107
00:05:01,640 --> 00:05:03,210
log n fois.

108
00:05:03,210 --> 00:05:06,160
Toutefois, dans le pire des cas, ce
algorithme peut effectivement être O (n

109
00:05:06,160 --> 00:05:09,850
carré.) Supposons que chaque génération,
le pivot se trouve juste à la

110
00:05:09,850 --> 00:05:12,520
le plus petit ou le plus grand de l'
chiffres que nous tri.

111
00:05:12,520 --> 00:05:15,870
Cela signifierait briser la liste
n fois et décision n moins 1

112
00:05:15,870 --> 00:05:17,690
comparaisons à chaque fois unique.

113
00:05:17,690 --> 00:05:20,490
Ainsi, n o de carré.

114
00:05:20,490 --> 00:05:22,000
>> Comment pouvons-nous améliorer la méthode?

115
00:05:22,000 --> 00:05:25,100
Une bonne façon d'améliorer la méthode est
de réduire la probabilité que

116
00:05:25,100 --> 00:05:28,150
l'exécution est jamais réellement
o n de carré.

117
00:05:28,150 --> 00:05:31,860
Rappelez-vous cette pire, le pire des scénarios
ne peut se produire lorsque le

118
00:05:31,860 --> 00:05:35,320
pivot choisi est toujours la plus haute
ou la plus basse valeur du tableau.

119
00:05:35,320 --> 00:05:38,630
Pour assurer que cela soit moins susceptible de se produire,
nous pouvons trouver le pivot par

120
00:05:38,630 --> 00:05:42,610
choix multiples éléments et
prenant la valeur médiane.

121
00:05:42,610 --> 00:05:44,650
>> Mon nom est Mark Grozen-Smith,
et c'est CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> Pour simplifier, supposons que les
les choses ne sont que des nombres entiers, mais

124
00:05:50,930 --> 00:05:51,970
savoir que QUICKSERT -

125
00:05:51,970 --> 00:05:53,160
QUICKSERT?

126
00:05:53,160 --> 00:05:55,200
Désolé.

127
00:05:55,200 --> 00:06:02,000
>> Ici, nous avons les nombres entiers
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> INTERLOCUTEUR 1: Vraiment?

129
00:06:03,200 --> 00:06:04,850
>> ENCEINTE 2: Ne pas s'arrêter là.

130
00:06:04,850 --> 00:06:06,100
>> INTERLOCUTEUR 1: Vraiment?

131
00:06:06,100 --> 00:06:08,491