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

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[Ito ay CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Natin ang isang pagtingin sa pagpapasok ng-uuri, isang algorithm para sa paglalaan ng isang listahan ng mga numero at pag-uuri-uri ang mga ito.

5
00:00:13,060 --> 00:00:18,300
Isang algorithm, tandaan, simpleng step-by-step na pamamaraan para sa accomplishing isang gawain.

6
00:00:18,300 --> 00:00:23,640
Ang pangunahing ideya sa likod ng pagpapasok ng-uuri, ay hatiin ang aming listahan sa dalawang bahagi,

7
00:00:23,640 --> 00:00:26,580
isang pinagsunod-sunod na bahagi at unsorted bahagi.

8
00:00:26,580 --> 00:00:29,290
>> Sa bawat hakbang ng algorithm, ang bilang ay inilipat

9
00:00:29,290 --> 00:00:32,439
mula sa unsorted bahagi sa pinagsunod-sunod bahagi

10
00:00:32,439 --> 00:00:35,680
hanggang sa kalaunan ang buong listahan ay pinagsunod-sunod.

11
00:00:35,680 --> 00:00:43,340
Narito ang listahan ng anim unsorted numero - 23, 42, 4, 16, 8, at 15.

12
00:00:43,340 --> 00:00:47,680
Dahil ang mga numero ay hindi lahat sa pataas na pagkakasunod-sunod, sila ay unsorted.

13
00:00:47,680 --> 00:00:53,890
Dahil hindi pa namin na nagsimula ang pag-uuri-uri pa, makikita namin isaalang-alang ang lahat ng anim na mga elemento sa aming unsorted bahagi.

14
00:00:53,890 --> 00:00:59,270
>> Sa sandaling simulan namin ang pag-uuri-uri, maglalagay kami ng mga pinagsunod-sunod numero sa kaliwa sa mga ito.

15
00:00:59,270 --> 00:01:03,600
Kaya, ipaalam sa magsimula sa 23, ang unang elemento sa aming listahan.

16
00:01:03,600 --> 00:01:06,930
Wala kaming anumang mga elemento sa aming pinagsunod-sunod na bahagi,

17
00:01:06,930 --> 00:01:12,460
kaya sabihin lamang isaalang-alang ang 23 sa pagsisimula at pagtatapos ng aming pinagsunod-sunod na bahagi.

18
00:01:12,460 --> 00:01:16,510
Ngayon, ang aming pinagsunod-sunod na bahagi ay may isang numero, 23,

19
00:01:16,510 --> 00:01:20,260
at ang aming unsorted bahagi ay ang limang numero.

20
00:01:20,260 --> 00:01:27,320
Natin ngayon ipasok ang susunod na bilang sa aming unsorted bahagi, 42, sa ang pinagsunod-sunod na bahagi.

21
00:01:27,320 --> 00:01:35,930
>> Upang gawin ito, makikita namin kailangan upang ihambing ang 42 sa 23 - ang tanging elemento sa aming pinagsunod-sunod bahagi sa ngayon.

22
00:01:35,930 --> 00:01:41,980
Apatnapu't-dalawang mas malaki kaysa sa 23, upang maaari naming lamang ikabit ang 42 sa dulo

23
00:01:41,980 --> 00:01:45,420
ng pinagsunod-sunod na bahagi ng listahan. Magaling!

24
00:01:45,420 --> 00:01:51,850
Ngayon ang aming pinagsunod-sunod na bahagi ay may dalawang mga elemento, at ang aming unsorted bahagi ay may apat na mga elemento.

25
00:01:51,850 --> 00:01:57,200
Kaya, sabihin ngayon lumipat sa 4, ang susunod na elemento sa unsorted bahagi.

26
00:01:57,200 --> 00:02:00,230
Kaya, kung saan dapat ito ilagay sa ang pinagsunod-sunod na bahagi?

27
00:02:00,230 --> 00:02:04,220
>> Tandaan, gusto namin na ilagay ang numero sa pinagsunod-sunod pagkakasunod-sunod

28
00:02:04,220 --> 00:02:08,680
kaya ang aming pinagsunod-sunod na bahagi ay nananatiling tama pinagsunod-sunod sa lahat ng oras.

29
00:02:08,680 --> 00:02:14,380
Kung inilagay namin ang 4 sa kanan ng 42, ang aming listahan ay sira.

30
00:02:14,380 --> 00:02:18,380
Kaya, sabihin magpatuloy sa paglipat kanan-papuntang-kaliwa sa aming bahagi sa-uuri.

31
00:02:18,380 --> 00:02:23,260
Bilang namin ilipat, sabihin shift bawat bilang down sa isang lugar upang gumawa ng room para sa mga bagong numero.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 din mas mababa sa 23, kaya hindi namin ilagay ito dito alinman.

33
00:02:31,740 --> 00:02:34,480
Natin ilipat ang 23 kanang isang lugar.

34
00:02:36,500 --> 00:02:43,120
>> Ibig sabihin nito ay nais naming ilagay ang 4 sa unang slot sa ang pinagsunod-sunod na bahagi.

35
00:02:43,120 --> 00:02:46,300
Pansinin kung paano ang puwang na ito sa listahan ay na walang laman,

36
00:02:46,300 --> 00:02:51,120
dahil kami ay gumagalaw pinagsunod-sunod elemento bilang Nakaranas kami ng mga ito.

37
00:02:51,120 --> 00:02:52,740
Ayos lang. Kaya, hindi namin kalahatian doon.

38
00:02:52,740 --> 00:02:57,990
Natin ipagpatuloy ang aming algorithm sa pamamagitan ng pagpapasok ng 16 sa ang pinagsunod-sunod na bahagi.

39
00:02:59,260 --> 00:03:03,820
Labing-anim ay mas mababa sa 42, kaya sabihin shift ang 42 sa kanan.

40
00:03:05,700 --> 00:03:10,190
Labing-anim ay din mas mababa sa 23, kaya sabihin din shift na elemento.

41
00:03:11,790 --> 00:03:20,820
>> Ngayon, 16 ay mas malaki kaysa sa 4. Kaya, mukhang nais naming upang ipasok ang 16 sa pagitan ng 4 at ang 23.

42
00:03:20,820 --> 00:03:24,620
Habang nililipat sa pamamagitan ng pinagsunod-sunod na bahagi ng listahan mula sa karapatan sa kaliwa,

43
00:03:24,620 --> 00:03:29,160
4 ay ang unang numero na iyong nakita namin na mas maliit kaysa sa bilang

44
00:03:29,160 --> 00:03:31,540
kami ay sinusubukan upang ipasok.

45
00:03:31,540 --> 00:03:35,820
Kaya, ngayon maaari naming ipasok ang 16 sa ito walang laman na slot,

46
00:03:35,820 --> 00:03:40,520
kung saan, Tandaan, kami nilikha ng gumalaw elemento sa bahagi-uuri sa

47
00:03:40,520 --> 00:03:43,340
Nakaranas kami ng mga ito.

48
00:03:43,340 --> 00:03:47,900
>> Ayos lang. Ngayon, kami ay may apat na pinagsunod-sunod na mga elemento at dalawang unsorted elemento.

49
00:03:47,900 --> 00:03:51,600
Kaya, sabihin ilipat ang 8 sa ang pinagsunod-sunod na bahagi.

50
00:03:51,600 --> 00:03:55,010
Walong ay mas mababa sa 42.

51
00:03:55,010 --> 00:03:56,940
Walong ay mas mababa sa 23.

52
00:03:56,940 --> 00:04:00,230
At 8 ay mas mababa sa 16.

53
00:04:00,230 --> 00:04:03,110
Ngunit 8 ay mas malaki kaysa sa 4.

54
00:04:03,110 --> 00:04:07,280
Kaya, nais naming upang ipasok ang 8 sa pagitan ng 4 at ang 16.

55
00:04:09,070 --> 00:04:13,650
At ngayon lang namin ng isa pang elemento sa kaliwa upang ayusin - ang 15.

56
00:04:13,950 --> 00:04:16,589
Labinlimang ay mas mababa sa 42,

57
00:04:16,589 --> 00:04:19,130
Labinlimang ay mas mababa sa 23.

58
00:04:19,130 --> 00:04:21,750
At 15 ay mas mababa sa 16.

59
00:04:21,750 --> 00:04:24,810
Ngunit 15 ay mas malaki kaysa sa 8.

60
00:04:24,810 --> 00:04:27,440
>> Kaya, dito ay kung saan nais namin upang gawing ang aming panghuling pagpapasok ng.

61
00:04:28,770 --> 00:04:30,330
At tapos na kami.

62
00:04:30,330 --> 00:04:33,540
Wala kaming higit pang mga elemento sa unsorted bahagi,

63
00:04:33,540 --> 00:04:36,670
at ang aming pinagsunod-sunod na bahagi ay sa tamang pagkakasunod-sunod.

64
00:04:36,670 --> 00:04:40,270
Ang mga numero ay order mula sa pinakamaliit sa pinakamalaking.

65
00:04:40,270 --> 00:04:44,330
Kaya, sabihin tingnan sa ilang pseudocode na naglalarawan sa mga hakbang na lang namin ginanap.

66
00:04:46,760 --> 00:04:51,740
>> Sa ika-1 linya, maaari naming makita na kakailanganin naming upang umulit sa paglipas ng bawat elemento sa listahan

67
00:04:51,740 --> 00:04:57,060
maliban sa unang, dahil ang unang elemento sa unsorted bahagi ay lamang maging

68
00:04:57,060 --> 00:05:00,220
sa unang elemento sa ang pinagsunod-sunod na bahagi.

69
00:05:00,220 --> 00:05:06,320
Sa linya 2 at 3, Pinananatili namin ang track ng aming kasalukuyang lugar sa unsorted bahagi.

70
00:05:06,320 --> 00:05:10,450
Element kumakatawan sa bilang kasalukuyan naming ay gumagalaw sa ang pinagsunod-sunod na bahagi,

71
00:05:10,450 --> 00:05:15,600
at j ay kumakatawan sa aming index sa unsorted bahagi.

72
00:05:15,600 --> 00:05:20,980
>> Sa linya 4, kami ay iterating sa pamamagitan ng ang pinagsunod-sunod bahagi mula sa karapatan sa kaliwa.

73
00:05:20,980 --> 00:05:26,010
Gusto naming itigil iterating sa sandaling ang elemento sa kaliwa ng aming kasalukuyang posisyon

74
00:05:26,010 --> 00:05:30,050
ay mas mababa kaysa sa elemento kami ay sinusubukan upang ipasok.

75
00:05:30,050 --> 00:05:35,600
Sa ika-5 linya, namin ang paglilipat ng bawat elemento kami nakatagpo ng isang espasyo sa kanan.

76
00:05:35,600 --> 00:05:40,950
Sa ganoong paraan, mayroon kaming isang malinaw na espasyo upang ipasok sa kapag nakita namin ang unang elemento

77
00:05:40,950 --> 00:05:44,080
mas mababa kaysa sa elemento na namin ang paglipat.

78
00:05:44,080 --> 00:05:50,800
Sa linya 6, kami ay ina-update ang aming counter upang magpatuloy upang ilipat sa kaliwa sa pamamagitan ng pinagsunod-sunod bahagi.

79
00:05:50,800 --> 00:05:56,860
Sa wakas, sa linya 7, kami ay pagpasok ng elemento sa pinagsunod-sunod na bahagi ng listahan.

80
00:05:56,860 --> 00:06:00,020
>> Alam namin na ito ay okay upang ipasok sa posisyon j,

81
00:06:00,020 --> 00:06:05,360
dahil Inilipat namin ang elemento na ginamit na doon isang espasyo sa kanan.

82
00:06:05,360 --> 00:06:09,460
Tandaan, kami ay gumagalaw sa pamamagitan ng pinagsunod-sunod bahagi mula sa karapatan sa kaliwa,

83
00:06:09,460 --> 00:06:13,960
ngunit kami ay gumagalaw sa pamamagitan ng unsorted bahagi mula kaliwa papuntang kanan.

84
00:06:13,960 --> 00:06:19,090
Ayos lang. Natin na ngayong kumuha ng isang pagtingin sa kung gaano katagal tumatakbo na algorithm kinuha.

85
00:06:19,090 --> 00:06:25,300
Ipapakita muna namin tanungin ang tanong kung gaano katagal aabutin para sa algorithm na ito upang tumakbo sa ang pinakamasama kaso.

86
00:06:25,300 --> 00:06:29,040
Manariwa sa diwa na kumakatawan namin ito tumatakbo oras may Big O pagtatanda.

87
00:06:32,530 --> 00:06:38,500
Upang ayusin ang aming listahan, nagkaroon kami upang umulit sa ibabaw ng mga elemento sa unsorted bahagi,

88
00:06:38,500 --> 00:06:43,430
at para sa bawat isa sa mga elemento, potensyal na higit sa lahat ng mga elemento sa ang pinagsunod-sunod na bahagi.

89
00:06:43,430 --> 00:06:47,950
Intuitively, ito tunog tulad ng isang operasyon ng O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Naghahanap sa aming pseudocode, mayroon kaming isang loop na nested sa loob ng isa pang loop,

91
00:06:51,840 --> 00:06:55,290
kung saan, sa katunayan, tunog tulad ng isang operasyon ng O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Gayunpaman, ang pinagsunod-sunod na bahagi ng listahan ay hindi naglalaman ang buong listahan ng hanggang sa pinakadulo.

93
00:07:01,590 --> 00:07:06,920
Pa rin, maaari naming potensyal na magpasok ng isang bagong elemento sa pinakadulo simula ng ang pinagsunod-sunod na bahagi

94
00:07:06,920 --> 00:07:09,320
sa bawat pag-ulit ng algorithm,

95
00:07:09,320 --> 00:07:14,500
na nangangahulugan na nais namin upang tumingin sa bawat elemento kasalukuyang sa ang pinagsunod-sunod na bahagi.

96
00:07:14,500 --> 00:07:20,090
Kaya, na nangangahulugang kami maaaring potensyal na gumawa ng isang paghahambing para sa pangalawang elemento,

97
00:07:20,090 --> 00:07:24,660
dalawang paghahambing para sa ikatlong elemento, at iba pa.

98
00:07:24,660 --> 00:07:32,480
Kaya, ang kabuuang bilang ng mga hakbang ay ang kabuuan ng integer mula sa 1 sa haba ng listahan minus 1.

99
00:07:32,480 --> 00:07:35,240
Maaari naming kumatawan ang mga ito gamit ang isang kabuuan.

100
00:07:41,170 --> 00:07:47,270
>> Hindi namin pumunta sa summations dito, ngunit ito lumiliko out na ang kabuuan na ito ay katumbas ng

101
00:07:47,270 --> 00:07:57,900
n (n - 1) sa 2, na kung saan ay katumbas n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kapag pakikipag-usap tungkol sa asymptotic runtime,

103
00:08:00,800 --> 00:08:05,170
ito n ^ 2 termino sa dominahin ito n termino.

104
00:08:05,170 --> 00:08:11,430
Kaya, pagpapasok ng-uuri ay Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Paano kung tumakbo namin ang pagpapasok ng uri sa isang na pinagsunod-sunod sa listahan.

106
00:08:16,150 --> 00:08:20,960
Sa kasong iyon, nais lamang namin bumuo ng ang bahagi na pinagsunod-sunod mula kaliwa papuntang kanan.

107
00:08:20,960 --> 00:08:25,050
Kaya, kailangan lamang namin sa pagkakasunud-sunod ng mga hakbang sa n.

108
00:08:25,050 --> 00:08:29,740
>> Iyon ay nangangahulugang ang pagpapasok ng-uuri ay may pinakamahusay na-case na pagganap ng n,

109
00:08:29,740 --> 00:08:34,130
na kinakatawan namin sa Ω (n).

110
00:08:34,130 --> 00:08:36,190
At na ito para sa pagpapasok ng-uuri,

111
00:08:36,190 --> 00:08:40,429
isa lamang sa maraming mga na mga algorithm na maaari naming gamitin upang pag-uri-uriin ang isang listahan.

112
00:08:40,429 --> 00:08:43,210
Ang pangalan ko ay Tommy, at ito ay CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, mo lamang ay hindi maaaring itigil na kapag nagsimula na itong.

115
00:09:01,620 --> 00:09:04,760
Oh, ginawa namin na - >> Boom!