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

2
00:00:02,290 --> 00:00:04,240
[Томи MacWilliam] [Харвардския университет]

3
00:00:04,240 --> 00:00:07,290
[Това е CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Нека да погледнем на вмъкване вид алгоритъм за вземане на списък от числа и ги сортира.

5
00:00:13,060 --> 00:00:18,300
Алгоритъм, не забравяйте, е просто стъпка по стъпка процедурата за изпълнение на дадена задача.

6
00:00:18,300 --> 00:00:23,640
Основната идея зад вмъкване вид, е да разделят нашия списък в две части,

7
00:00:23,640 --> 00:00:26,580
подредени част и несортиран част.

8
00:00:26,580 --> 00:00:29,290
>> На всяка стъпка на алгоритъма, се премества номер

9
00:00:29,290 --> 00:00:32,439
от несортиран част на сортират част

10
00:00:32,439 --> 00:00:35,680
, докато накрая на целия списък се сортират.

11
00:00:35,680 --> 00:00:43,340
Ето списъка от шест несортирани числа - 23, 42, 4, 16, 8 и 15.

12
00:00:43,340 --> 00:00:47,680
Тъй като тези номера не всички са във възходящ ред, те несортирани.

13
00:00:47,680 --> 00:00:53,890
Тъй като ние сортиране все още не са започнали, ние ще разгледаме всички шест елемента несортирани част.

14
00:00:53,890 --> 00:00:59,270
>> След като започнете сортиране, ние ще поставим тези сортирани номера в ляво от тях.

15
00:00:59,270 --> 00:01:03,600
Така че, нека започнем с 23, първият елемент в нашия списък.

16
00:01:03,600 --> 00:01:06,930
Ние все още не разполагат с никакви елементи в сортирали част,

17
00:01:06,930 --> 00:01:12,460
така че нека да разгледа 23 за начало и край на сортирали част.

18
00:01:12,460 --> 00:01:16,510
Сега, нашата подредени част има един номер, 23,

19
00:01:16,510 --> 00:01:20,260
и нашата несортирани част има тези пет числа.

20
00:01:20,260 --> 00:01:27,320
Нека сега поставете следващия номер несортирани нашата част, 42, в сортират част.

21
00:01:27,320 --> 00:01:35,930
>> За да направите това, ние ще трябва да се сравни от 42 до 23 - единственият елемент в сортирали част досега.

22
00:01:35,930 --> 00:01:41,980
Четиридесет и две е по-голям от 23, така че може просто да добавите 42 до края

23
00:01:41,980 --> 00:01:45,420
подредени част от списъка. Чудесно!

24
00:01:45,420 --> 00:01:51,850
Сега нашата подредени част има два елемента, и несортирани нашата част има четири елемента.

25
00:01:51,850 --> 00:01:57,200
Така че, нека сега се движат на четири, следващият елемент в несортиран част.

26
00:01:57,200 --> 00:02:00,230
Така че, когато това трябва да бъде поставен в сортират част?

27
00:02:00,230 --> 00:02:04,220
>> Не забравяйте, че ние искаме да се постави този номер в сортират за

28
00:02:04,220 --> 00:02:08,680
така че нашата подредени част остава правилно подредени по всяко време.

29
00:02:08,680 --> 00:02:14,380
Ако ние поставяме от 4 до правото на 42, а след това в нашия списък ще бъде в ред.

30
00:02:14,380 --> 00:02:18,380
Така че, нека да продължи да се движи отдясно-наляво в нашия вид част.

31
00:02:18,380 --> 00:02:23,260
Като се движим, да смени всеки номер за определяне на място, за да направи място за новия номер.

32
00:02:25,440 --> 00:02:31,740
Добре, 4 също е по-малко от 23, така че не можем да го поставите тук.

33
00:02:31,740 --> 00:02:34,480
Нека преминем 23 правото на едно място.

34
00:02:36,500 --> 00:02:43,120
>> Това означава, че ние бихме искали да поставите четири в първия слот в сортират част.

35
00:02:43,120 --> 00:02:46,300
Забележете как това пространство в списъка вече е празна,

36
00:02:46,300 --> 00:02:51,120
защото сме се движи сортирани елементи, както сме ги срещали.

37
00:02:51,120 --> 00:02:52,740
Добре. Така че, ние сме по средата там.

38
00:02:52,740 --> 00:02:57,990
Нека продължим нашия алгоритъм чрез вмъкване на 16 в сортират част.

39
00:02:59,260 --> 00:03:03,820
Sixteen е по-малко от 42, така че нека прехвърли 42 надясно.

40
00:03:05,700 --> 00:03:10,190
Шестнадесет също е по-малко от 23, така че нека да измести този елемент.

41
00:03:11,790 --> 00:03:20,820
>> Сега, 16 години е по-голяма от 4. Така че, изглежда, че ние бихме искали да вкарате 16 между 4 и 23.

42
00:03:20,820 --> 00:03:24,620
Докато се движат през сортират част на списъка от дясно на ляво,

43
00:03:24,620 --> 00:03:29,160
4 е първото число сме виждали, че е по-малък от броя

44
00:03:29,160 --> 00:03:31,540
ние се опитваме да вмъкнете.

45
00:03:31,540 --> 00:03:35,820
Така че, сега можем да вмъкнете 16 в този празен слот,

46
00:03:35,820 --> 00:03:40,520
които, не забравяйте, ние сме създали от движещи се елементи в нещо част

47
00:03:40,520 --> 00:03:43,340
както сме ги срещали.

48
00:03:43,340 --> 00:03:47,900
>> Добре. Сега имаме четири сортирани елемента и два несортирани елементи.

49
00:03:47,900 --> 00:03:51,600
Така че, нека да преминем 8 в сортират част.

50
00:03:51,600 --> 00:03:55,010
Осем е по-малко от 42.

51
00:03:55,010 --> 00:03:56,940
Осем е по-малко от 23.

52
00:03:56,940 --> 00:04:00,230
И 8 е по-малко от 16.

53
00:04:00,230 --> 00:04:03,110
Но 8 е по-голяма от 4.

54
00:04:03,110 --> 00:04:07,280
Така че, ние бихме искали да вмъкнете 8 между 4 и 16.

55
00:04:09,070 --> 00:04:13,650
И сега ние просто трябва още един оставяли елемент да сортирате - 15.

56
00:04:13,950 --> 00:04:16,589
Петнадесет е по-малко от 42,

57
00:04:16,589 --> 00:04:19,130
Петнадесет е по-малко от 23.

58
00:04:19,130 --> 00:04:21,750
И 15 е по-малко от 16.

59
00:04:21,750 --> 00:04:24,810
Но 15 е по-голяма от 8.

60
00:04:24,810 --> 00:04:27,440
>> Така че, тук е мястото, където ние искаме да направим нашата крайна вмъкване.

61
00:04:28,770 --> 00:04:30,330
И сме готови.

62
00:04:30,330 --> 00:04:33,540
Ние не разполагаме с повече елементи в несортиран част,

63
00:04:33,540 --> 00:04:36,670
и нашата подредени част е в правилния ред.

64
00:04:36,670 --> 00:04:40,270
Числата са подредени от най-малките до най-големите.

65
00:04:40,270 --> 00:04:44,330
Така че, нека да разгледаме някои pseudocode, която описва стъпките, които току-що са извършили.

66
00:04:46,760 --> 00:04:51,740
>> На ред 1, можем да видим, че ние ще трябва да обхождане на всеки елемент в списъка

67
00:04:51,740 --> 00:04:57,060
с изключение на първата, тъй като първият елемент в несортиран част просто ще стане

68
00:04:57,060 --> 00:05:00,220
първият елемент в сортират част.

69
00:05:00,220 --> 00:05:06,320
На линии 2 и 3, ние сме следене на нашето място в несортиран част.

70
00:05:06,320 --> 00:05:10,450
Елемент представлява номер, с който в момента се движат в сортират част,

71
00:05:10,450 --> 00:05:15,600
и к представлява нашия индекс в несортиран част.

72
00:05:15,600 --> 00:05:20,980
>> На ред 4, ние сме итерации през подредени част от дясно на ляво.

73
00:05:20,980 --> 00:05:26,010
Искаме да спрем итерации веднъж елемента в ляво на настоящата си позиция

74
00:05:26,010 --> 00:05:30,050
е по-малко от елемент, който ние се опитваме да вмъкнете.

75
00:05:30,050 --> 00:05:35,600
На линия 5, преместване всеки елемент се сблъскваме с едно място в дясно.

76
00:05:35,600 --> 00:05:40,950
По този начин, когато намерим първия елемент, ще имаме свободно пространство, за да вмъкнете в

77
00:05:40,950 --> 00:05:44,080
по-малко от елемент, който ние се движим.

78
00:05:44,080 --> 00:05:50,800
На линия 6, ние сме актуализиране на нашите брояч, за да продължи да се движи наляво през сортират част.

79
00:05:50,800 --> 00:05:56,860
И накрая, по линия 7, ние сме вмъкване на елемент в сортират част на списъка.

80
00:05:56,860 --> 00:06:00,020
>> Ние знаем, че е добре да поставите в позиция J,

81
00:06:00,020 --> 00:06:05,360
защото вече сме преместили елемент, който да бъде използван там един пространството дясно.

82
00:06:05,360 --> 00:06:09,460
Не забравяйте, че ние се движим през подредени част от дясно на ляво,

83
00:06:09,460 --> 00:06:13,960
но ние се движим през несортиран част от ляво на дясно.

84
00:06:13,960 --> 00:06:19,090
Добре. Нека сега да видим колко дълго работи с този алгоритъм взе.

85
00:06:19,090 --> 00:06:25,300
Ще първо да си зададем въпроса колко време е необходимо, за този алгоритъм, за да се движи в най-лошия случай.

86
00:06:25,300 --> 00:06:29,040
Спомнете си, че ние представляваме това време на работа с Big O нотация.

87
00:06:32,530 --> 00:06:38,500
За да се оправи в нашия списък, имахме за обхождане на елементите в несортиран част,

88
00:06:38,500 --> 00:06:43,430
и за всеки от тези елементи, потенциално над всички елементи в сортират част.

89
00:06:43,430 --> 00:06:47,950
Интуитивно, това звучи като O (N ^ 2) експлоатация.

90
00:06:47,950 --> 00:06:51,840
>> Търсите в нашия pseudocode, имаме една линия, вложени в друг цикъл,

91
00:06:51,840 --> 00:06:55,290
, които наистина звучи като O (N ^ 2) експлоатация.

92
00:06:55,290 --> 00:07:01,590
Въпреки това, подредени част от списък не съдържа целия списък до самия край.

93
00:07:01,590 --> 00:07:06,920
Все пак, ние потенциално биха могли да вмъкнете нов елемент в самото начало на подредени част

94
00:07:06,920 --> 00:07:09,320
на всяка итерация на алгоритъма,

95
00:07:09,320 --> 00:07:14,500
което означава, че ние ще трябва да разгледаме всеки елемент в момента подредени част.

96
00:07:14,500 --> 00:07:20,090
Така че, това означава, че ние може потенциално да направи едно сравнение за втори елемент,

97
00:07:20,090 --> 00:07:24,660
две сравнения за третия елемент, и така нататък.

98
00:07:24,660 --> 00:07:32,480
Така, общият брой на стъпките е сумата на числата от 1 до дължината на списъка минус 1.

99
00:07:32,480 --> 00:07:35,240
Ние може да представлява това с сумиране.

100
00:07:41,170 --> 00:07:47,270
>> Ние няма да отидат в summations тук, но се оказва, че това сумиране е равна на

101
00:07:47,270 --> 00:07:57,900
N (N - 1) над 2, което е еквивалентно N ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
Когато говорим за асимптотичната по време на работа,

103
00:08:00,800 --> 00:08:05,170
този N ^ 2 план ще да доминират тази н мандат.

104
00:08:05,170 --> 00:08:11,430
Така че, вмъкване вид е Big O (N ^ 2).

105
00:08:11,430 --> 00:08:16,150
Какво ще стане, ако ние се завтече вмъкване вид на вече сортиран списък.

106
00:08:16,150 --> 00:08:20,960
В този случай, ние просто ще изгради подредени част от ляво на дясно.

107
00:08:20,960 --> 00:08:25,050
Така че, ние ще трябва само по нареждане на стъпките н.

108
00:08:25,050 --> 00:08:29,740
>> Това означава, че включването вид има най-добрия случай изпълнението на N,

109
00:08:29,740 --> 00:08:34,130
, които ние представляваме с Ω (N).

110
00:08:34,130 --> 00:08:36,190
И това е за поставяне вид,

111
00:08:36,190 --> 00:08:40,429
само един от многото алгоритми можем да използваме, за да сортирате списъка.

112
00:08:40,429 --> 00:08:43,210
Моето име е Томи, и това е CS50.

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

114
00:08:46,110 --> 00:08:49,230
О, ти просто не може да спре, че след като тя започва.

115
00:09:01,620 --> 00:09:04,760
О, ние сме го направили - >> Boom!