1
00:00:00,000 --> 00:00:03,360
>> [Музички]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
Даг LLOYD: Добро, така
меур вид е алгоритам

4
00:00:06,730 --> 00:00:08,730
можете да го користите да се најде решение е збир на елементи.

5
00:00:08,730 --> 00:00:10,850
Ајде да ги разгледаме во тоа како таа работи.

6
00:00:10,850 --> 00:00:13,240
>> Значи основната идеја зад
меур вид е ова.

7
00:00:13,240 --> 00:00:17,340
Ние генерално сакаат да се движат повисоки
ценети елементи генерално на правото,

8
00:00:17,340 --> 00:00:20,340
и пониски ценети елементи општо
од лево, како што би се очекувало.

9
00:00:20,340 --> 00:00:23,256
Сакаме долниот работи кои треба да бидат на
на почетокот, а на повисоките работи

10
00:00:23,256 --> 00:00:24,970
да биде на крајот.

11
00:00:24,970 --> 00:00:26,130
>> Како го правиме тоа?

12
00:00:26,130 --> 00:00:28,040
Добро во pseudocode код,
може да се каже, ајде

13
00:00:28,040 --> 00:00:30,320
постави трампа спротивност со не-нулта вредност.

14
00:00:30,320 --> 00:00:32,570
Ќе видиме зошто го правиме тоа во една секунда.

15
00:00:32,570 --> 00:00:36,090
А потоа се повторува на следниве
процесот до шанкот трампа е 0,

16
00:00:36,090 --> 00:00:39,910
или додека ние не правиме никакви свопови на сите.

17
00:00:39,910 --> 00:00:43,170
>> Ресетирате трампа спротивни
0 ако тоа не е веќе 0.

18
00:00:43,170 --> 00:00:46,420
Потоа да се погледне во секој
соседен пар од елементи.

19
00:00:46,420 --> 00:00:49,550
Ако овие два елементи се
не е во ред, ги трампа,

20
00:00:49,550 --> 00:00:51,620
и додадете 1 до шалтер трампа.

21
00:00:51,620 --> 00:00:53,870
Ако сте размислување за
ова пред да се визуелизира,

22
00:00:53,870 --> 00:00:57,471
забележи дека ова ќе се движи пониско
ценети елементи од лево

23
00:00:57,471 --> 00:01:00,720
и високо ценети елементи на правото,
ефикасно да се прави она што ние сакаме да го направи тоа,

24
00:01:00,720 --> 00:01:03,940
кој е се движи оние групи
на елементите на тој начин.

25
00:01:03,940 --> 00:01:07,035
Ајде да се визуелизира како оваа
Може да се погледне за користење на нашата низа

26
00:01:07,035 --> 00:01:10,504
дека ние се користи за тестирање
на овие алгоритми.

27
00:01:10,504 --> 00:01:13,420
Имаме несортиран низа овде, повторно,
означена со сите елементи

28
00:01:13,420 --> 00:01:14,840
да се биде во црвена боја.

29
00:01:14,840 --> 00:01:17,970
И јас во собата ми трампа контра
на нула вредност.

30
00:01:17,970 --> 00:01:20,610
Јас произволно одбрав
негативни 1-- тоа не е 0.

31
00:01:20,610 --> 00:01:23,840
Ние сакаме да се повтори овој процес
до шанкот трампа е 0.

32
00:01:23,840 --> 00:01:26,540
Ова е причината зошто јас во собата ми трампа
спротивно на некои не-нулта вредност,

33
00:01:26,540 --> 00:01:29,400
бидејќи во спротивно на
swap противвредност ќе биде 0.

34
00:01:29,400 --> 00:01:31,610
Ние дури и не ќе започне
процесот на алгоритмот.

35
00:01:31,610 --> 00:01:33,610
Значи, повторно, чекорите are--
ресетирате бројачот за размена

36
00:01:33,610 --> 00:01:37,900
на 0, а потоа погледнете во секој соседни
пар, а ако тие се на ред,

37
00:01:37,900 --> 00:01:40,514
ги трампа, и додадете 1
на шалтер трампа.

38
00:01:40,514 --> 00:01:41,680
Значи, да се започне овој процес.

39
00:01:41,680 --> 00:01:44,430
Така првото нешто што го правиме е
ние во собата на шалтер трампа на 0,

40
00:01:44,430 --> 00:01:46,660
а потоа и да се свртиме
во секој соседен пар.

41
00:01:46,660 --> 00:01:49,140
>> Па ние прво почнете да барате во 5 и 2.

42
00:01:49,140 --> 00:01:52,410
Гледаме дека тие се надвор од
порачате и да можеме да ги трампа.

43
00:01:52,410 --> 00:01:53,830
И се додаваат 1 до шанкот трампа.

44
00:01:53,830 --> 00:01:57,860
Па сега нашите трампа контра е 1,
и 2 и 5 се вклучи.

45
00:01:57,860 --> 00:01:59,370
Сега ние се повторува процесот повторно.

46
00:01:59,370 --> 00:02:03,540
>> Ние гледаме на следниот соседен пар,
5 и 1-- тие се, исто така, на ред,

47
00:02:03,540 --> 00:02:06,960
па ние да ги разменуваат и да додадете
1 до шанкот трампа.

48
00:02:06,960 --> 00:02:08,900
Потоа ќе погледнеме во 5 и 3.

49
00:02:08,900 --> 00:02:13,830
Тие се на ред, па ние се разменуваат
нив и ние додадете 1 до шалтер трампа.

50
00:02:13,830 --> 00:02:15,550
Потоа ќе погледнеме во 5 и 6.

51
00:02:15,550 --> 00:02:18,630
Тие се во ред, па ние всушност не
треба да се разменуваат ништо тоа време.

52
00:02:18,630 --> 00:02:20,250
Потоа ќе погледнеме во 6 и 4.

53
00:02:20,250 --> 00:02:24,920
Тие се, исто така, на ред, па ние се разменуваат
нив и ние додадете 1 до шалтер трампа.

54
00:02:24,920 --> 00:02:26,230
>> Сега се забележи она што се случи.

55
00:02:26,230 --> 00:02:29,514
Ние се пресели 6 па се до крајот.

56
00:02:29,514 --> 00:02:32,180
Така што во вид избор, ако сте
види дека видео, она што го направив беше

57
00:02:32,180 --> 00:02:35,290
ние заврши со поместување на
Најмалата елементи во градењето

58
00:02:35,290 --> 00:02:39,640
сортирани низа суштински од
лево кон десно, најмалите до најголемите.

59
00:02:39,640 --> 00:02:43,200
Во случај на меур вид, ако ние сме
следува по ова конкретно алгоритам,

60
00:02:43,200 --> 00:02:46,720
ние сме всушност ќе треба да се гради
сортирани низа од десно

61
00:02:46,720 --> 00:02:49,100
кон лево, најголемиот до најмалиот.

62
00:02:49,100 --> 00:02:53,840
Имаме ефикасно клобуркаше 6,
Најголемата вредност, по целиот пат до крај.

63
00:02:53,840 --> 00:02:56,165
>> Па сега можеме да се изјасни
дека тоа е сортирана,

64
00:02:56,165 --> 00:02:59,130
и во иднина iterations--
минува низ низа again--

65
00:02:59,130 --> 00:03:01,280
ние не треба да се разгледа 6 повеќе.

66
00:03:01,280 --> 00:03:03,850
Ние само треба да се разгледа
на несортиран елементи

67
00:03:03,850 --> 00:03:06,299
кога ние сме во потрага на соседните парови.

68
00:03:06,299 --> 00:03:08,340
Па ние имаат завршено еден
поминат низ меур вид.

69
00:03:08,340 --> 00:03:11,941
Па сега ние се вратиме на прашањето,
Повторете се додека шалтер трампа е 0.

70
00:03:11,941 --> 00:03:13,690
И контра трампа
е 4, па ние ќе

71
00:03:13,690 --> 00:03:15,410
да ги повторува овој процес повторно.

72
00:03:15,410 --> 00:03:19,180
>> Ние ќе треба да го ресетирате бројачот за размена
на 0, и се погледне во секој соседен пар.

73
00:03:19,180 --> 00:03:21,890
За да можеме да започнат со 2 и 1-- тие се
на ред, за да можеме да ги трампа

74
00:03:21,890 --> 00:03:23,620
и се додаваат 1 до шанкот трампа.

75
00:03:23,620 --> 00:03:25,490
2 и 3, тие се во ред.

76
00:03:25,490 --> 00:03:27,060
Ние не треба да се направи нешто.

77
00:03:27,060 --> 00:03:28,420
3 и 5 се во ред.

78
00:03:28,420 --> 00:03:30,150
Ние не треба да се направи нешто таму.

79
00:03:30,150 --> 00:03:32,515
>> 5 и 4, тие се надвор
на ред, и така ние

80
00:03:32,515 --> 00:03:35,130
треба да ги разменуваат и да додадете
1 до шанкот трампа.

81
00:03:35,130 --> 00:03:38,880
И сега ние се пресели 5,
следниот најголемиот елемент,

82
00:03:38,880 --> 00:03:40,920
до крајот на несортиран дел.

83
00:03:40,920 --> 00:03:44,360
Па сега можеме да го наречеме дека
дел од подредени дел.

84
00:03:44,360 --> 00:03:47,180
>> Сега сте во потрага по
екран и веројатно може да се каже,

85
00:03:47,180 --> 00:03:50,130
како може јас, дека низата
е сортирана во моментов.

86
00:03:50,130 --> 00:03:51,820
Но, ние не може да докаже дека сеуште.

87
00:03:51,820 --> 00:03:54,359
Ние немаме гаранција
дека тоа се подредени.

88
00:03:54,359 --> 00:03:56,900
Но, ова е местото каде што на swap
противвредност ќе влезе во игра.

89
00:03:56,900 --> 00:03:59,060
>> Значи ние сме завршиле помине.

90
00:03:59,060 --> 00:04:00,357
Противвредност трампа е 2.

91
00:04:00,357 --> 00:04:02,190
Па ние ќе треба да се повтори
овој процес повторно,

92
00:04:02,190 --> 00:04:04,290
Повторете се додека шалтер трампа е 0.

93
00:04:04,290 --> 00:04:05,550
Ресетирање на бројачите трампа на 0.

94
00:04:05,550 --> 00:04:06,820
Па ние ќе го ресетирате.

95
00:04:06,820 --> 00:04:09,810
>> Сега гледам на секој соседен пар.

96
00:04:09,810 --> 00:04:11,880
Тоа е во ред, 1 и 2.

97
00:04:11,880 --> 00:04:13,590
2 и 3 се во ред.

98
00:04:13,590 --> 00:04:15,010
3 и 4 се во ред.

99
00:04:15,010 --> 00:04:19,250
Па во овој момент, известување ќе завршиме
гледа во секој соседен пар,

100
00:04:19,250 --> 00:04:22,530
но контра своп се уште е 0.

101
00:04:22,530 --> 00:04:25,520
>> Ако ние не треба да се префрлите
било какви елементи, а потоа тие

102
00:04:25,520 --> 00:04:28,340
мора да биде во ред, од страна на
врз основа на овој процес.

103
00:04:28,340 --> 00:04:32,000
И така на ефикасност на сорти,
дека ние компјутерски научници сакам,

104
00:04:32,000 --> 00:04:35,560
сега можеме да се изјасни
целата низа мора

105
00:04:35,560 --> 00:04:38,160
се решат, бидејќи ние не
мора да ги замените било елементи.

106
00:04:38,160 --> 00:04:40,380
Тоа е прилично убаво.

107
00:04:40,380 --> 00:04:43,260
>> Значи, што е најлош случај
сценарио меур вид?

108
00:04:43,260 --> 00:04:46,240
Во најлош случај низата е
во сосема обратен редослед,

109
00:04:46,240 --> 00:04:49,870
и така што мораме да секој меур
на големите елементи сите

110
00:04:49,870 --> 00:04:51,780
пат низ низа.

111
00:04:51,780 --> 00:04:55,350
И ние, исто така, мора да се ефикасно
меур сите мали елементи назад

112
00:04:55,350 --> 00:04:57,050
целиот пат низ низа, исто така.

113
00:04:57,050 --> 00:05:01,950
Па секој од n елементи треба да се движи
во сите на други n елементи.

114
00:05:01,950 --> 00:05:04,102
Значи тоа е најлошото сценарио.

115
00:05:04,102 --> 00:05:05,810
Во најдобар случај
сценарио иако, ова е

116
00:05:05,810 --> 00:05:07,880
малку поинаков од селекција вид.

117
00:05:07,880 --> 00:05:10,040
Низата е веќе
подредени кога одиме во.

118
00:05:10,040 --> 00:05:12,550
Ние не треба да направите било какви
размена на првиот помине.

119
00:05:12,550 --> 00:05:14,940
Значи, ние можеби ќе мора да се погледне
на помалку елементи, нели?

120
00:05:14,940 --> 00:05:18,580
Ние не треба да се повтори овој
процесира голем број на пати.

121
00:05:18,580 --> 00:05:19,540
>> Значи она што значи тоа?

122
00:05:19,540 --> 00:05:22,390
Значи, што е најлошото сценарио
балон за вид, а она што е

123
00:05:22,390 --> 00:05:25,330
најдобро сценарио за меур вид?

124
00:05:25,330 --> 00:05:27,770
Ми го погоди ова?

125
00:05:27,770 --> 00:05:32,420
Во најлош случај ќе мора да iterate
во сите n елементи n пати.

126
00:05:32,420 --> 00:05:34,220
Па најлош случај е N на квадрат.

127
00:05:34,220 --> 00:05:36,550
>> Ако низата е совршено
сортирани иако, само

128
00:05:36,550 --> 00:05:38,580
мора да се погледне во секој
на елементите еднаш.

129
00:05:38,580 --> 00:05:42,670
И ако контра своп се уште е 0,
може да се каже оваа низа е сортирана.

130
00:05:42,670 --> 00:05:45,780
И така во најдобар случај, ова е
всушност подобра од селекцијата

131
00:05:45,780 --> 00:05:49,230
sort-- тоа е омега на n.

132
00:05:49,230 --> 00:05:50,270
>> Јас сум Даг Лојд.

133
00:05:50,270 --> 00:05:52,140
Ова е CS50.

134
00:05:52,140 --> 00:05:54,382