Modhanna a shórtáil i gclárú: sórtáil de réir "mboilgeog"

Ní mheastar gurb é an modh is tapúla a shórtáiltear le mboilgeog ach amháin, dúnann sé an liosta de na bealaí is moille le hordú. Mar sin féin, tá a buntáistí aige freisin. Mar sin, is é an modh bubble a shórtáil an réiteach is loighciúil agus nádúrtha ar an bhfadhb, más gá duit na heilimintí a shocrú in ord áirithe. Bainfidh gnáth-dhuine, mar shampla, é a úsáid de láimh, ach trí intuition.

Cén áit a tháinig an t-ainm neamhghnách seo?

Fuarthas ainm an mhodha ag baint úsáide as analaí le boilgeoga aeir in uisce. Is meafar é seo. Díreach mar a n-ardóidh boilgeoga beaga aeir go barr - toisc go bhfuil a dlús níos mó ná aon leacht (sa chás seo - uisce), agus gach eilimint den eagar, is lú an luach is mó é, is é an méid is mó a dhéanann sé a bhealach go dtí tús liosta na n-uimhreacha.

Cur síos ar an algartam

Déantar socrú mboilgeog mar seo a leanas:

• An chéad pas: tógtar eilimintí an tsraith uimhreacha in dhá agus déantar iad a chur i gcomparáid i mbeirteanna freisin. Más rud é i dhá cheann de na heilimintí go bhfuil an chéad luach níos mó ná an dara ceann, déanann an clár a n-áiteanna a mhalartú;
• dá bhrí sin, an líon is mó na n misses an deireadh an eagar. Cé go bhfanann na heilimintí go léir, de réir mar a bhí siad, in ord chaos agus go dteastaíonn uathu tuilleadh sórtála;
• Dá bhrí sin, tá gá le pas dara: déantar é a léiriú de réir analaí leis an gceann roimhe seo (tuairiscithe cheana) agus tá roinnt comparáidí aige - lúide ceann amháin;
• Ag an bpas, tá an líon trí chomparáid níos lú ná an dara ceann, agus tá an deuce dhá ná an chéad cheann. Agus mar sin de;
• Déanaimid achoimre go bhfuil comparáidí idir gach pas (i líon, uimhir shonrach) lúide (líon na n-pas).

Is féidir fiú algartam níos giorra den chlár amach anseo a scríobh mar seo a leanas:

• Seiceáiltear líon na n-uimhreacha go dtí go bhfuarthas dhá uimhir, agus ní mór an dara ceann a bheith níos mó ná an chéad cheann;
• Tá sé suite go mícheart i ndáil le gach eilimint eile den eagar, babhtálacha an chláir.

Pseudocode bunaithe ar an algartam a thuairiscítear

Is é seo a leanas an cur chun feidhme is simplí:

Nós imeachta Sortirovka_Puzirkom;

Tosaigh

timthriall haghaidh j ó nachalnii_index go konechii_index;

timthriall ar feadh i ó nachalnii_index go konechii_index-1;

más rud é Massiv [i]> Massiv [i + 1] (eilimint an chéad níos mó ná an dara), ansin:

(Athraigh na luachanna in áiteanna);

An Deireadh

Ar ndóigh, níl an simplíocht seo ach níos measa ar an staid: an t-algartam níos simplí, is mó a léiríonn sé na heasnaimh uile. Tá an-íditheach ró-mhór fiú le haghaidh sraith bheag (tagann an ghaolta seo anseo: d'fhéadfadh an méid ama a bheith cosúil le beagán don duine meánmhéide, ach i ngach dara nó fiú milleoicéad ar an gcuntas).

Ghlac sé cur i bhfeidhm níos fearr. Mar shampla, ag cur san áireamh luachanna luachanna sa ghréasán i roinnt áiteanna:

Nós imeachta Sortirovka_Puzirkom;

Tosaigh

sortirovka = fíor;

timthriall go dtí go = sortirovka fíor;

sortirovka = bréagach;

timthriall ar feadh i ó nachalnii_index go konechii_index-1;

más rud é Massiv [i]> Massiv [i + 1] (eilimint an chéad níos mó ná an dara), ansin:

(Athraíonn muid na heilimintí in áiteanna);

sortirovka = fíor; (Léirigh gur rinneadh an malartú).

An deireadh.

Míbhuntáistí an mhodha

Is é an mhíbhuntáiste is mó fad an phróisis. Cé mhéad uair a dhéantar sórtáil algartam mboilgeog?

Ríomhtar an t-am forfheidhmithe ón gcearnóg de líon na n-uimhreacha sa sraith - tá an toradh deiridh comhréireach leis.

Leis an gcás is measa, déanfar an sraith a thrasnú a mhéad uair is go bhfuil eilimintí ann, lúide luach amháin. Tá sé seo toisc nach bhfuil ach aon ghné amháin sa deireadh nach bhfuil aon rud le déanamh i gcomparáid leis, agus is é an pas deireanach tríd an eagra gníomh gan úsáid.

Ina theannta sin, ní hé an modh a dhéantar trí mhalartuithe simplí a shórtáil, mar a thugtar air freisin, éifeachtach ach amháin d'fhionraí beaga. Ní féidir méideanna móra sonraí a phróiseáil ag baint úsáide as: is é an toradh a bheidh ann ná earráidí, nó tuairteála clár.

Buntáistí

Tá an-éasca le tuiscint a fháil ar mboilgeog a shórtáil. I gcuraclaim na n-ollscoileanna teicniúla, nuair a bhíonn sé ag déanamh staidéir ar ordú eilimintí de shraith, téann sé ar dtús. Is é an modh éasca dá an teanga Delphi cláir (L (Delphi), agus an t-C / C ++ (C / C móide móide), ina luachanna thar a bheith simplí ar algartam suíomh san ord ceart agus ag an chur chun feidhme Pascal (Pascal). Tá saghas mboilgeog iontach do thosaitheoirí.

De bharr easnaimh, ní úsáidtear an algartam chun críocha seach-churaclaim.

Prionsabal soiléir maidir le sórtáil

Is é tuairim tosaigh na sraithe 8 22 4 74 44 37 1 7

Céim 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Céim 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Céim 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Céim 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Céim 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Céim 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Céim 7 1 4 7 8 22 37 44 74

Sampla maidir le mboilgeog a shórtáil i Pascal

Sampla:

Const kol_mas = 10;

Var massiv: eagar [1..kol_mas] de slánuimhir;

A, b, k: slánuimhir;

Tosaigh

Scríbhneoireacht ('ionchur', kol_mas, 'eilimintí eagar');

Maidir le: = 1 to kol_mas do readln (massiv [a]);

Le haghaidh: tosú = 1 go kol_mas-1

Le haghaidh b: tosóidh = a + 1 le kol_mas

Má tá massiv [a]> massiv [b] ansin tosú

K: = massiv [a]; Massiv [a]: = massiv [b]; Massiv [b]: = k;

Deireadh;

Deireadh;

Deireadh;

Scríbhneoireacht ('tar éis an tsórt');

Maidir le: = 1 le kol_mas déan scríobh (massiv [a]);

Deireadh.

Sampla maidir le mboilgeog a shórtáil i C (C)

Sampla:

#include

#include

Príomhghníomhach (int argc, char * argv [])

{

Int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

Do (;;) {

F = 0;

I gcás (i = 7; i> 0; i -) {

Má (massiv [i]

Babhtáil (massiv [i], massiv [i-1]);

Ff ++;

}

}

Má bhriseann (ff == 0);

}

Getch (); // mhoill scáileáin

Tuairisceán 0;

}.