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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Ollscoil Harvard]

3
00:00:04,000 --> 00:00:07,000
Is é [seo CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Ligean ar labhairt faoi sort chumaiscthe.

5
00:00:09,000 --> 00:00:14,000
Go dtí seo tá tú ag feiceáil saghas mboilgeog, a shórtáil isteach, agus sórtáil roghnú.

6
00:00:14,000 --> 00:00:17,000
Cé Feicfidh mé cineál toinne mo lámh ar cad is ciall agam le níos fearr,

7
00:00:17,000 --> 00:00:21,000
merge sórtáil fheidhmíonn i gcoitinne níos fearr ná aon cheann de na 3 cineál.

8
00:00:22,000 --> 00:00:27,000
>> Ach sula ag caint faoi saghas merge, a ligean ar labhairt faoi chumasc 2 liosta sórtáilte.

9
00:00:27,000 --> 00:00:31,000
Beidh muid glaoch ar an bpróiseas a ghlacadh 2 liosta sórtáilte, mar seo,

10
00:00:31,000 --> 00:00:35,000
agus ag déanamh liosta amháin in eagar le amach acu - chumasc na liostaí.

11
00:00:35,000 --> 00:00:37,750
Conas is féidir linn seo a dhéanamh?

12
00:00:37,750 --> 00:00:41,290
Bhuel, ar cheann smaoineamh a bata díreach liosta amháin isteach ar an deireadh an liosta eile

13
00:00:41,290 --> 00:00:43,830
agus sórtáil ansin ar an liosta thoradh air sin.

14
00:00:43,830 --> 00:00:47,220
>> Cé go n-oibríonn seo, tá sé a lán oibre gan ghá.

15
00:00:47,220 --> 00:00:49,900
Is féidir linn é a dhéanamh níos tapúla ná díreach a shórtáil.

16
00:00:49,900 --> 00:00:54,100
Fógra go bhfuil ceann smaoineamh mícheart a ghlacadh ach cupáin alternating ó gach liosta.

17
00:00:54,100 --> 00:00:56,460
Cé gur féidir go bhfuil cuma mhaith go n-oibríonn ar dtús,

18
00:00:56,460 --> 00:01:05,760
a dhéanamh go bhfuil muid ag deireadh suas le 4, 8, 15, 23, 16 - Fógra go bhfuil 16 agus 23 as áit.

19
00:01:05,760 --> 00:01:09,380
Tá sé seo toisc 2 gnéithe ba chóir a feiceáil i ndiaidh a chéile ar an liosta cumaiscthe

20
00:01:09,380 --> 00:01:11,720
Tá an liosta céanna tosaigh.

21
00:01:11,720 --> 00:01:14,850
An dá 15 agus 16 atá ar an liosta ar chlé.

22
00:01:14,850 --> 00:01:19,810
Is é an trick leas a bhaint as an bhfíric go bhfuil an dá liostaí atá curtha in eagar cheana féin.

23
00:01:19,810 --> 00:01:23,320
Ciallaíonn sé seo má táimid ach breathnú ar na gnéithe chéad dá liostaí -

24
00:01:23,320 --> 00:01:29,580
anseo, 4 agus 8 - ní mór ceann amháin acu a bheith chomh maith an chéad ghné den liosta cumaiscthe.

25
00:01:29,580 --> 00:01:31,620
Bhuel, cén fáth é sin?

26
00:01:31,620 --> 00:01:33,520
Tá an dá de na liostaí seo atá curtha in eagar cheana féin,

27
00:01:33,520 --> 00:01:38,410
agus mar sin ní mór a bheith 4 nó 8 an ghné is lú nuair a chéile muid an 2 liosta.

28
00:01:38,410 --> 00:01:41,770
Sa chás seo, is é is lú 4,

29
00:01:41,770 --> 00:01:46,370
ionas gur féidir linn a thógáil amach 4 agus é a dhéanamh an chéad ghné den ár liosta cumaiscthe.

30
00:01:46,370 --> 00:01:50,710
Anois táimid ag leanúint ar aghaidh tríd an 3 atá fágtha gnéithe den chéad liosta

31
00:01:50,710 --> 00:01:52,920
agus 4 eilimintí an dara liosta.

32
00:01:52,920 --> 00:01:57,150
>> Arís eile, is gá dúinn ach chun breathnú ar an chéad eilimint de dá liostaí.

33
00:01:57,150 --> 00:02:01,060
Ní mór don lú den 2 an dara gné d'ár liosta cumaiscthe.

34
00:02:01,060 --> 00:02:05,440
An uair seo, idir 8 agus 15 is lú 8, agus mar sin againn isteach go

35
00:02:05,440 --> 00:02:09,240
mar an dara gné den ár liosta in eagar.

36
00:02:09,240 --> 00:02:12,180
Is féidir linn leanúint ar aghaidh i gcomparáid leis an chéad chuid de dhá liostaí

37
00:02:12,180 --> 00:02:14,420
agus a bhaint de na lú ar an 2.

38
00:02:14,420 --> 00:02:19,460
Comparáid 15 agus 23, 15 níos lú agus mar sin go s ár tríú gné.

39
00:02:21,000 --> 00:02:23,910
Anois i gcomparáid 16 agus 23, 16 níos lú.

40
00:02:23,910 --> 00:02:26,820
Mar sin, go bhfuil an ghné ceathrú.

41
00:02:26,820 --> 00:02:30,390
>> Fógra a tháinig 2 gnéithe ón liosta céanna i ndiaidh a chéile.

42
00:02:30,390 --> 00:02:34,400
Sin é an fáth nach féidir an liosta cumaiscthe díreach gnéithe malartach ó na liostaí 2.

43
00:02:34,400 --> 00:02:40,020
Comparáid 50 agus 23, 23 níos lú, mar sin roghnaigh muid go.

44
00:02:40,770 --> 00:02:44,070
Idir 50 agus 42, is é 42 níos lú.

45
00:02:44,070 --> 00:02:48,290
Idir 50 agus 108, is é 50 níos lú.

46
00:02:48,290 --> 00:02:52,330
Agus, ar deireadh, ní mór dúinn ach 108, mar sin caithfidh sé dul ar an deireadh ar ár liosta.

47
00:02:53,750 --> 00:02:56,180
Fógra gur féidir linn an deas, liosta in eagar.

48
00:02:56,180 --> 00:02:59,040
Gach uair i gcomparáid muid an chéad 2 gnéithe den 2 liosta

49
00:02:59,040 --> 00:03:02,730
bhí muid in ann chun a chinneadh an chéad bhall eile ón liosta cumaiscthe.

50
00:03:02,730 --> 00:03:08,070
Ciallaíonn sé seo go bhfuil má tá an liosta deiridh uimhreacha n, áit a bhfuil n anseo 8,

51
00:03:08,070 --> 00:03:12,610
ansin is gá dúinn ar an chuid is mó comparáidí n a fháil ar gach ceann de na huimhreacha ar an áit ceart.

52
00:03:13,230 --> 00:03:16,230
Tá a leithéid de algartam sin a reáchtáil i am líneach,

53
00:03:16,230 --> 00:03:18,090
ach ná bíodh imní ort faoi sin anseo.

54
00:03:18,570 --> 00:03:22,810
>> Ag baint úsáide as ár n-algartam le haghaidh a chumasc, is féidir linn a dhéanamh ar algartam saghas tapa chumaiscthe.

55
00:03:22,810 --> 00:03:25,170
Mar sin, a ligean ar a athshocrú ár liostaí.

56
00:03:35,210 --> 00:03:37,750
Tá 2 céimeanna móra sa phróiseas saghas chumaiscthe.

57
00:03:37,750 --> 00:03:41,500
Gcéad dul síos, scoilt leanúnach ar an liosta de na cupáin i leatha

58
00:03:41,500 --> 00:03:44,860
go dtí go bhfuil muid a bunch de liostaí le cupán ach 1 i dóibh.

59
00:03:44,860 --> 00:03:47,350
Ná bíodh imní ort má tá liosta corruimhir

60
00:03:47,350 --> 00:03:49,880
agus ní féidir leat a dhéanamh gearrtha breá glan eatarthu.

61
00:03:49,880 --> 00:03:53,750
Just a roghnú treallach a liosta a chur san áireamh an cupán breise isteach

62
00:03:53,750 --> 00:03:56,240
Mar sin, a ligean ar roinneadh na liostaí seo.

63
00:03:58,140 --> 00:04:01,310
Anois, tá muid 2 liosta.

64
00:04:04,120 --> 00:04:06,570
Anois, tá muid 4 liostaí.

65
00:04:10,350 --> 00:04:13,870
>> Agus anois ní mór dúinn 8 liostaí le cupán amháin i ngach liosta.

66
00:04:13,870 --> 00:04:16,630
Mar sin tá go bhfuil sé do chéim 1.

67
00:04:16,630 --> 00:04:22,230
Le haghaidh chéim 2, ní mór dúinn merge arís agus arís eile péirí liostaí baint úsáide as an algartam merge fhoghlaim muid roimh.

68
00:04:22,230 --> 00:04:29,160
A chumasc 108 agus 15, deireadh muid suas leis an liosta 15, 108.

69
00:04:30,330 --> 00:04:36,250
Cumasc 50 agus 4, deireadh muid suas le 4, 50.

70
00:04:36,960 --> 00:04:41,400
A chumasc 8 agus 42, ní mór dúinn deireadh suas le 8, 42.

71
00:04:42,790 --> 00:04:48,130
Agus a chumasc 23 agus 16, ní mór dúinn deireadh suas le 16, 23.

72
00:04:49,740 --> 00:04:52,450
Anois, tá gach ár liostaí de mhéid 2.

73
00:04:53,020 --> 00:04:56,180
Fógra go bhfuil gach ceann de na 4 liostaí curtha in eagar.

74
00:04:56,180 --> 00:04:59,160
>> Mar sin, is féidir linn tús a chumasc péirí liostaí arís.

75
00:04:59,160 --> 00:05:03,240
Cumasc 15 agus 108 agus 4 agus 50 -

76
00:05:03,240 --> 00:05:11,170
an chéad a chur ar an 4, ansin 15, ansin an 50, ansin an 108.

77
00:05:11,170 --> 00:05:15,120
A chumasc 8, 42 agus 16, 23,

78
00:05:15,120 --> 00:05:22,440
beimid ag tabhairt faoi ar dtús leis an 8, ansin an 16, ansin an 23, ansin an 42.

79
00:05:22,440 --> 00:05:27,370
Mar sin, anois ní mór dúinn ach 2 liosta de mhéid 4, tá gach ceann acu curtha in eagar.

80
00:05:27,370 --> 00:05:30,980
Mar sin, anois merge againn ar na 2 liosta.

81
00:05:30,980 --> 00:05:33,440
An Chéad muid a chur ar an 4.

82
00:05:33,440 --> 00:05:36,580
Ansin againn a chur ar an 8.

83
00:05:36,580 --> 00:05:50,700
Ansin againn a chur ar an 15 agus 16, ansin 23, ansin 42, ansin 50, ansin 108.

84
00:05:50,700 --> 00:05:52,220
Agus muid ag déanamh.

85
00:05:52,220 --> 00:05:54,900
Tá muid anois ar liosta in eagar.

86
00:05:54,900 --> 00:05:57,890
Mar sin, cé chomh tapa raibh sé seo, go díreach?

87
00:05:57,890 --> 00:06:02,000
I dtéarmaí teicniúla, tá merge sórtáil O (n log n),

88
00:06:02,000 --> 00:06:07,380
cé go bhfuil gach ceann de saghas mboilgeog, a shórtáil isteach, agus sórtáil roghnú O (n ²).

89
00:06:07,380 --> 00:06:11,120
Go deimhin, mar beidh tú ag foghlaim go luath, ní bheidh tú in ann teacht suas le saghas

90
00:06:11,120 --> 00:06:14,820
a dhéanann níos fearr ná O (n log n) i gcás go ginearálta.

91
00:06:14,820 --> 00:06:19,120
Arís, ná bíodh imní ort faoi seo nodaireacht O mór más rud é nach bhfuil tú ag feiceáil go fóill.

92
00:06:19,120 --> 00:06:23,490
>> Just a fhios go ciallaíonn sé seo más rud é go bhíomar ag iarraidh a shórtáil ar liosta mór i ndáiríre

93
00:06:23,490 --> 00:06:26,820
D'fhéadfadh saghas mboilgeog, a shórtáil isteach, agus a roghnú saghas a ghlacadh d'fhéadfadh a bheith

94
00:06:26,820 --> 00:06:29,500
bhfad níos faide ná mar a chumasadh saghas.

95
00:06:29,500 --> 00:06:33,210
Ní chiallaíonn sé go mbeidh merge sórtáil a bheith níos tapúla le haghaidh gach liosta

96
00:06:33,210 --> 00:06:36,220
nó fiú ar aon liosta amháin faoi mhéid áirithe.

97
00:06:36,220 --> 00:06:41,950
Mar shampla, d'fhéadfadh a bheith saghas isteach an saghas is tapúla le haghaidh gach liosta níos lú ná 5 heilimintí sin.

98
00:06:41,950 --> 00:06:47,360
I gcleachtas, merge sórtáil de ghnáth níos tapúla le haghaidh liostaí chomh beag agus is 50 heilimintí sin.

99
00:06:47,360 --> 00:06:51,120
>> Ach ní dhéanann an luas breise a thagann gan ar phraghas.

100
00:06:51,120 --> 00:06:54,770
Murab ionann agus ár n-cineál eile, a chur ar liosta agus a mhodhnú an liosta atá i bhfeidhm

101
00:06:54,770 --> 00:06:58,740
go dtí go bhfaigheann muid liosta curtha in eagar, ní mór merge sórtáil roinnt spás breise

102
00:06:58,740 --> 00:07:00,900
a chumasadh 2 liosta le chéile.

103
00:07:00,900 --> 00:07:04,690
Ní féidir linn a úsáid láithreach na liostaí atá á chumasc a stóráil ar an liosta cumaiscthe

104
00:07:04,690 --> 00:07:08,880
ós rud é a d'fhéadfadh muid a shárú gnéithe mór a chomhall fós a chumasc.

105
00:07:08,880 --> 00:07:13,540
Tá an spás le beagán de phraghas, ach tá sé de ghnáth ní míréasúnta.

106
00:07:13,540 --> 00:07:15,330
Agus sin é do sort chumaiscthe.

107
00:07:15,330 --> 00:07:18,490
>> Is é mo ainm Rob Bowden, agus tá sé seo CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- Agus roghnú saghas.

110
00:07:24,000 --> 00:07:25,880
[Gáirí]

111
00:07:25,880 --> 00:07:31,480
Ó, fuair a ghlacadh go amach freisin mar gheall ar athraigh mé conas a bhí i láthair mé é.

112
00:07:31,480 --> 00:07:35,680
Liosta ar thaobh na láimhe clé. Ba é sin a typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] screwed mé suas -

114
00:07:39,290 --> 00:07:41,190
[Gáirí]

115
00:07:41,190 --> 00:07:44,190
Níl a fhios agam cad -