1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Sórtáil isteach]

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

3
00:00:04,240 --> 00:00:07,290
[Tá sé seo CS50.TV]

4
00:00:07,290 --> 00:00:13,060
A ligean ar ghlacadh le breathnú ar saghas leanas a chur isteach, algartaim as liosta d'uimhreacha agus sórtáil leo.

5
00:00:13,060 --> 00:00:18,300
Tá algartam, cuimhnigh, ach nós imeachta céim-ar-chéim do accomplishing tasc.

6
00:00:18,300 --> 00:00:23,640
An smaoineamh taobh thiar de bhun saghas isteach, is é a roinnt ár liosta ina dhá chuid,

7
00:00:23,640 --> 00:00:26,580
cuid curtha in eagar agus cuid neamhshórtáilte.

8
00:00:26,580 --> 00:00:29,290
>> Ag gach céim den algartam, tá roinnt ar athraíodh a ionad

9
00:00:29,290 --> 00:00:32,439
as an chuid neamhshórtáilte leis an gcuid in eagar

10
00:00:32,439 --> 00:00:35,680
go dtí deireadh an liosta ar fad curtha in eagar.

11
00:00:35,680 --> 00:00:43,340
Seo liosta de na sé uimhir neamhshórtáilte - 23, 42, 4, 16, 8, agus 15.

12
00:00:43,340 --> 00:00:47,680
Ós rud é nach bhfuil na huimhreacha seo ar fad in ord ardaitheach, tá siad ag neamhshórtáilte.

13
00:00:47,680 --> 00:00:53,890
Ós rud é nach mór dúinn tús a shórtáil go fóill, beidh orainn a mheas na sé ghné dár gcuid neamhshórtáilte.

14
00:00:53,890 --> 00:00:59,270
>> Nuair a thosaíonn muid ag sórtáil, beidh muid ag na huimhreacha seo in eagar a chur ar an taobh clé de na.

15
00:00:59,270 --> 00:01:03,600
Mar sin, a ligean ar tús a chur le 23, an chéad eilimint i ár liosta.

16
00:01:03,600 --> 00:01:06,930
Ní thugaimid aon ghnéithe inár chuid curtha in eagar go fóill,

17
00:01:06,930 --> 00:01:12,460
mar sin a ligean ar a mheas ach 23 a bheith ar an tús agus deireadh ár gcuid curtha in eagar.

18
00:01:12,460 --> 00:01:16,510
Anois, tá ár sciar curtha in eagar aon uimhir amháin, 23,

19
00:01:16,510 --> 00:01:20,260
agus tá ár sciar neamhshórtáilte na cúig uimhreacha.

20
00:01:20,260 --> 00:01:27,320
Lig isteach anois an chéad uimhir eile sa chuid neamhshórtáilte, 42, isteach sa chuid eagar.

21
00:01:27,320 --> 00:01:35,930
>> Chun sin a dhéanamh, beidh orainn an 42 i gcomparáid leis an 23 - an ghné amháin i ár gcuid curtha in eagar go dtí seo.

22
00:01:35,930 --> 00:01:41,980
Daichead a dó is mó ná 23, ionas gur féidir linn gceangal ach 42 go dtí deireadh

23
00:01:41,980 --> 00:01:45,420
na coda curtha in eagar ar an liosta. Great!

24
00:01:45,420 --> 00:01:51,850
Anois, tá ár sciar curtha in eagar dhá ghné, agus tá ár sciar neamhshórtáilte ceithre ghné.

25
00:01:51,850 --> 00:01:57,200
Mar sin, a ligean ar bogadh anois leis an 4, an ghné eile sa chuid neamhshórtáilte.

26
00:01:57,200 --> 00:02:00,230
Mar sin, ba chóir nuair is é seo a chur sa chuid curtha in eagar?

27
00:02:00,230 --> 00:02:04,220
>> Cuimhnigh, ba mhaith linn chun an uimhir seo in ord sórtáilte

28
00:02:04,220 --> 00:02:08,680
mar sin i gcónaí ar ár gcuid sórtáilte mar is ceart curtha in eagar i gcónaí.

29
00:02:08,680 --> 00:02:14,380
Má tá ar siúl againn ar an 4 do cheart na 42, ansin beidh ár liosta a bheith as ord.

30
00:02:14,380 --> 00:02:18,380
Mar sin, a ligean ar aghaidh ag bogadh ceart-go-chlé i ár gcuid saghas.

31
00:02:18,380 --> 00:02:23,260
Agus muid ag bogadh, a ligean ar athrú gach uimhir síos in áit seomra a dhéanamh ar an líon nua.

32
00:02:25,440 --> 00:02:31,740
Maith go leor, is é 4 níos lú ná 23, mar sin ní féidir linn é a chur anseo ach an oiread.

33
00:02:31,740 --> 00:02:34,480
A ligean ar bogadh an 23 ceart áit amháin.

34
00:02:36,500 --> 00:02:43,120
>> Ciallaíonn sin ba mhaith linn chun an 4 isteach sa sliotán den chéad uair sa chuid eagar.

35
00:02:43,120 --> 00:02:46,300
Fógra conas a bhí an spás seo ar an liosta cheana folamh,

36
00:02:46,300 --> 00:02:51,120
mar tá muid ag bogadh eilimintí eagar síos mar a bhíonn againn orthu.

37
00:02:51,120 --> 00:02:52,740
Gach ceart. Mar sin, tá muid leathbhealach ann.

38
00:02:52,740 --> 00:02:57,990
A ligean ar leanúint ar aghaidh lenár algartam tríd an 16 isteach sa chuid eagar.

39
00:02:59,260 --> 00:03:03,820
Sé cinn déag de níos lú ná 42, mar sin a ligean ar an 42 a aistriú chuig an ceart.

40
00:03:05,700 --> 00:03:10,190
Sé cinn déag freisin níos lú ná 23, mar sin a ligean aistriú freisin an eilimint.

41
00:03:11,790 --> 00:03:20,820
>> Anois, tá 16 níos mó ná 4. Mar sin, tá sé cosúil mhaith linn a chur isteach ar an 16 idir an 4 agus an 23.

42
00:03:20,820 --> 00:03:24,620
Cé ag gluaiseacht tríd an chuid curtha in eagar ar an liosta ó ceart ar chlé,

43
00:03:24,620 --> 00:03:29,160
Is é 4 an chéad uimhir againn le feiceáil go bhfuil níos lú ná an líon

44
00:03:29,160 --> 00:03:31,540
táimid ag iarraidh a chur isteach.

45
00:03:31,540 --> 00:03:35,820
Mar sin, anois is féidir linn a chur isteach ar an 16 isteach sa sliotán folamh,

46
00:03:35,820 --> 00:03:40,520
a bhfuil, cuimhnigh, tá muid cruthaithe ag gnéithe gluaiseacht sa chuid saghas thar

47
00:03:40,520 --> 00:03:43,340
mar a againn a bhíonn orthu.

48
00:03:43,340 --> 00:03:47,900
>> Gach ceart. Anois, ní mór dúinn ceithre ghné curtha in eagar agus dhá eilimint neamhshórtáilte.

49
00:03:47,900 --> 00:03:51,600
Mar sin, a ligean ar bogadh an 8 isteach sa chuid eagar.

50
00:03:51,600 --> 00:03:55,010
Tá ocht níos lú ná 42.

51
00:03:55,010 --> 00:03:56,940
Tá ocht níos lú ná 23.

52
00:03:56,940 --> 00:04:00,230
Agus is é 8 lú ná 16.

53
00:04:00,230 --> 00:04:03,110
Ach tá níos mó ná 8 4.

54
00:04:03,110 --> 00:04:07,280
Mar sin, ba mhaith linn a chur isteach ar an 8 idir an 4 agus an 16.

55
00:04:09,070 --> 00:04:13,650
Agus anois tá ach gné amháin níos mó a d'fhág a shórtáil - an 15.

56
00:04:13,950 --> 00:04:16,589
Tá cúig cinn déag de níos lú ná 42,

57
00:04:16,589 --> 00:04:19,130
Tá cúig cinn déag de níos lú ná 23.

58
00:04:19,130 --> 00:04:21,750
Agus is é 15 níos lú ná 16.

59
00:04:21,750 --> 00:04:24,810
Ach tá 15 níos mó ná 8.

60
00:04:24,810 --> 00:04:27,440
>> Mar sin, tá anseo áit ar mhaith linn a dhéanamh ar ár leanas a chur isteach deiridh.

61
00:04:28,770 --> 00:04:30,330
Agus muid ag déanamh.

62
00:04:30,330 --> 00:04:33,540
Tá aon eilimintí níos mó sa chuid neamhshórtáilte,

63
00:04:33,540 --> 00:04:36,670
agus is é ár sciar curtha in eagar san ord ceart.

64
00:04:36,670 --> 00:04:40,270
Na huimhreacha ordú ó lú go dtí mó.

65
00:04:40,270 --> 00:04:44,330
Mar sin, a ligean ar ghlacadh le breathnú ar roinnt pseudocode a chuireann síos ar na céimeanna a dhéantar againn ach.

66
00:04:46,760 --> 00:04:51,740
>> Ar líne 1, is féidir linn a fheiceáil go beidh orainn a iterate thar gach gné ar an liosta

67
00:04:51,740 --> 00:04:57,060
ach amháin an gcéad dul síos, beidh ós rud é an chéad eilimint sa chuid neamhshórtáilte a bheith simplí

68
00:04:57,060 --> 00:05:00,220
an chéad eilimint sa chuid eagar.

69
00:05:00,220 --> 00:05:06,320
Ar línte 2 agus 3, tá muid ag súil a choinneáil ar ár n-áit chónaithe reatha sa chuid neamhshórtáilte.

70
00:05:06,320 --> 00:05:10,450
Eilimint Is ionann an líon táimid ag bogadh faoi láthair isteach sa chuid curtha in eagar,

71
00:05:10,450 --> 00:05:15,600
agus is ionann j ár innéacs isteach sa chuid neamhshórtáilte.

72
00:05:15,600 --> 00:05:20,980
>> Ar líne 4, tá muid ag iterating tríd an chuid eagar ó ceart chun chlé.

73
00:05:20,980 --> 00:05:26,010
Ba mhaith linn a stopadh iterating uair an eilimint an taobh clé den ár suíomh reatha

74
00:05:26,010 --> 00:05:30,050
níos lú ná an eilimint táimid ag iarraidh a chur isteach.

75
00:05:30,050 --> 00:05:35,600
Ar líne 5, tá muid ag aistriú gach eilimint muid ar cheann spás a bhíonn ar dheis.

76
00:05:35,600 --> 00:05:40,950
Sa chaoi sin, beidh orainn spás soiléir a chur isteach i nuair a fhaigheann muid an chéad eilimint

77
00:05:40,950 --> 00:05:44,080
níos lú ná an eilimint táimid ag gluaiseacht.

78
00:05:44,080 --> 00:05:50,800
Ar líne 6, tá muid ag cothrom le dáta ár gcuntar chun leanúint ar aghaidh chun bogadh ar chlé tríd an chuid eagar.

79
00:05:50,800 --> 00:05:56,860
Ar deireadh, líne 7, táimid tríd an eilimint isteach sa chuid curtha in eagar ar an liosta.

80
00:05:56,860 --> 00:06:00,020
>> Tá a fhios againn go bhfuil sé ceart go leor a chur isteach i j seasamh,

81
00:06:00,020 --> 00:06:05,360
mar tá muid ar athraíodh a ionad cheana féin ar an eilimint a úsáidtear a bheith ann spás amháin leis an gceart.

82
00:06:05,360 --> 00:06:09,460
Cuimhnigh, tá muid ag bogadh tríd an chuid eagar ó ceart ar chlé,

83
00:06:09,460 --> 00:06:13,960
ach táimid ag gluaiseacht tríd an chuid neamhshórtáilte ó chlé go deas.

84
00:06:13,960 --> 00:06:19,090
Gach ceart. A ligean ar a ghlacadh anois le breathnú ar cé chomh fada ag rith a tharla algartam.

85
00:06:19,090 --> 00:06:25,300
Beidh muid a iarraidh ar dtús leis an cheist cé chomh fada a thógann sé ar an algartam a reáchtáil sa chás is measa.

86
00:06:25,300 --> 00:06:29,040
Glaoch ar ais go ionadaíocht againn an uair seo ag rith le nodaireacht O Big.

87
00:06:32,530 --> 00:06:38,500
D'fhonn a shórtáil ar ár liosta, bhí againn a iterate ar na gnéithe seo sa chuid neamhshórtáilte,

88
00:06:38,500 --> 00:06:43,430
agus do gach ceann de na gnéithe sin, d'fhéadfadh a bheith os cionn gach eilimint sa chuid eagar.

89
00:06:43,430 --> 00:06:47,950
Intuitively, fuaimeanna seo cosúil le oibríocht (n ^ 2) O.

90
00:06:47,950 --> 00:06:51,840
>> Ag Breathnú ar an pseudocode, ní mór dúinn a lúb neadaithe taobh istigh eile lúb,

91
00:06:51,840 --> 00:06:55,290
a bhfuil, go deimhin, fuaimeanna, cosúil le feidhmiú le (n ^ 2) O.

92
00:06:55,290 --> 00:07:01,590
Mar sin féin, ní raibh an chuid curtha in eagar de liosta an liosta iomlán go dtí deireadh an-.

93
00:07:01,590 --> 00:07:06,920
Fós, d'fhéadfadh muid a chur isteach d'fhéadfadh a bheith ina ghné nua ag tús an-an chuid eagar

94
00:07:06,920 --> 00:07:09,320
ar gach atriall an algartam,

95
00:07:09,320 --> 00:07:14,500
rud a chiallaíonn gur mhaith linn a bheith chun breathnú ar gach gné faoi láthair sa chuid eagar.

96
00:07:14,500 --> 00:07:20,090
Mar sin, ciallaíonn sé go bhféadfadh muid a dhéanamh d'fhéadfadh a bheith ar cheann i gcomparáid le haghaidh an dara gné,

97
00:07:20,090 --> 00:07:24,660
dhá comparáidí le haghaidh an tríú gné, agus mar sin de.

98
00:07:24,660 --> 00:07:32,480
Mar sin, tá an líon iomlán na céimeanna suim na slánuimhreacha ó 1 go fad an liosta lúide 1.

99
00:07:32,480 --> 00:07:35,240
Is féidir linn seo a léiriú le go léir a shuimiú.

100
00:07:41,170 --> 00:07:47,270
>> Ní féidir linn dul i summations anseo, ach anois sé amach go bhfuil an tsuimithe cothrom le

101
00:07:47,270 --> 00:07:57,900
n (n - 1) os cionn 2, a bhfuil n comhionann ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Nuair a labhairt faoi runtime asymptotic,

103
00:08:00,800 --> 00:08:05,170
tá sé seo ^ n 2 téarma ag dul a tionchar an-mhór an téarma n.

104
00:08:05,170 --> 00:08:11,430
Mar sin, tá saghas isteach Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Cad a tharlaíonn má bhí ar siúl againn saghas isteach ar an liosta sórtáilte cheana.

106
00:08:16,150 --> 00:08:20,960
Sa chás sin, ba mhaith linn a thógáil ach suas an chuid eagar ó chlé go deas.

107
00:08:20,960 --> 00:08:25,050
Mar sin, beidh orainn gá ach ar an ord céimeanna n.

108
00:08:25,050 --> 00:08:29,740
>> Ciallaíonn sé sin go bhfuil saghas isteach ar fheidhmíocht is fearr ar chás na n,

109
00:08:29,740 --> 00:08:34,130
a dhéanann ionadaíocht againn le Ω (n).

110
00:08:34,130 --> 00:08:36,190
Agus sin é do saghas leanas a chur isteach,

111
00:08:36,190 --> 00:08:40,429
ach ceann amháin de na halgartaim is féidir linn a úsáid a shórtáil liosta.

112
00:08:40,429 --> 00:08:43,210
Is é mo ainm Tommy, agus tá sé seo CS50.

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

114
00:08:46,110 --> 00:08:49,230
Ó, tá tú nach féidir stop a chur díreach go uair a thosaíonn sé.

115
00:09:01,620 --> 00:09:04,760
Ó, rinne muid go - Boom >>!