>> [Ag seinm ceoil]
DOUG LLOYD: Is saghas Roghnú ina algartam sin, mar a d'fhéadfadh a bheith ag súil,
sórtálfar sraith na n-eilimintí.
Agus a thabhairt chun cuimhne algartam Is sraith céim-ar-chéim
de treoracha tasc a chríochnú.
>> I roghnú shórtáil an Is smaoineamh bunúsach seo,
teacht ar an ghné is lú neamhshórtáilte agus é a chur go dtí deireadh an liosta sórtáilte.
Go héifeachtach cad a dhéanann seo a thógáil liosta curtha in eagar, gné amháin ag an am.
Briseadh sé síos go dtí pseudocode d'fhéadfadh muid a lua an algartam
mar seo a leanas, arís seo go dtí go bhfanann aon eilimintí neamhshórtáilte.
Cuardaigh tríd an neamhshórtáilte sonraí a fháil ar an luach is lú,
ansin babhtála an luach is lú leis an an chéad ghné den chuid neamhshórtáilte.
>> D'fhéadfadh sé cabhrú a shamhlú seo, mar sin a ligean ar ghlacadh le breathnú ar seo.
Mar sin, seo, contend mé, ina sraith neamhshórtáilte agus tá mé
Léirigh sé ag léiriú go léir de na heilimintí atá daite dearg,
nach bhfuil siad curtha in eagar go fóill.
Is é seo an fad chuid neamhshórtáilte an eagar.
>> Mar sin, a ligean ar dul tríd na céimeanna de saghas roghnaithe a shórtáil seo eagar.
Mar sin arís, tá muid ag dul a athuair go dtí go bhfanann aon eilimintí neamhshórtáilte.
Táimid ag dul a chuardach trí na sonraí a fháil ar an luach is lú,
agus ansin babhtála go luach leis an an chéad ghné den chuid neamhshórtáilte.
>> Ceart anois, arís, ar an iomlán Is eagar an chuid neamhshórtáilte.
Gach ceann de na heilimintí dearg atá neamhshórtáilte.
Mar sin, táimid ag cuardach trí agus feicimid an luach is lú.
Tús a chur againn ag an tús, théann muid go dtí an deireadh,
feicimid go bhfuil an luach is lú, ceann amháin.
Mar sin, go bhfuil cuid amháin.
Agus ansin cuid a dó, a mhalartú go luach le an chéad ghné den chuid neamhshórtáilte,
nó an chéad eilimint dearg.
>> Sa chás seo, bheadh cúig, agus mar sin a mhalartú muid ar cheann agus cúig.
Nuair a dhéanaimid é seo, is féidir linn féach amhairc go bhfuil muid
ar athraíodh a ionad an ghné is lú luach an eagar, go dtí an tús.
Go héifeachtach sórtáil sin gné.
>> Agus mar sin is féidir linn a dhearbhú go deimhin agus luaigh go bhfuil ceann, atá curtha in eagar.
Agus mar sin beidh orainn a chur in iúl an chuid curtha in eagar ár n-eagar, trí dathú gorm é.
>> Anois táimid ag arís ach an próiseas arís.
Táimid ag cuardach tríd an chuid neamhshórtáilte de an eagar chun teacht ar an eilimint is lú.
Sa chás seo, tá sé an dá.
>> Babhtála go bhfuil an chéad eilimint den pháirt neamhshórtáilte.
Sa chás seo dhá tharlaíonn chomh maith le bheith an chéad ghné den chuid neamhshórtáilte.
Mar sin bhabhtáil muid beirt leis féin, a ndáiríre a fhágann ach dhá
áit a bhfuil sé, agus tá sé curtha in eagar.
Ag leanúint ar, táimid ag cuardach trí chun teacht ar an eilimint is lú.
Tá sé trí.
Babhtála dúinn é leis an chéad eilimint, a bhfuil cúig.
Agus anois tá trí curtha in eagar.
>> Táimid ag cuardach trí arís, agus táimid ag teacht ar go bhfuil an ghné is lú a ceathair.
Babhtála dúinn é leis an chéad ghné den chuid neamhshórtáilte, agus anois tá sé ceithre curtha in eagar.
>> Fháil againn go bhfuil cúig an eilimint is lú.
Babhtála dúinn é leis an chéad eilimint den pháirt neamhshórtáilte.
Agus anois tá cúig curtha in eagar.
>> Agus ansin ar deireadh, ár n- Is éard atá mar chuid neamhshórtáilte
de ach eilimint amháin, mar sin táimid ag cuardach trí
agus a fháil againn go bhfuil sé an is lú, agus go deimhin, ach amháin eilimint.
Agus ansin is féidir linn a rá go bhfuil sé curtha in eagar.
Agus anois tá muid aistrigh ár sraith ó bheith neamhshórtáilte hiomlán
i dearg, chun curtha in eagar go hiomlán i gorm, ag baint úsáide as saghas roghnaithe.
>> Mar sin, cad é an cás is measa anseo?
Go maith i an ceann is measa glan cás, ní mór dúinn chun breathnú ar
gach ceann de na heilimintí an eagar a teacht ar an ghné is lú neamhshórtáilte,
agus ní mór dúinn a dhéanamh arís an próiseas seo n amanna.
Uair amháin le haghaidh gach eilimint den eagar mar gheall orainn ach, sa algartam,
saghas gné amháin ag an am.
>> Cad é an scéal chás is fearr?
Bhuel tá sé díreach mar an gcéanna, ceart?
Ní mór dúinn i ndáiríre chun dlús fóill trí gach gné amháin den eagar
d'fhonn a dheimhniú go bhfuil sé, go deimhin, an eilimint is lú.
>> Mar sin, an cás is measa runtime, táimid ag a athdhéanamh le próiseas n uair,
uair amháin le haghaidh gach ceann de na heilimintí n.
Agus sa chás is fearr, ní mór dúinn a dhéanamh an chéanna.
>> Mar sin, smaoineamh ar ais go dtí ár bosca uirlisí castacht ríomhaireachtúil,
cad a cheapann tú go bhfuil an ceann is measa runtime cás le haghaidh saghas roghnaithe?
Cad a cheapann tú go bhfuil an chuid is fearr runtime cás le haghaidh saghas roghnaithe?
>> An raibh tú buille faoi thuairim Big O de n cearnógach, agus Big Omega na n cearnógach?
Gur mhaith leat a bheith ceart.
Glacfar iad, i ndáiríre, an cás is measa agus cás a reáchtáil is fearr
amanna, d'saghas roghnaithe.
>> Tá mé Doug Lloyd.
Is é seo an CS50.