1
00:00:00,000 --> 00:00:05,726
>> [Ag seinm ceoil]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Is saghas Roghnú ina
algartam sin, mar a d'fhéadfadh a bheith ag súil,

3
00:00:08,600 --> 00:00:10,470
sórtálfar sraith na n-eilimintí.

4
00:00:10,470 --> 00:00:12,470
Agus a thabhairt chun cuimhne algartam
Is sraith céim-ar-chéim

5
00:00:12,470 --> 00:00:15,260
de treoracha tasc a chríochnú.

6
00:00:15,260 --> 00:00:17,580
>> I roghnú shórtáil an
Is smaoineamh bunúsach seo,

7
00:00:17,580 --> 00:00:22,080
teacht ar an ghné is lú neamhshórtáilte agus
é a chur go dtí deireadh an liosta sórtáilte.

8
00:00:22,080 --> 00:00:26,970
Go héifeachtach cad a dhéanann seo a thógáil
liosta curtha in eagar, gné amháin ag an am.

9
00:00:26,970 --> 00:00:29,800
Briseadh sé síos go dtí pseudocode
d'fhéadfadh muid a lua an algartam

10
00:00:29,800 --> 00:00:34,490
mar seo a leanas, arís seo go dtí go
bhfanann aon eilimintí neamhshórtáilte.

11
00:00:34,490 --> 00:00:38,660
Cuardaigh tríd an neamhshórtáilte
sonraí a fháil ar an luach is lú,

12
00:00:38,660 --> 00:00:44,130
ansin babhtála an luach is lú leis an
an chéad ghné den chuid neamhshórtáilte.

13
00:00:44,130 --> 00:00:47,130
>> D'fhéadfadh sé cabhrú a shamhlú seo,
mar sin a ligean ar ghlacadh le breathnú ar seo.

14
00:00:47,130 --> 00:00:49,710
Mar sin, seo, contend mé, ina
sraith neamhshórtáilte agus tá mé

15
00:00:49,710 --> 00:00:53,040
Léirigh sé ag léiriú go léir
de na heilimintí atá daite dearg,

16
00:00:53,040 --> 00:00:54,420
nach bhfuil siad curtha in eagar go fóill.

17
00:00:54,420 --> 00:00:57,670
Is é seo an fad
chuid neamhshórtáilte an eagar.

18
00:00:57,670 --> 00:01:02,020
>> Mar sin, a ligean ar dul tríd na céimeanna de
saghas roghnaithe a shórtáil seo eagar.

19
00:01:02,020 --> 00:01:05,296
Mar sin arís, tá muid ag dul a athuair
go dtí go bhfanann aon eilimintí neamhshórtáilte.

20
00:01:05,296 --> 00:01:07,920
Táimid ag dul a chuardach trí na
sonraí a fháil ar an luach is lú,

21
00:01:07,920 --> 00:01:11,990
agus ansin babhtála go luach leis an
an chéad ghné den chuid neamhshórtáilte.

22
00:01:11,990 --> 00:01:14,380
>> Ceart anois, arís, ar an iomlán
Is eagar an chuid neamhshórtáilte.

23
00:01:14,380 --> 00:01:16,534
Gach ceann de na heilimintí dearg atá neamhshórtáilte.

24
00:01:16,534 --> 00:01:18,700
Mar sin, táimid ag cuardach trí agus
feicimid an luach is lú.

25
00:01:18,700 --> 00:01:20,533
Tús a chur againn ag an tús,
théann muid go dtí an deireadh,

26
00:01:20,533 --> 00:01:23,630
feicimid go bhfuil an luach is lú, ceann amháin.

27
00:01:23,630 --> 00:01:24,860
Mar sin, go bhfuil cuid amháin.

28
00:01:24,860 --> 00:01:29,440
Agus ansin cuid a dó, a mhalartú go luach le
an chéad ghné den chuid neamhshórtáilte,

29
00:01:29,440 --> 00:01:31,340
nó an chéad eilimint dearg.

30
00:01:31,340 --> 00:01:34,980
>> Sa chás seo, bheadh
cúig, agus mar sin a mhalartú muid ar cheann agus cúig.

31
00:01:34,980 --> 00:01:37,320
Nuair a dhéanaimid é seo, is féidir linn
féach amhairc go bhfuil muid

32
00:01:37,320 --> 00:01:41,260
ar athraíodh a ionad an ghné is lú luach
an eagar, go dtí an tús.

33
00:01:41,260 --> 00:01:43,920
Go héifeachtach sórtáil sin gné.

34
00:01:43,920 --> 00:01:47,520
>> Agus mar sin is féidir linn a dhearbhú go deimhin
agus luaigh go bhfuil ceann, atá curtha in eagar.

35
00:01:47,520 --> 00:01:52,080
Agus mar sin beidh orainn a chur in iúl an chuid curtha in eagar
ár n-eagar, trí dathú gorm é.

36
00:01:52,080 --> 00:01:53,860
>> Anois táimid ag arís ach an próiseas arís.

37
00:01:53,860 --> 00:01:57,430
Táimid ag cuardach tríd an chuid neamhshórtáilte de
an eagar chun teacht ar an eilimint is lú.

38
00:01:57,430 --> 00:01:59,000
Sa chás seo, tá sé an dá.

39
00:01:59,000 --> 00:02:02,100
>> Babhtála go bhfuil an chéad
eilimint den pháirt neamhshórtáilte.

40
00:02:02,100 --> 00:02:05,540
Sa chás seo dhá tharlaíonn chomh maith le bheith
an chéad ghné den chuid neamhshórtáilte.

41
00:02:05,540 --> 00:02:08,650
Mar sin bhabhtáil muid beirt leis féin,
a ndáiríre a fhágann ach dhá

42
00:02:08,650 --> 00:02:11,257
áit a bhfuil sé, agus tá sé curtha in eagar.

43
00:02:11,257 --> 00:02:13,840
Ag leanúint ar, táimid ag cuardach trí
chun teacht ar an eilimint is lú.

44
00:02:13,840 --> 00:02:15,030
Tá sé trí.

45
00:02:15,030 --> 00:02:17,650
Babhtála dúinn é leis an chéad
eilimint, a bhfuil cúig.

46
00:02:17,650 --> 00:02:19,450
Agus anois tá trí curtha in eagar.

47
00:02:19,450 --> 00:02:22,440
>> Táimid ag cuardach trí arís, agus táimid ag
teacht ar go bhfuil an ghné is lú a ceathair.

48
00:02:22,440 --> 00:02:28,070
Babhtála dúinn é leis an chéad ghné den
chuid neamhshórtáilte, agus anois tá sé ceithre curtha in eagar.

49
00:02:28,070 --> 00:02:29,910
>> Fháil againn go bhfuil cúig
an eilimint is lú.

50
00:02:29,910 --> 00:02:32,900
Babhtála dúinn é leis an chéad
eilimint den pháirt neamhshórtáilte.

51
00:02:32,900 --> 00:02:34,740
Agus anois tá cúig curtha in eagar.

52
00:02:34,740 --> 00:02:36,660
>> Agus ansin ar deireadh, ár n-
Is éard atá mar chuid neamhshórtáilte

53
00:02:36,660 --> 00:02:38,576
de ach eilimint amháin,
mar sin táimid ag cuardach trí

54
00:02:38,576 --> 00:02:41,740
agus a fháil againn go bhfuil sé an
is lú, agus go deimhin, ach amháin eilimint.

55
00:02:41,740 --> 00:02:44,906
Agus ansin is féidir linn a rá go bhfuil sé curtha in eagar.

56
00:02:44,906 --> 00:02:47,530
Agus anois tá muid aistrigh ár sraith
ó bheith neamhshórtáilte hiomlán

57
00:02:47,530 --> 00:02:52,660
i dearg, chun curtha in eagar go hiomlán
i gorm, ag baint úsáide as saghas roghnaithe.

58
00:02:52,660 --> 00:02:54,920
>> Mar sin, cad é an cás is measa anseo?

59
00:02:54,920 --> 00:02:57,830
Go maith i an ceann is measa glan
cás, ní mór dúinn chun breathnú ar

60
00:02:57,830 --> 00:03:02,170
gach ceann de na heilimintí an eagar a
teacht ar an ghné is lú neamhshórtáilte,

61
00:03:02,170 --> 00:03:04,750
agus ní mór dúinn a dhéanamh arís
an próiseas seo n amanna.

62
00:03:04,750 --> 00:03:09,090
Uair amháin le haghaidh gach eilimint den eagar
mar gheall orainn ach, sa algartam,

63
00:03:09,090 --> 00:03:12,180
saghas gné amháin ag an am.

64
00:03:12,180 --> 00:03:13,595
>> Cad é an scéal chás is fearr?

65
00:03:13,595 --> 00:03:15,040
Bhuel tá sé díreach mar an gcéanna, ceart?

66
00:03:15,040 --> 00:03:18,440
Ní mór dúinn i ndáiríre chun dlús fóill trí
gach gné amháin den eagar

67
00:03:18,440 --> 00:03:22,040
d'fhonn a dheimhniú go bhfuil sé,
go deimhin, an eilimint is lú.

68
00:03:22,040 --> 00:03:26,760
>> Mar sin, an cás is measa runtime, táimid ag
a athdhéanamh le próiseas n uair,

69
00:03:26,760 --> 00:03:28,960
uair amháin le haghaidh gach ceann de na heilimintí n.

70
00:03:28,960 --> 00:03:31,940
Agus sa chás is fearr,
ní mór dúinn a dhéanamh an chéanna.

71
00:03:31,940 --> 00:03:35,340
>> Mar sin, smaoineamh ar ais go dtí ár
bosca uirlisí castacht ríomhaireachtúil,

72
00:03:35,340 --> 00:03:39,250
cad a cheapann tú go bhfuil an ceann is measa
runtime cás le haghaidh saghas roghnaithe?

73
00:03:39,250 --> 00:03:41,840
Cad a cheapann tú go bhfuil an chuid is fearr
runtime cás le haghaidh saghas roghnaithe?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> An raibh tú buille faoi thuairim Big O de n cearnógach,
agus Big Omega na n cearnógach?

76
00:03:49,325 --> 00:03:49,950
Gur mhaith leat a bheith ceart.

77
00:03:49,950 --> 00:03:52,490
Glacfar iad, i ndáiríre, an
cás is measa agus cás a reáchtáil is fearr

78
00:03:52,490 --> 00:03:55,100
amanna, d'saghas roghnaithe.

79
00:03:55,100 --> 00:03:56,260
>> Tá mé Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Is é seo an CS50.

81
00:03:58,600 --> 00:04:00,279