1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Mar sin, i CS50 d'fhoghlaim muid faoi
ar éagsúlacht na sórtáil agus cuardach

3
00:00:08,900 --> 00:00:09,442
halgartaim.

4
00:00:09,442 --> 00:00:11,400
Agus uaireanta is féidir é a bheith
beag tricky a choinneáil

5
00:00:11,400 --> 00:00:14,161
dhéanann súil a choinneáil ar cén algartam cad.

6
00:00:14,161 --> 00:00:15,910
Tá muid i ndáiríre ach
bearrtha an dromchla freisin,

7
00:00:15,910 --> 00:00:18,740
tá go leor eile chuardach
agus halgartaim sórtáil.

8
00:00:18,740 --> 00:00:21,780
Mar sin, i físeán seo a ligean ar
ach cúpla nóiméad a ghlacadh

9
00:00:21,780 --> 00:00:24,980
chun iarracht a dhéanamh agus a distill gach algartam
síos go dtí a eilimintí lárnacha

10
00:00:24,980 --> 00:00:27,810
ionas gur féidir leat cuimhneamh ar an chuid is mó
eolas tábhachtach mar gheall orthu

11
00:00:27,810 --> 00:00:31,970
agus a bheith in ann a chur in iúl ar an
difríochtaí, más gá.

12
00:00:31,970 --> 00:00:34,220
>> Is é an chéad saghas roghnaithe.

13
00:00:34,220 --> 00:00:38,210
An smaoineamh bunúsach taobh thiar de saghas roghnaithe
Tá teacht ar an ghné is lú neamhshórtáilte

14
00:00:38,210 --> 00:00:42,890
i sraith agus bhabhtáil sé leis an
chéad eilimint neamhshórtáilte den eagar.

15
00:00:42,890 --> 00:00:46,620
Dúirt muid go raibh an ceann is measa ar chás
reáchtáil am sin bhí n cearnógach.

16
00:00:46,620 --> 00:00:50,060
Agus más mian leat a thabhairt chun cuimhne cén fáth, a chur
a féachaint ar na físeáin saghas roghnaithe.

17
00:00:50,060 --> 00:00:54,560
An t-am is fearr a reáchtáil ar chás
Tá n cearnaithe freisin.

18
00:00:54,560 --> 00:00:58,910
>> Saghas mboilgeog, an smaoineamh taobh thiar de sin
tá sé ar cheann a mhalartú péirí cóngaracha.

19
00:00:58,910 --> 00:01:01,730
Mar sin, go bhfuil an eochair a chuidíonn leat
cuimhneamh ar an difríocht anseo.

20
00:01:01,730 --> 00:01:04,920
Roghnú saghas is é sin, go dtí seo,
teacht ar an mboilgeog smallest--

21
00:01:04,920 --> 00:01:06,790
saghas é sin mhalartú péirí cóngaracha.

22
00:01:06,790 --> 00:01:08,710
Babhtála táimid ag péirí cóngaracha
na n-eilimintí má tá siad

23
00:01:08,710 --> 00:01:12,530
atá as ordú, a go héifeachtach
boilgeoga gnéithe níos mó leis an gceart,

24
00:01:12,530 --> 00:01:17,060
agus ag an am céanna tosaíonn sé freisin
chun bogadh eilimintí níos lú ar an taobh clé.

25
00:01:17,060 --> 00:01:20,180
An ceann is measa ar chás am cás a reáchtáil
de mboilgeog saghas atá cearnaithe n.

26
00:01:20,180 --> 00:01:23,476
An t-am is fearr a reáchtáil ar chás
de mboilgeog Is saghas n.

27
00:01:23,476 --> 00:01:25,350
Toisc i staid sin
ní féidir linn a actually--

28
00:01:25,350 --> 00:01:27,141
D'fhéadfadh ní mór dúinn a
aon babhtálacha ar chor ar bith.

29
00:01:27,141 --> 00:01:31,026
Ní mór dúinn ach a dhéanamh ar cheann
pas a fháil ar fud gach gné n.

30
00:01:31,026 --> 00:01:34,600
>> I chur isteach a shórtáil, an
Tá smaoineamh bunúsach anseo aistriú.

31
00:01:34,600 --> 00:01:36,630
Sin an eochairfhocal do chur isteach saghas.

32
00:01:36,630 --> 00:01:39,630
Táimid ag dul chun dlús uair amháin trí
an sraith ó chlé go deas.

33
00:01:39,630 --> 00:01:41,670
Agus mar a bhíonn againn, tá muid
dul chun eilimintí aistriú

34
00:01:41,670 --> 00:01:46,260
againn le feiceáil cheana féin seomra a dhéanamh le haghaidh
cinn níos lú gur gá a d'oirfeadh áit éigin

35
00:01:46,260 --> 00:01:48,080
ar ais sa chuid sin curtha in eagar.

36
00:01:48,080 --> 00:01:51,600
Mar sin, a thógáil againn ar an sraith sórtáilte amháin
eilimint ag an am, ó chlé go deas,

37
00:01:51,600 --> 00:01:54,740
agus athrú muid rudaí seomra a dhéanamh.

38
00:01:54,740 --> 00:01:58,650
An t-am a reáchtáil is measa ar chás de
Tá a chur isteach a shórtáil cearnógach n.

39
00:01:58,650 --> 00:02:02,380
Is é an t-am is fearr ar chás reáchtáil n.

40
00:02:02,380 --> 00:02:05,380
>> Cumaisc sort-- an eochairfhocal
anseo scoilt agus chumasadh.

41
00:02:05,380 --> 00:02:08,949
Scoilt muid an sraith iomlán, cibé acu
tá sé sé gnéithe, ocht ngné,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- scoilt muid é
síos ag leath, ag leath, ag leath,

43
00:02:13,790 --> 00:02:17,720
go dtí go atá againn faoi eagar
de n amháin arrays eilimint.

44
00:02:17,720 --> 00:02:19,470
Sraith de n amháin arrays eilimint.

45
00:02:19,470 --> 00:02:22,640
Mar sin, thosaigh muid le ceann amháin
Sraith 1,000-eilimint,

46
00:02:22,640 --> 00:02:26,550
agus a fhaigheann muid go dtí an pointe nuair a muid
tá 1,000 eagair aon-eilimint.

47
00:02:26,550 --> 00:02:30,990
Ansin muid ag cur tús a chumasadh leis na arrays fo
ar ais le chéile san ord ceart.

48
00:02:30,990 --> 00:02:34,860
Mar sin, a chur orainn dhá arrays aon-eilimint
agus a chruthú sraith dhá-eilimint.

49
00:02:34,860 --> 00:02:38,180
A chur orainn dhá arrays dhá eilimint
agus a chruthú sraith ceithre eilimint

50
00:02:38,180 --> 00:02:43,900
agus mar sin de agus mar sin de go dtí go bhfuil muid
arís atógadh amháin eagar gné n.

51
00:02:43,900 --> 00:02:48,410
>> An t-am a reáchtáil is measa ar chás de
merge sórtáil é sin n uair logáil n.

52
00:02:48,410 --> 00:02:52,390
Ní mór dúinn gnéithe n, ach
an próiseas seo recombining

53
00:02:52,390 --> 00:02:56,960
Bíonn logáil n céimeanna a fháil
ar ais go dtí raon iomlán.

54
00:02:56,960 --> 00:03:01,160
Is é an cás is fearr am siúl freisin n logáil
n toisc nach bhfuil an próiseas seo i ndáiríre

55
00:03:01,160 --> 00:03:04,090
cúram an raibh an eagar
curtha in eagar nó gan tús a chur leis.

56
00:03:04,090 --> 00:03:07,590
Tá an próiseas mar an gcéanna, níl
aon bhealach chun rudaí a chuaird gearr.

57
00:03:07,590 --> 00:03:11,610
Mar sin, n logáil isteach n sa chás is measa,
n logáil isteach n sa chás is fearr.

58
00:03:11,610 --> 00:03:13,960
>> Labhair muid thart ar dhá
halgartaim cuardach.

59
00:03:13,960 --> 00:03:16,230
Dá bhrí sin tá cuardach líneach gheall iterating.

60
00:03:16,230 --> 00:03:19,500
Dul ar aghaidh muid trasna an eagar
uair amháin, ó chlé go deas,

61
00:03:19,500 --> 00:03:21,950
ag iarraidh a fháil ar an líon
go bhfuil muid ag lorg.

62
00:03:21,950 --> 00:03:24,550
Is é an t-am is measa ar chás reáchtáil O mór de n.

63
00:03:24,550 --> 00:03:27,610
D'fhéadfadh sé a ghlacadh chugainn iterating
trasna gach gné amháin

64
00:03:27,610 --> 00:03:30,660
chun teacht ar an eilimint táimid ag lorg
do, bíodh sé sa phost seo caite,

65
00:03:30,660 --> 00:03:31,630
nó nach bhfuil ag gach.

66
00:03:31,630 --> 00:03:34,720
Ach ní féidir linn a dheimhniú go dtí go
tá muid d'fhéach sé ar gach rud.

67
00:03:34,720 --> 00:03:36,730
m an chuid is fearr ar chás, feicimid láithreach.

68
00:03:36,730 --> 00:03:41,060
An t-am is fearr a reáchtáil-gcás
Tá cuardach líneach óimige de 1.

69
00:03:41,060 --> 00:03:43,689
>> Ar deireadh, ní raibh cuardaigh dhénártha,
a éilíonn eagar assorted.

70
00:03:43,689 --> 00:03:45,605
Cuimhnigh go bhfuil an-
breithniú tábhachtach

71
00:03:45,605 --> 00:03:47,155
iad ag obair le cuardaigh dénártha.

72
00:03:47,155 --> 00:03:50,180
Tá sé ina réamhriachtanas chun úsáid a bhaint it--
an eagar go bhfuil tú ag lorg trí

73
00:03:50,180 --> 00:03:52,160
Ní mór a shórtáil.

74
00:03:52,160 --> 00:03:54,500
Seachas sin, an eochairfhocal
Tá deighilt agus conquer.

75
00:03:54,500 --> 00:03:58,310
Scoilt an eagar i leath agus
deireadh a chur leis ar leath de na heilimintí

76
00:03:58,310 --> 00:04:00,780
gach uair mar a théann tú tríd.

77
00:04:00,780 --> 00:04:04,330
Mar gheall ar an scoilt agus conquer
agus rudaí scoilteadh i gcur chuige leath,

78
00:04:04,330 --> 00:04:07,450
an t-am a reáchtáil is measa ar chás
Is de cuardaigh dénártha

79
00:04:07,450 --> 00:04:11,730
logáil n, atá i bhfad
níos fearr ná cuardach líneach ar n.

80
00:04:11,730 --> 00:04:13,570
Is é an t-am is fearr ar chás ar siúl fós ar cheann.

81
00:04:13,570 --> 00:04:17,010
>> D'fhéadfadh muid a aimsiú láithreach an
chéad uair a dhéanamh linn le roinn, ach,

82
00:04:17,010 --> 00:04:19,339
arís, cuimhnigh go
cé go bhfuil cuardaigh dhénártha

83
00:04:19,339 --> 00:04:24,030
go substaintiúil níos fearr ná cuardaigh líneach
de bhua a bheith logáil n versus n,

84
00:04:24,030 --> 00:04:27,110
a bheadh ​​agat chun dul tríd an obair
de sórtáil do eagar ar dtús, a

85
00:04:27,110 --> 00:04:32,010
d'fhéadfadh é a dhéanamh chomh héifeachtach ag brath
ar an méid de na iterating curtha in eagar.

86
00:04:32,010 --> 00:04:35,250
>> Tá mé Doug Lloyd, is é seo CS50.

87
00:04:35,250 --> 00:04:36,757