1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Вметнување Сортирај]

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
Значи, ајде сега се движи до 4, следниот елемент во несортиран дел.

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
>> Тоа значи дека ние би сакале да се одржи на 4 во првиот слот во решат дел.

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
Шеснаесет е помалку од 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, можеме да видиме дека ние ќе треба да iterate во текот секој елемент во листата

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
>> On-line 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
>> Ние знаеме дека тоа е во ред да се вметне во позиција ѕ,

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
Потсетиме дека ние ги претставуваме оваа трчање време со Биг О нотација.

87
00:06:32,530 --> 00:06:38,500
Со цел да се најде нашата листа, моравме да iterate во текот на елементи во несортиран дел,

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

89
00:06:43,430 --> 00:06:47,950
Интуитивно, ова звучи како О (n ^ 2) операција.

90
00:06:47,950 --> 00:06:51,840
>> Гледајќи нашата pseudocode, имаме јамка вгнездени внатре во јамка,

91
00:06:51,840 --> 00:06:55,290
кои, навистина, звучи како О (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 рок ќе доминираат овој n рок.

104
00:08:05,170 --> 00:08:11,430
Значи, вметнување вид е Биг О (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
Значи, ние само ќе треба на цел од n чекори.

108
00:08:25,050 --> 00:08:29,740
>> Тоа значи дека вметнување вид има најдобар случај перформанси на n,

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

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
О, ние го сторивме тоа - >> бум!