1
00:00:00,000 --> 00:00:02,826
>> [Мусиц плаиинг]

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

3
00:00:05,660 --> 00:00:09,370
>> Даг Ллоид: Дакле, убацивање врста је још један
алгоритам можемо користити за сортирање низ.

4
00:00:09,370 --> 00:00:12,350
Идеја која стоји иза овог алгоритма
је да се изгради свој сортирану низ

5
00:00:12,350 --> 00:00:19,670
у мјесту, пребацивање елементе из
начин како идете, како би направили места.

6
00:00:19,670 --> 00:00:22,240
Ово је нешто другачија
од одабира врсте или балон

7
00:00:22,240 --> 00:00:25,460
сорт, на пример, где
ми прилагођавање локације,

8
00:00:25,460 --> 00:00:26,910
где правимо свопови.

9
00:00:26,910 --> 00:00:29,760
>> У овом случају оно што уствари
раде је клизни елементи

10
00:00:29,760 --> 00:00:31,390
преко, ван пута.

11
00:00:31,390 --> 00:00:34,030
Како ово алгоритам
рад у псеудокоду?

12
00:00:34,030 --> 00:00:37,646
Па хајде да кажем да је произвољно
Први елемент низа се сортирају.

13
00:00:37,646 --> 00:00:38,770
Ми га граде на месту.

14
00:00:38,770 --> 00:00:42,660
>> Идемо један елемент у једном тренутку и
граде га, тако да је прва ствар коју видимо

15
00:00:42,660 --> 00:00:43,890
је низ један елемент.

16
00:00:43,890 --> 00:00:47,720
И по дефиницији, један
Елемент низ сортира.

17
00:00:47,720 --> 00:00:50,850
>> Онда ћемо поновити овај процес док--
ћемо поновити следећи процес

18
00:00:50,850 --> 00:00:52,900
док сви елементи су поредани.

19
00:00:52,900 --> 00:00:57,770
Поглед на следећем обичан елемент и
убаците га у сортираног део,

20
00:00:57,770 --> 00:01:01,209
померањем потребног броја
елемената од начина.

21
00:01:01,209 --> 00:01:03,750
Надам се да ово визуализација
ће вам помоћи да видите шта је

22
00:01:03,750 --> 00:01:05,980
дешава са унесени врсте.

23
00:01:05,980 --> 00:01:08,010
>> Дакле, опет, ово је наш
Читав низ мусиц,

24
00:01:08,010 --> 00:01:10,970
све елементе наведено у црвено.

25
00:01:10,970 --> 00:01:13,320
И да пратите
кораци наше псеудокоду.

26
00:01:13,320 --> 00:01:16,970
Прва ствар коју радимо, је зовемо
Први елемент низа, поредани.

27
00:01:16,970 --> 00:01:20,920
Дакле, ми смо само да рецимо
пет, ви сада поредани.

28
00:01:20,920 --> 00:01:24,570
>> Онда погледате следећи
мусиц елемент низа

29
00:01:24,570 --> 00:01:27,610
и желимо да убаците да
у сортирани део,

30
00:01:27,610 --> 00:01:29,750
померањем елемената преко.

31
00:01:29,750 --> 00:01:33,470
Дакле, два је следећа мусиц
елемент низа.

32
00:01:33,470 --> 00:01:36,250
Јасно припада пре
пет, па шта ћемо урадити

33
00:01:36,250 --> 00:01:41,580
је врста држите два одвојена за секунду,
схифт пет преко, а затим убаците два

34
00:01:41,580 --> 00:01:43,210
пре пет година, где треба да иде.

35
00:01:43,210 --> 00:01:45,280
И сада можемо рећи да су две сортира.

36
00:01:45,280 --> 00:01:48,400
>> Дакле, као што видите, имамо само сам до сада
Погледао два елемента низа.

37
00:01:48,400 --> 00:01:50,600
Ми нисмо погледали
рест уопште, али смо

38
00:01:50,600 --> 00:01:54,582
добио та два елемента поредани према
начин померање механизма.

39
00:01:54,582 --> 00:01:56,410
>> Тако смо поновите поступак поново.

40
00:01:56,410 --> 00:01:58,850
Погледајте следећи мусиц
елеменат, то је један.

41
00:01:58,850 --> 00:02:04,010
Хајде да сматрају да страну на секунд,
схифт све преко, и стави један

42
00:02:04,010 --> 00:02:05,570
где је требало да иде.

43
00:02:05,570 --> 00:02:08,110
>> Опет, ипак, само смо икада
погледао један, два и пет.

44
00:02:08,110 --> 00:02:12,480
Ми не знамо шта друго долази,
али смо поредани та три елемента.

45
00:02:12,480 --> 00:02:16,030
>> Следећа мусиц елемент је
три, па ћемо га издваја.

46
00:02:16,030 --> 00:02:18,200
Ми ћемо схифт над оним што
требају којој, овај пут

47
00:02:18,200 --> 00:02:21,820
није све као у претходна
два случаја, то је само пет.

48
00:02:21,820 --> 00:02:25,440
А онда ћемо остати у три,
између два и пет.

49
00:02:25,440 --> 00:02:27,849
>> Шест је следећи мусиц
елемент низа.

50
00:02:27,849 --> 00:02:31,140
И, у ствари шест је већа од пет, со
ми ни не треба да урадите било премештају.

51
00:02:31,140 --> 00:02:35,710
Можемо само да прикаче шест право на
крај сортирана дела.

52
00:02:35,710 --> 00:02:38,270
>> На крају, четири је
прошле мусиц елемента.

53
00:02:38,270 --> 00:02:42,060
Тако ћемо га издвојила, мијења се у
елементи треба да пређу преко,

54
00:02:42,060 --> 00:02:43,780
а затим ставите четири тамо где и припада.

55
00:02:43,780 --> 00:02:46,400
И сада изгледају, некако смо си
од свих елемената.

56
00:02:46,400 --> 00:02:48,150
Обратите пажњу са убацивањем
врста, нисмо имали

57
00:02:48,150 --> 00:02:50,240
да се вратим и назад преко низа.

58
00:02:50,240 --> 00:02:54,720
Ишли смо само преко низа
једном, а ми померио ствари

59
00:02:54,720 --> 00:02:59,870
да смо већ би наишли, како
да би се направио простор за нове елементе.

60
00:02:59,870 --> 00:03:02,820
>> Дакле, оно што је најгори случај
сценарио са уметања врстом?

61
00:03:02,820 --> 00:03:05,090
У најгорем случају,
низ је обрнутим редоследом.

62
00:03:05,090 --> 00:03:11,180
Морате да пребаци сваки од н елемената
до н позицијама, сваки пут кад

63
00:03:11,180 --> 00:03:12,880
направити уметање.

64
00:03:12,880 --> 00:03:15,720
То је много мења.

65
00:03:15,720 --> 00:03:18,014
>> У најбољем случају,
низ је савршено поредани.

66
00:03:18,014 --> 00:03:20,680
И нешто као што се догодило
са пет и шест у примјеру,

67
00:03:20,680 --> 00:03:23,779
где бисмо могли да га тацк на
без да уради било померање,

68
00:03:23,779 --> 00:03:24,820
ми у суштини би то.

69
00:03:24,820 --> 00:03:27,560
>> Ако замислите да је наш
низ је био један кроз шест,

70
00:03:27,560 --> 00:03:29,900
да кренемо са стране
проглашавајући једну сортира.

71
00:03:29,900 --> 00:03:33,300
Два долази након што је један тако да једноставно не могу
кажу, у реду, добро један и два су поредани.

72
00:03:33,300 --> 00:03:36,190
Три долази после два тако, у реду,
један и два и три су поредани.

73
00:03:36,190 --> 00:03:39,590
>> Нећемо било каквих замјену, ми смо
Само креће ову произвољна граница

74
00:03:39,590 --> 00:03:42,460
између поредани и мусиц како идемо.

75
00:03:42,460 --> 00:03:46,646
Како ефикасно као што смо урадили у примеру,
окретање елементе плаво, као што наставите.

76
00:03:46,646 --> 00:03:48,270
Дакле, оно што је најгори случај рунтиме, онда?

77
00:03:48,270 --> 00:03:51,854
Запамтите, ако морамо да пребаци сваки од
се н елемената евентуално н позиција,

78
00:03:51,854 --> 00:03:54,020
надамо се да вам даје
идеја да је најгори случај

79
00:03:54,020 --> 00:03:57,770
Рунтиме је Биг О од н на квадрат.

80
00:03:57,770 --> 00:04:00,220
>> Ако је низ савршено
поредани, све што треба да урадите

81
00:04:00,220 --> 00:04:04,480
се погледати сваког елемента
једном, а онда смо готови.

82
00:04:04,480 --> 00:04:08,440
Дакле, у најбољем случају, то је омега н.

83
00:04:08,440 --> 00:04:09,490
>> Ја сам Доуг Лојд.

84
00:04:09,490 --> 00:04:11,760
Ово је ЦС50.

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