1
00:00:00,000 --> 00:00:02,826
>> [Jouer de la musique]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Donc, le tri par insertion est un autre
algorithme nous pouvons utiliser pour trier un tableau.

4
00:00:09,370 --> 00:00:12,350
L'idée derrière cet algorithme
est de construire votre tableau trié

5
00:00:12,350 --> 00:00:19,670
en place, déplacer des éléments sur
la façon que vous allez, pour faire place.

6
00:00:19,670 --> 00:00:22,240
Ce chiffre est légèrement différente
de sorte de sélection ou la bulle

7
00:00:22,240 --> 00:00:25,460
trier, par exemple, où
nous ajustons les emplacements,

8
00:00:25,460 --> 00:00:26,910
où nous faisons des swaps.

9
00:00:26,910 --> 00:00:29,760
>> Dans ce cas, ce que nous sommes en fait
faire est éléments coulissants

10
00:00:29,760 --> 00:00:31,390
plus, hors de la voie.

11
00:00:31,390 --> 00:00:34,030
Comment fonctionne cet algorithme
travailler en pseudo?

12
00:00:34,030 --> 00:00:37,646
Eh bien, laissez simplement de dire que l'arbitraire
le premier élément de tableau est trié.

13
00:00:37,646 --> 00:00:38,770
Nous construisons en place.

14
00:00:38,770 --> 00:00:42,660
>> Nous allons aller un élément à la fois et
construire, et donc la première chose que nous voyons

15
00:00:42,660 --> 00:00:43,890
est un tableau d'un élément.

16
00:00:43,890 --> 00:00:47,720
Et par définition, un un
élément tableau est trié.

17
00:00:47,720 --> 00:00:50,850
>> Ensuite, nous allons répéter ce processus until--
nous répétons le processus suivant

18
00:00:50,850 --> 00:00:52,900
jusqu'à ce que tous les éléments sont classés.

19
00:00:52,900 --> 00:00:57,770
Regardez le prochain élément non triés et
insérer dans la partie triés,

20
00:00:57,770 --> 00:01:01,209
en décalant le nombre requis
d'éléments sur le chemin.

21
00:01:01,209 --> 00:01:03,750
Espérons que cette visualisation
vous aidera à voir exactement ce qui est

22
00:01:03,750 --> 00:01:05,980
passe avec le tri par insertion.

23
00:01:05,980 --> 00:01:08,010
>> Encore une fois, voici notre
ensemble du réseau non triés,

24
00:01:08,010 --> 00:01:10,970
tous les éléments indiqués en rouge.

25
00:01:10,970 --> 00:01:13,320
Et nous allons suivre la
étapes de notre pseudo.

26
00:01:13,320 --> 00:01:16,970
La première chose que nous faisons, est que nous appelons le
premier élément du tableau, triés.

27
00:01:16,970 --> 00:01:20,920
Donc, nous sommes juste vas dire
cinq ans, vous êtes maintenant triés.

28
00:01:20,920 --> 00:01:24,570
>> Ensuite, nous regardons à la prochaine
élément non triés du tableau

29
00:01:24,570 --> 00:01:27,610
et nous voulons insérer ce
dans la partie triés,

30
00:01:27,610 --> 00:01:29,750
en déplaçant les éléments sur.

31
00:01:29,750 --> 00:01:33,470
Donc deux est la prochaine non triés
élément du tableau.

32
00:01:33,470 --> 00:01:36,250
Il est clair qu'il appartient avant le
cinq, donc ce que nous allons faire

33
00:01:36,250 --> 00:01:41,580
est une sorte de tenir deux de côté pour un deuxième,
décaler cinq de plus, puis insérez deux

34
00:01:41,580 --> 00:01:43,210
avant cinq, où devrait aller.

35
00:01:43,210 --> 00:01:45,280
Et maintenant, nous pouvons dire que deux est trié.

36
00:01:45,280 --> 00:01:48,400
>> Donc, comme vous pouvez le voir, nous avons seulement jusqu'à présent
regardé deux éléments du tableau.

37
00:01:48,400 --> 00:01:50,600
Nous avons pas regardé le
repos à tous, mais nous avons

38
00:01:50,600 --> 00:01:54,582
a obtenu ces deux éléments classés par
le moyen de mécanisme de déplacement.

39
00:01:54,582 --> 00:01:56,410
>> Donc, nous le répétons à nouveau le processus.

40
00:01:56,410 --> 00:01:58,850
Regardez la prochaine non triés
élément, qui est un.

41
00:01:58,850 --> 00:02:04,010
Tenons cela de côté pour un deuxième,
décaler tout fini, et mettre un

42
00:02:04,010 --> 00:02:05,570
où il doit aller.

43
00:02:05,570 --> 00:02:08,110
>> Encore une fois, encore, nous avons seulement jamais
regardé un, deux et cinq.

44
00:02:08,110 --> 00:02:12,480
Nous ne savons pas quoi d'autre est à venir,
mais nous avons trié ces trois éléments.

45
00:02:12,480 --> 00:02:16,030
>> Suivant élément non triés est
trois, nous allons donc le mettre de côté.

46
00:02:16,030 --> 00:02:18,200
Nous déplaçons sur ce que nous
besoin à qui, cette fois,

47
00:02:18,200 --> 00:02:21,820
est pas tout comme dans le précédent
deux cas, il est juste cinq.

48
00:02:21,820 --> 00:02:25,440
Et puis, nous nous en tiendrons à trois,
entre les deux et cinq.

49
00:02:25,440 --> 00:02:27,849
>> Six est le prochain non triés
élément au tableau.

50
00:02:27,849 --> 00:02:31,140
Et en fait six est supérieur à cinq, afin
on n'a même pas besoin de faire une permutation.

51
00:02:31,140 --> 00:02:35,710
Nous pouvons simplement virer à droite sur six
l'extrémité de la partie triés.

52
00:02:35,710 --> 00:02:38,270
>> Enfin, quatre est le
dernier élément non triés.

53
00:02:38,270 --> 00:02:42,060
Donc, nous allons le mettre de côté, changement au cours du
les éléments que nous avons besoin de passer plus,

54
00:02:42,060 --> 00:02:43,780
et ensuite mettre à quatre où il appartient.

55
00:02:43,780 --> 00:02:46,400
Et maintenant, regardez, nous avons en quelque sorte
de tous les éléments.

56
00:02:46,400 --> 00:02:48,150
Remarquez avec insertion
Trier, nous ne disposions pas

57
00:02:48,150 --> 00:02:50,240
pour aller d'avant en arrière à travers la matrice.

58
00:02:50,240 --> 00:02:54,720
Nous n'y sommes allés à travers la matrice
un moment, et nous avons déplacé les choses

59
00:02:54,720 --> 00:02:59,870
que nous avions déjà rencontré, dans l'ordre
pour faire place à des nouveaux éléments.

60
00:02:59,870 --> 00:03:02,820
>> Alors, quel est le pire des cas
scénario avec le tri par insertion?

61
00:03:02,820 --> 00:03:05,090
Dans le pire des cas, le
tableau est dans l'ordre inverse.

62
00:03:05,090 --> 00:03:11,180
Vous avez à déplacer chacun des n éléments
jusqu'à n positions, chaque fois que nous avons de

63
00:03:11,180 --> 00:03:12,880
faire une insertion.

64
00:03:12,880 --> 00:03:15,720
Cela fait beaucoup de décalage.

65
00:03:15,720 --> 00:03:18,014
>> Dans le meilleur des cas, la
tableau est parfaitement réglé.

66
00:03:18,014 --> 00:03:20,680
Et un peu comme ce qui est arrivé
avec cinq et six dans l'exemple,

67
00:03:20,680 --> 00:03:23,779
où nous ne pouvions tout simplement virer sur
sans avoir à faire tout déplacement,

68
00:03:23,779 --> 00:03:24,820
nous avions essentiellement le faisons.

69
00:03:24,820 --> 00:03:27,560
>> Si vous imaginez que notre
tableau était de un à six,

70
00:03:27,560 --> 00:03:29,900
nous serions commençons par
déclarant l'un est triée.

71
00:03:29,900 --> 00:03:33,300
Deux vient après un si nous pouvons simplement
dire, OK, bien un et deux sont triés.

72
00:03:33,300 --> 00:03:36,190
Trois vient après deux oui, OK,
un et deux et trois sont triés.

73
00:03:36,190 --> 00:03:39,590
>> Nous ne faisons pas des swaps, nous sommes
de transférer cette ligne arbitraire

74
00:03:39,590 --> 00:03:42,460
triés et non triés entre que nous allons.

75
00:03:42,460 --> 00:03:46,646
Aussi efficacement que nous l'avons fait dans l'exemple,
éléments virer au bleu, que nous procédons.

76
00:03:46,646 --> 00:03:48,270
Alors, quel est le pire des cas d'exécution, alors?

77
00:03:48,270 --> 00:03:51,854
Rappelez-vous, si nous devons passer chacun des
les n éléments éventuellement n positions,

78
00:03:51,854 --> 00:03:54,020
Espérons que cela vous donne
une idée que le pire des cas

79
00:03:54,020 --> 00:03:57,770
runtime est de Big O n carré.

80
00:03:57,770 --> 00:04:00,220
>> Si le tableau est parfaitement
trié, tout ce que nous avons à faire

81
00:04:00,220 --> 00:04:04,480
est de regarder chaque élément
une fois, et puis nous avons terminé.

82
00:04:04,480 --> 00:04:08,440
Donc, dans le meilleur des cas, il est l'oméga de n.

83
00:04:08,440 --> 00:04:09,490
>> Je suis Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Ceci est CS50.

85
00:04:11,760 --> 00:04:13,119