[Powered by Google Translate] [SORT mboilgeog] [JACKSON STEINKAMP Ollscoil Harvard] É [SEO CS50. CS50TV] Is é Sórtáil mboilgeog sampla de algartam sórtáil - is é sin, nós imeachta chun sórtáil sraith na n-eilimintí i ardaitheach nó ord íslitheach. Mar shampla, má raibh tú a shórtáil le sraith ina bhfuil an líon [3, 5, 2, 9], bheadh ​​feidhme i gceart Sórtáil mboilgeog ais eagar curtha in eagar [2, 3, 5, 9] in ord ardaitheach. Anois, tá mé ag dul a mhíniú i pseudocode conas a oibríonn an algartam. 

Ligean le rá táimid ag sórtáil liosta de 5 slánuimhreacha - 3, 2, 9, 6, agus 5. Tosaíonn an algartam trí bhreathnú ar an dá ghné den chéad uair, 3 agus 2, agus seiceáil má tá siad as ord i gcoibhneas lena chéile. Tá siad - 3 níos mó ná 2. Chun a bheith in ord dul suas, ba chóir dóibh a bheith ar an bealach eile timpeall. Mar sin, babhtála againn orthu. Anois Breathnaíonn an liosta mar seo: [2, 3, 9, 6, 5]. 

Next, táimid ag na gnéithe dara agus an tríú, 3 agus 9. Tá siad san ord ceart i gcoibhneas lena chéile. Is é sin, tá 3 níos lú ná 9 mar sin nach bhfuil an algartam babhtála leo. Next, táimid ag 9 agus 6. Tá siad as ord. 

Mar sin, ní mór dúinn a mhalartú leo toisc go bhfuil 9 níos mó ná 6. Ar deireadh, táimid ag an dá slánuimhreacha seo caite, 9 agus 5. Tá siad as ord, mar sin ní mór iad a mhalartú. Tar éis an pas chéad iomlán tríd an liosta, Breathnaíonn sé mar seo: [2, 3, 6, 5, 9]. Gan olc. Tá sé curtha in eagar beagnach. Ach ní mór dúinn a reáchtáil trí mheán an liosta arís a fháil curtha in eagar go hiomlán. Dhá níos lú ná 3, mar sin ní féidir linn a mhalartú leo. 

Trí níos lú ná 6, mar sin ní féidir linn a mhalartú leo. Sé níos mó ná 5. Mhalartaigh againn. Sé níos lú ná 9. Ní chuirimid mhalartú. Tar éis an pas dara tríd, tá sé mar seo: [2, 3, 5, 6, 9]. Perfect. Anois, a ligean ar scríobh sé i pseudocode. Go bunúsach, do gach eilimint sa liosta, ní mór dúinn chun breathnú ar sé agus an eilimint go díreach ina cheart. Má tá siad as ord i gcoibhneas lena chéile - is é sin, más rud é an ghné ar an taobh clé níos mó ná an ceann ar dheis - ba chóir dúinn a mhalartú ar an dá ghné. 

Déanaimid é seo le haghaidh gach gné ar an liosta, agus atá déanta againn ar cheann pas a fháil tríd. Anois, tá muid díreach a dhéanamh ar an am pas-trí leor chun a chinntiú ar an liosta , tá curtha in eagar go hiomlán i gceart. Ach cé mhéad uair a bhfuil muid ag dul tríd an liosta ráthaíocht a thabhairt go bhfuil muid ag déanamh? Bhuel, tá an cás is measa ar chás má táimid tar éis liosta go hiomlán ar gcúl. Ansin a thógann sé roinnt pas-throughs comhionann leis an líon gnéithe n-1. Más rud é nach bhfuil an ciall intuitively, smaoineamh ar chás simplí - an liosta [2, 1]. 

Tá sé seo ag dul a ghlacadh pas amháin-trí a shórtáil i gceart. [3, 2, 1] - Is é an cás is measa go bhfuil 3 ghné curtha in eagar ar gcúl, tá sé ag dul go dtí 2 atriallta a ghlacadh chun a shórtáil. Tar éis atriall, tá sé [2, 1, 3]. An táirgeacht dara sraith curtha in eagar [1, 2, 3]. Mar sin, tá a fhios agat go bhfuil tú riamh dul tríd an eagar, go ginearálta, níos mó ná n-1 uair, áit a bhfuil n líon na n-eilimintí sa eagar. Sé ar a dtugtar Sórtáil mboilgeog mar gheall ar an claonadh a bhíonn gnéithe is mó a 'mboilgeog-suas' leis an gceart go tapa go leor. Go deimhin, tá an algartam iompar an-suimiúil. 

Tar éis iterations m tríd an eagar ar fad, na heilimintí m rightmost a ráthú chun a shórtáil i n-áit ceart. Más mian leat a fheiceáil seo le haghaidh duit féin, is féidir linn iarracht é a chur ar liosta go hiomlán ar gcúl [9, 6, 5, 3, 2]. Tar éis pas a fháil tríd an liosta ar fad, [Fuaim na scríbhneoireachta] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] Is é an ghné rightmost 9 ina áit chuí. Tar éis an dara pas-trí, beidh an 6 bhfuil 'bubbled-suas' leis an áit rightmost an dara. Tá an dhá ghné ar dheis - 6 agus 9 - beidh a bheith ina n-áiteanna ceart tar éis an chéad dá pas-throughs. 

Mar sin, conas is féidir linn seo a úsáid chun Optamaigh an algartam? Bhuel, tar éis atriall tríd an eagar ní mór dúinn i ndáiríre a sheiceáil leis an eilimint rightmost mar tá a fhios againn tá sé curtha in eagar. Tar éis dhá atriallta, tá a fhios againn do cinnte an dá rightmost heilimintí i bhfeidhm. Mar sin, go ginearálta, tar éis atriallta k tríd an raon iomlán, seiceáil na heilimintí k deireanach iomarcach ó tá a fhios againn tá siad sa suíomh ceart cheana féin. 

Mar sin, má tá tú ag sórtáil le sraith de ghnéithe n, ar an leagan den chéad uair - tá you'll a shórtáil gach ceann de na heilimintí - an chéad n-0. Ar an dara leagan, beidh ort chun breathnú ar gach ceann de na heilimintí rud ach an - an chéad n-1. Eile ad'fhéadfadh a bheith leas iomlán a bhaint a sheiceáil má tá an liosta in eagar cheana tar éis gach leagan. Má tá sé curtha in eagar cheana féin, ní mór dúinn a dhéanamh atriallta ar bith níos mó tríd an liosta. Conas is féidir linn seo a dhéanamh? Bhuel, más rud é nach bhfuil muid a dhéanamh ar aon bhabhtálacha ar pas-trí an liosta, tá sé soiléir go bhfuil an liosta a bhí curtha in eagar cheana féin toisc nach raibh muid a mhalartú rud ar bith. Mar sin, táimid cinnte nach bhfuil a shórtáil arís. 

B'fhéidir go bhféadfaí tú a thúsú athróg bratach ar a dtugtar 'Ní curtha in eagar' a falsa agus é a athrú go fíor má tá tú a mhalartú aon ghnéithe ar amháin atriall tríd an eagar. Nó dul céanna, a dhéanamh cuntar a chomhaireamh cé mhéad malairtí a dhéanann tú ar aon leagan ar leith. Ag deireadh an leagan, más rud é nach raibh tú babhtála aon cheann de na heilimintí, tá a fhios agat go bhfuil an liosta in eagar cheana féin agus tú ag déanamh. Sórtáil Bubble, cosúil le halgartaim sórtáil eile ar féidir, a bheith tweaked a bheith ag obair le haghaidh aon ghnéithe a bhfuil modh a ordú. 

Is é sin, mar gheall ar dhá ghné ar a bhfuil tú ar bhealach a rá má tá an chéad cheann níos mó ná, cothrom le nó níos lú ná an dara. Mar shampla, d'fhéadfaí tú a shórtáil litreacha na haibítre ag rá go <b, b <c, etc Nó d'fhéadfaí tú a shórtáil laethanta na seachtaine ina bhfuil dé domhnaigh níos lú ná Dé Luain atá níos lú ná Dé Máirt. 

Is é Sórtáil de mboilgeog trí aon mhodh algartam sórtáil an-éifeachtach nó go tapa. Is í an gcás is measa runtime Big O n ² toisc go bhfuil tú a dhéanamh atriallta n tríd an liosta seiceáil na heilimintí go léir n gach pas-trí, nxn = n ². Ciallaíonn an t-am ar siúl go mar an líon de na gnéithe atá tú méaduithe sórtáil, Méadaíonn sé seo an t-am a reáchtáil quadratically. 

Ach más rud é nach bhfuil éifeachtacht ábhar mór imní é do chlár nó má tá tú ag sórtáil ach líon beag na n-eilimintí, d'fhéadfá a fháil Sórtáil Bubble úsáideach mar gheall ar Tá sé ar cheann de na halgartaim simplí sórtáil a thuiscint agus chun cód. Tá sé freisin ar bhealach iontach taithí a fháil le aistriú a teoiriciúil algartam i cód feidhmiú iarbhír. Bhuel, sin é Sórtáil mboilgeog ar do shon. Go raibh maith agat chun breathnú ar. CS50.TV