[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