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
>> Дъг LLOYD: Така сортиране чрез вмъкване е друг
алгоритъм можем да използваме, за да сортирате масив.

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
>> След това ще се повтаря този процес until--
ние ще се повтори след процеса

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
>> Six е следващата несортирани
елемент на масива.

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
Две идва след една, така че ние може просто
казват, OK, и едно и две са подредени.

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

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
Времето за автономна работа Big O на п квадрат.

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
Това е CS50.

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