1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Trier Insertion]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Université de Harvard]

3
00:00:04,240 --> 00:00:07,290
[C'est CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Jetons un coup d'oeil à tri par insertion, un algorithme de prendre une liste de numéros et de les trier.

5
00:00:13,060 --> 00:00:18,300
Un algorithme, rappelez-vous, c'est tout simplement une procédure étape par étape pour accomplir une tâche.

6
00:00:18,300 --> 00:00:23,640
L'idée de base derrière le tri par insertion, est de diviser notre liste en deux parties,

7
00:00:23,640 --> 00:00:26,580
une partie triés et une partie non triés.

8
00:00:26,580 --> 00:00:29,290
>> À chaque étape de l'algorithme, un nombre est déplacée

9
00:00:29,290 --> 00:00:32,439
de la partie non triés à la partie triée

10
00:00:32,439 --> 00:00:35,680
jusqu'à ce que finalement toute la liste est triée.

11
00:00:35,680 --> 00:00:43,340
Voici la liste des six numéros non triés - 23, 42, 4, 16, 8, et 15.

12
00:00:43,340 --> 00:00:47,680
Étant donné que ces chiffres ne sont pas tout dans l'ordre croissant, ils sont triés.

13
00:00:47,680 --> 00:00:53,890
Puisque nous n'avons pas encore commencé le tri, nous allons examiner l'ensemble des six éléments de notre partie non triés.

14
00:00:53,890 --> 00:00:59,270
>> Une fois que nous commencer à trier, nous allons mettre ces chiffres triés à la gauche de ceux-ci.

15
00:00:59,270 --> 00:01:03,600
Donc, nous allons commencer par 23, le premier élément de la liste.

16
00:01:03,600 --> 00:01:06,930
Nous n'avons pas tous les éléments dans notre partie encore triées,

17
00:01:06,930 --> 00:01:12,460
nous allons donc considérer simplement 23 soit le début et la fin de notre part triés.

18
00:01:12,460 --> 00:01:16,510
Maintenant, notre part triés contient un numéro, 23,

19
00:01:16,510 --> 00:01:20,260
et notre portion non triés possède ces cinq numéros.

20
00:01:20,260 --> 00:01:27,320
Nous allons maintenant insérer le numéro suivant dans notre partie non triés, 42, dans la partie triée.

21
00:01:27,320 --> 00:01:35,930
>> Pour ce faire, nous aurons besoin de comparer la 42 à la 23 - le seul élément de notre part triés jusqu'ici.

22
00:01:35,930 --> 00:01:41,980
Quarante-deux est plus grand que 23, donc nous pouvons simplement ajouter 42 à la fin

23
00:01:41,980 --> 00:01:45,420
de la partie de la liste triée. Super!

24
00:01:45,420 --> 00:01:51,850
Maintenant, notre partie a deux éléments triés et non triés notre partie comporte quatre éléments.

25
00:01:51,850 --> 00:01:57,200
Donc, nous allons maintenant passer à la 4, l'élément suivant dans la partie non triés.

26
00:01:57,200 --> 00:02:00,230
Alors, où doit-il être placé dans la partie triée?

27
00:02:00,230 --> 00:02:04,220
>> Rappelez-vous, nous voulons placer ce chiffre dans l'ordre de tri

28
00:02:04,220 --> 00:02:08,680
de sorte que notre partie triée reste correctement triés en tout temps.

29
00:02:08,680 --> 00:02:14,380
Si nous plaçons la 4 à la droite de la 42, alors notre liste sera hors d'usage.

30
00:02:14,380 --> 00:02:18,380
Donc, nous allons continuer à aller de droite à gauche dans notre partie quelconque.

31
00:02:18,380 --> 00:02:23,260
Comme nous nous déplaçons, nous allons passer chaque numéro en bas d'un endroit pour faire de la place pour le nouveau numéro.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 est également inférieur à 23, nous ne pouvons pas le placer non plus.

33
00:02:31,740 --> 00:02:34,480
Passons le 23 à droite un seul endroit.

34
00:02:36,500 --> 00:02:43,120
>> Cela signifie que nous aimerions placer les 4 dans la première fente dans la partie triée.

35
00:02:43,120 --> 00:02:46,300
Remarquez comment cet espace dans la liste était déjà vide,

36
00:02:46,300 --> 00:02:51,120
parce que nous avons été des éléments mobiles triés de la manière que nous avons rencontrés.

37
00:02:51,120 --> 00:02:52,740
Très bien. Donc, nous sommes à mi-chemin.

38
00:02:52,740 --> 00:02:57,990
Continuons notre algorithme en insérant le 16 dans la partie triée.

39
00:02:59,260 --> 00:03:03,820
Seize ans est inférieur à 42, nous allons donc passer de 42 à droite.

40
00:03:05,700 --> 00:03:10,190
Seize ans est également inférieur à 23, nous allons donc passer outre cet élément.

41
00:03:11,790 --> 00:03:20,820
>> Maintenant, 16 est supérieur à 4. Donc, il semble que nous aimerions insérer le 16, entre le 4 et le 23.

42
00:03:20,820 --> 00:03:24,620
Tout en se déplaçant à travers la partie triée de la liste de droite à gauche,

43
00:03:24,620 --> 00:03:29,160
4 est le premier numéro, nous avons vu que est plus petit que le nombre

44
00:03:29,160 --> 00:03:31,540
nous essayons d'insérer.

45
00:03:31,540 --> 00:03:35,820
Donc, maintenant nous pouvons insérer le 16 dans ce logement vide,

46
00:03:35,820 --> 00:03:40,520
qui, rappelez-vous, nous avons créé par des éléments mobiles dans la partie tri sur

47
00:03:40,520 --> 00:03:43,340
comme nous l'avons rencontrés.

48
00:03:43,340 --> 00:03:47,900
>> Très bien. Maintenant, nous avons quatre éléments triés et deux éléments non triés.

49
00:03:47,900 --> 00:03:51,600
Donc, nous allons déplacer le 8 dans la partie triée.

50
00:03:51,600 --> 00:03:55,010
Huit est inférieur à 42.

51
00:03:55,010 --> 00:03:56,940
Huit est inférieur à 23.

52
00:03:56,940 --> 00:04:00,230
Et la figure 8 est inférieure à 16.

53
00:04:00,230 --> 00:04:03,110
Mais 8 est supérieur à 4.

54
00:04:03,110 --> 00:04:07,280
Donc, nous aimerions insérer le 8 entre le 4 et le 16.

55
00:04:09,070 --> 00:04:13,650
Et maintenant nous avons juste un élément de plus à gauche pour trier - le 15.

56
00:04:13,950 --> 00:04:16,589
Quinze est inférieur à 42,

57
00:04:16,589 --> 00:04:19,130
Quinze est inférieur à 23.

58
00:04:19,130 --> 00:04:21,750
Et 15 est inférieur à 16.

59
00:04:21,750 --> 00:04:24,810
15 mais est supérieure à 8.

60
00:04:24,810 --> 00:04:27,440
>> Donc, c'est là que nous voulons faire de notre insertion finale.

61
00:04:28,770 --> 00:04:30,330
Et c'est fait.

62
00:04:30,330 --> 00:04:33,540
Nous n'avons pas plus d'éléments dans la partie non triés,

63
00:04:33,540 --> 00:04:36,670
et notre partie est triée dans l'ordre correct.

64
00:04:36,670 --> 00:04:40,270
Les nombres sont ordonnés du plus petit au plus grand.

65
00:04:40,270 --> 00:04:44,330
Donc, nous allons jeter un oeil à certains pseudo-code qui décrit les étapes que nous venons effectuées.

66
00:04:46,760 --> 00:04:51,740
>> Sur la ligne 1, nous pouvons voir que nous aurons besoin d'itérer sur chaque élément de la liste

67
00:04:51,740 --> 00:04:57,060
exception de la première, depuis le premier élément de la partie non triés deviendra tout simplement

68
00:04:57,060 --> 00:05:00,220
le premier élément de la partie triée.

69
00:05:00,220 --> 00:05:06,320
Sur les lignes 2 et 3, nous gardons une trace de notre place actuelle dans la partie non triés.

70
00:05:06,320 --> 00:05:10,450
Élément représente le nombre que nous sommes actuellement en train dans la partie triée,

71
00:05:10,450 --> 00:05:15,600
et j représente notre index dans la partie non triés.

72
00:05:15,600 --> 00:05:20,980
>> Sur la ligne 4, nous nous parcourons la partie triée de droite à gauche.

73
00:05:20,980 --> 00:05:26,010
Nous voulons arrêter l'itération une fois l'élément à gauche de notre position actuelle

74
00:05:26,010 --> 00:05:30,050
est inférieure à l'élément que nous essayons d'insérer.

75
00:05:30,050 --> 00:05:35,600
Sur la ligne 5, nous déplacer chaque élément que nous rencontrons un espace vers la droite.

76
00:05:35,600 --> 00:05:40,950
De cette façon, nous aurons un espace libre d'insérer dans quand nous trouvons le premier élément

77
00:05:40,950 --> 00:05:44,080
au moins la partie nous allons.

78
00:05:44,080 --> 00:05:50,800
Sur la ligne 6, nous mettons à jour notre comptoir de continuer à déplacer vers la gauche à travers la partie triée.

79
00:05:50,800 --> 00:05:56,860
Enfin, sur la ligne 7, nous insérer l'élément dans la partie de la liste triée.

80
00:05:56,860 --> 00:06:00,020
>> Nous savons que c'est bon d'insérer dans la position j,

81
00:06:00,020 --> 00:06:05,360
parce que nous avons déjà déplacé l'élément qui sert à être là un espace vers la droite.

82
00:06:05,360 --> 00:06:09,460
Rappelez-vous, nous allons à travers la partie triée de droite à gauche,

83
00:06:09,460 --> 00:06:13,960
mais nous avançons à travers la partie non triés de gauche à droite.

84
00:06:13,960 --> 00:06:19,090
Très bien. Jetons maintenant un coup d'oeil à la façon dont l'algorithme de longue durée qui a pris.

85
00:06:19,090 --> 00:06:25,300
Nous allons d'abord poser la question combien de temps faut-il pour que cet algorithme afin de fonctionner dans le pire des cas.

86
00:06:25,300 --> 00:06:29,040
Rappelez-vous que nous représentons cette durée avec la notation O Big.

87
00:06:32,530 --> 00:06:38,500
Afin de régler notre liste, nous avons dû parcourir les éléments dans la partie non triés,

88
00:06:38,500 --> 00:06:43,430
et pour chacun de ces éléments, éventuellement au-dessus de tous les éléments dans la partie triée.

89
00:06:43,430 --> 00:06:47,950
Intuitivement, cela ressemble à une opération O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> En regardant notre pseudo-code, nous avons une boucle imbriquée dans une autre boucle,

91
00:06:51,840 --> 00:06:55,290
qui, en effet, ressemble à une opération O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Toutefois, la partie de la liste triée ne contient pas la liste entière jusqu'à la fin.

93
00:07:01,590 --> 00:07:06,920
Pourtant, nous pourrions insérer un nouvel élément au tout début de la partie triée

94
00:07:06,920 --> 00:07:09,320
à chaque itération de l'algorithme,

95
00:07:09,320 --> 00:07:14,500
ce qui signifie que nous aurions à examiner chaque élément actuellement dans la partie triée.

96
00:07:14,500 --> 00:07:20,090
Donc, cela signifie que nous pourrions éventuellement faire une comparaison pour le deuxième élément,

97
00:07:20,090 --> 00:07:24,660
deux comparaisons pour le troisième élément, et ainsi de suite.

98
00:07:24,660 --> 00:07:32,480
Ainsi, le nombre total d'étapes est la somme des nombres entiers de 1 à la longueur de la liste moins 1.

99
00:07:32,480 --> 00:07:35,240
On peut représenter cela avec une sommation.

100
00:07:41,170 --> 00:07:47,270
>> Nous n'entrerons pas dans sommations ici, mais il s'avère que cette somme est égale à

101
00:07:47,270 --> 00:07:57,900
n (n - 1) sur 2, ce qui est équivalent ^ n 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Quand on parle d'exécution asymptotique,

103
00:08:00,800 --> 00:08:05,170
ce n ^ 2 terme va dominer ce terme n.

104
00:08:05,170 --> 00:08:11,430
Ainsi, le tri par insertion est Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Que faire si nous avons couru le tri par insertion sur une liste déjà triée.

106
00:08:16,150 --> 00:08:20,960
Dans ce cas, nous serions tout simplement mettre en place la partie triés de gauche à droite.

107
00:08:20,960 --> 00:08:25,050
Donc, nous allons seulement besoin de l'ordre de n étapes.

108
00:08:25,050 --> 00:08:29,740
>> Cela signifie que le tri par insertion a un rendement meilleur des cas de n,

109
00:08:29,740 --> 00:08:34,130
que nous représentons avec Ω (n).

110
00:08:34,130 --> 00:08:36,190
Et c'est tout pour le tri par insertion,

111
00:08:36,190 --> 00:08:40,429
juste un des nombreux algorithmes que nous pouvons utiliser pour trier la liste.

112
00:08:40,429 --> 00:08:43,210
Mon nom est Tommy, et c'est CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, vous ne pouvez pas arrêter cela une fois qu'il démarre.

115
00:09:01,620 --> 00:09:04,760
Oh, nous l'avons fait - Boom! >>