[Ag seinm ceoil] DOUG LLOYD: Ceart go leor, mar sin Is mboilgeog saghas algartaim Is féidir leat é a úsáid a shórtáil le sraith na n-eilimintí. A ligean ar ghlacadh le breathnú ar conas a oibríonn sé. 

Mar sin, an smaoineamh bunúsach taobh thiar de Tá mboilgeog saghas seo. Ba mhaith linn go ginearálta a bhogadh níos airde gnéithe luacháil go ginearálta leis an gceart, agus eilimintí luacháil níos ísle go ginearálta ar an taobh clé, mar ba mhaith linn a bheith ag súil. Ba mhaith linn na rudaí níos ísle a bheith ag an tús, agus na rudaí níos airde a bheith ag an deireadh. 

Conas is féidir linn é seo a? Go maith i cód pseudocode, d'fhéadfadh muid a rá, a ligean ar shocrú cuntar babhtála a luach neamh-náid. Beidh muid a fheiceáil cén fáth a dhéanann muid go sa dara. Agus ansin dúinn arís ar an méid seo a leanas próiseas go dtí go bhfuil an gcuntar babhtála 0, nó go dtí go ndéanann dúinn aon babhtálacha ar chor ar bith. 

Athshocraigh an gcuntar babhtála a 0 mura bhfuil sé cheana 0. Ansin, breathnú ar gach péire aice na n-eilimintí. Má tá na dhá ghné ní in ord, babhtála iad, agus cuir 1 leis an gcuntar babhtála. Má tá tú ag smaoineamh faoi seo sula tú visualize é, faoi ​​deara go mbeidh an bogadh níos ísle gnéithe luacháil ar an taobh clé agus níos airde gnéithe do cheart meas, ag déanamh go héifeachtach cad ba mhaith linn a dhéanamh, a bhfuil bogadh na grúpaí na n-eilimintí sa tslí sin. A ligean ar a shamhlú conas an D'fhéadfadh cuma baint úsáide as ár sraith go úsáid againn chun tástáil amach na halgartaim. Ní mór dúinn le sraith neamhshórtáilte anseo arís, le fios ag gach ceann de na heilimintí a bheith i dearg. Agus leag mé mo gcuntar babhtála le luach nonzero. Roghnaigh mé treallach diúltach 1-- nach bhfuil sé 0. Is mian linn a dhéanamh arís ar an bpróiseas seo go dtí an gcuntar babhtála Is 0. Sin é an fáth a leag mé mo babhtála gcuntar le roinnt luach neamh-náid, mar gheall ar shlí eile ar an Bheadh ​​gcuntar babhtála bheith 0. Ní bheadh ​​muid ag cur tús fiú an próiseas an algartam. Mar sin arís, are-- na céimeanna athshocrú an gcuntar babhtála chun 0, ansin féachaint ar gach aice péire, agus má tá siad as ord, babhtála iad, agus cuir 1 go dtí an gcuntar babhtála. Mar sin, a ligean ar tús a chur leis an bpróiseas seo. Mar sin, is é an chéad rud a dhéanann muid a leag muid an gcuntar babhtála chun 0, agus ansin tús a chur orainn ag lorg ag gach beirt in aice láimhe. 

Mar sin, táimid an chéad tús féachaint ar 5 agus 2. Feicimid go bhfuil siad amach as ordú agus mar sin táimid ag babhtála iad. Agus muid cuir 1 leis an gcuntar babhtála. Mar sin, anois tá ár gcuntar babhtála 1, agus 2 agus 5 curtha aistrigh. Anois táimid ag arís ar an bpróiseas arís. 

Táimid ag an péire eile in aice láimhe, 5 agus 1-- tá siad chomh maith as ord, mar sin againn babhtála iad agus cuir 1 a ghabhann leis an gcuntar babhtála. Ansin táimid ag 5 agus 3. Tá siad as ord, mar sin táimid ag babhtála iad agus táimid ag cuir 1 leis an gcuntar babhtála. Ansin táimid ar 5 agus 6. Tá siad in ord, mar sin ní bhfuil againn i ndáiríre gá aon rud a mhalartú an am seo. Ansin táimid ag 6 agus 4. Tá siad freisin as ord, mar sin táimid ag babhtála iad agus táimid ag cuir 1 leis an gcuntar babhtála. 

Anois faoi deara cad a tharla. Táimid tar éis ar athraíodh a ionad 6 léir ar an mbealach go dtí deireadh. Mar sin, i saghas roghnú, má tá tú le feiceáil go bhfuil físeán, cad a rinne muid go raibh dar críoch muid suas ag gluaiseacht an eilimintí is lú i bhfoirgneamh an sraith sórtáilte go bunúsach ó chlé go deas, is lú go dtí mó. I gcás na mboilgeog saghas, má tá muid tar éis an algartam áirithe, táimid ag dul i ndáiríre a bheith ag tógáil an sraith sórtáilte ó ceart ar chlé, is mó a is lú. Táimid tar éis a bubbled héifeachtach 6, an luach is mó, léir ar an mbealach go dtí deireadh. 

Agus mar sin is féidir linn a dhearbhú anois go bhfuil curtha in eagar, agus sa todhchaí iterations-- ag dul tríd an eagar again-- nach bhfuil againn a bhreithniú 6 níos mó. Ní mór dúinn ach a mheas na heilimintí neamhshórtáilte nuair a muid ag féachaint ar péirí cóngaracha. Mar sin, ní mór dúinn críochnaithe amháin pas a fháil trí mboilgeog saghas. Mar sin, anois táimid ag dul ar ais go dtí an cheist, arís go dtí go bhfuil an gcuntar babhtála 0. Bhuel an gcuntar babhtála 4, mar sin táimid ag dul a choinneáil ar athrá ar an bpróiseas arís. 

Táimid ag dul a athshocrú an gcuntar babhtála chun 0, agus breathnú ar gach péire in aice láimhe. Mar sin, tús a chur againn le 2 agus tá siad 1-- as ord, mar sin againn babhtála iad agus cuir muid 1 go dtí an gcuntar babhtála. 2 agus 3, tá siad in ord. Ní chuirimid gá aon rud a dhéanamh. 3 agus 5 in ord. Ní chuirimid gá aon rud a dhéanamh ann. 

5 agus 4, tá siad amach ar ordú, agus mar sin táimid ag Ní mór a mhalartú leo agus cuir 1 a ghabhann leis an gcuntar babhtála. Agus anois tá muid ar athraíodh a ionad 5, an ghné eile is mó, go dtí deireadh an chuid neamhshórtáilte. Ionas gur féidir linn glaoch anois go mar chuid den chuid curtha in eagar. 

Anois tá tú ag lorg ar an scáileán agus is féidir a insint is dócha, agus is féidir liom, go bhfuil an eagar Tá curtha in eagar ceart anois. Ach ní féidir linn a chruthú go fóill. Ní chuirimid bhfuil ráthaíocht go bhfuil sé curtha in eagar. Ach tá sé seo i gcás an babhtála gcuntar dul le teacht i spraoi. 

Mar sin, tá muid pas i gcrích. Is é an gcuntar babhtála 2. Mar sin, táimid ag dul a dhéanamh arís an próiseas seo arís, arís go dtí go bhfuil an gcuntar babhtála 0. Athshocraigh an gcuntar babhtála a 0. Mar sin, beidh orainn a athshocrú é. 

Anois féach ar gach péire in aice láimhe. Sin in ord, 1 agus 2. 2 agus 3 in ord. 3 agus 4 in ord. Mar sin, ag an bpointe seo, faoi deara atá i gcrích againn ag féachaint ar gach péire in aice láimhe, ach tá an gcuntar babhtála fós 0. 

Más rud é nach bhfuil againn a athrú aon ghnéithe, ansin siad Ní mór a bheith in ord, ag bhua an phróisis. Agus mar sin ar éifeachtacht de shaghas, Is breá go eolaithe ríomhaire againn, Tá féidir linn a dhearbhú anois Ní mór an eagar ar fad a shórtáil, mar nach raibh muid a mhalartú aon eilimintí. Sin go leor go deas. 

Mar sin, cad é an cás is measa scéal le mboilgeog saghas? Sa chás is measa is an eagar in ord droim ar ais go hiomlán, agus mar sin ní mór dúinn a mboilgeog gach de na heilimintí móra go léir an mbealach trasna an eagar. Agus ní mór dúinn go héifeachtach chomh maith le mboilgeog gach ceann de na heilimintí beag ar ais léir ar an mbealach ar fud an eagar, freisin. Mar sin, tá gach ceann de na heilimintí n a bhogadh thar gach ceann de na heilimintí n eile. Mar sin, go bhfuil an cás is measa. Sa chás is fearr scéal áfach, is é seo beagán difriúil ó saghas roghnú. Is é an eagar cheana curtha in eagar nuair a théann muid i. Nach bhfuil againn a dhéanamh ar aon babhtálacha ar an chéad pas. Mar sin, d'fhéadfadh muid chun breathnú ag níos lú heilimintí, ceart? Ní chuirimid a athdhéanamh seo a phróiseáil roinnt huaire níos mó. 

Mar sin, cad a chiallaíonn? Mar sin, cad é an cás is measa do mboilgeog a shórtáil, agus cad atá an scéal chás is fearr le haghaidh mboilgeog saghas? An raibh tú buille faoi thuairim é seo? Sa chás is measa a bhfuil tú a iterate trasna na heilimintí n n amanna. Mar sin, tá an cás is measa cearnaithe n. 

Má tá an eagar breá sórtáilte áfach, tú ach chun breathnú ar gach ceann de na heilimintí uair amháin. Agus má tá an gcuntar babhtála fós 0, Is féidir leat a rá go bhfuil an eagar curtha in eagar. Agus mar sin sa chás is fearr, is é seo iarbhír níos fearr ná rogha sort-- tá sé óimige de n. 

Tá mé Doug Lloyd. Is é seo an CS50.