Quicksort mar mhodh cláir

I 1960, d'fhorbair K. A. Hoar modh chun an sórtáil tapa eolais, tháinig an ceann is cáiliúla. Sa lá atá inniu tá sé in úsáid go forleathan i gcláir, mar tá sé a lán de na hairíonna dearfach: Is féidir é a úsáid le haghaidh cásanna ginearálta, éilíonn sé méadú beag ar an chuimhne breise, ag luí le cineálacha éagsúla de liostaí agus éasca a chur i bhfeidhm. Ach tá míbhuntáistí, a bhfuil Quicksort: ag baint úsáide as an obair a cheadaítear a lán de na botúin, agus tá sé beagán éagobhsaí.

Mar sin féin, is é an leagan is staidéar. Tar éis an chéad Hoare íocaíocht, an bhfuil go leor a staidéar dlúth. Bunaíodh bonn mór ar cheisteanna teoiriciúil a aimsiú ar an am a chaitear ar an bpost, a bhíonn bunaithe ar fhianaise eimpíreach. Bhí moltaí fíor chun feabhas a chur ar an algartam bunúsach agus luas méadaithe.

Tá Quicksort an-choitianta, is féidir é a fháil i ngach áit. Ar a bhonn an modh i bhfeidhm TList.Sort, i láthair i ngach leagan (ach amháin 1) Delphi, an fheidhm leabharlainne ama a thóg sé a chur i gcrích, qsort i C ++.

Is féidir leis an prionsabal bhunúsacha fheidhmiú a chur le chéile mar "scoilt agus conquer". Tarlaíonn sé briseadh an liosta ina dhá ghrúpa agus atá curtha in eagar do gach cuid a chuireann sé féin. Leanann sé gur chóir níos mó airde a íoc leis an phróiseas scartha, ina dtarlóidh an méid seo a leanas: chinneadh ag eilimint bonn agus tá ord nua orthu réasúnta a liosta iomlán. Tógtha ar an taobh clé de ghrúpa iarrthóirí, ar a bhfuil an luach níos lú ná na rialacha aistrithe eile. Casadh sé amach go bhfuil an ghné is mó ar an liosta curtha in eagar in a áit rightful. An chéad chéim eile - dúshlán feidhmeanna sórtáil recursive don dá thaobh de na heilimintí i gcoibhneas leis an mbonn. Críochnaíonn sé oibríonn an próiseas ach amháin i gcás ina mbeidh ach eilimint amháin ar an liosta, is é sin le bheith curtha in eagar. Dá bhrí sin, d'fhonn a mháistir feidhm cláir mar saghas tapa, tá sé riachtanach go mbeadh a fhios d'obair na halgartaim níos ísle-leibhéal: a) an rogha an chomhalta bonn; b) liosta de na permutation is éifeachtaí a thabhairt ar aird dhá thacar luachanna níos lú agus níos mó.

Eolas maidir leis bhunphrionsabail. Nuair a roghnú an comhalta bonn, ba cheart a roghnú go hidéalach ón liosta de meán. Ansin, ar an sos roinnte ina dhá leath chothroma. Just a ríomh meánluach atá sa liosta an-deacair, mar sin seachbhóithre fiú an sórtáil tapúla an taobh calcalas. Ach an rogha an gné bhunúsach leis an t-uasluach nó íosta - chomh maith nach bhfuil an rogha is fearr. I gcás Cruthaíonn an cinneadh sin de amháin liostaí folamh a ráthú, agus an dara iomlán. Dá réir sin an tátal gur chóir an chomhalta bonn a roghnú amháin go bhfuil níos gaire don mheán, ach ar an t-uasmhéid agus íosmhéid.

Chomh luath agus go bhfuil rogha a chinneadh, is féidir leat dul ar aghaidh leis an algartam lobhadh. Seo ar a dtugtar lúba istigh saghas tapaidh. Tá gach rud tógtha ar dhá innéacsanna Mear-Rochtana: an chéad dul thar na heilimintí ó chlé go deas, an dara, ar a mhalairt, ó ceart ar chlé. Tosaíonn oibríocht fhorghníomhú ceart: tá an t-innéacs ar an liosta agus comparáid a dhéanamh idir na luachanna go dtí an príomh. Is é an timthriall iomlán nuair a bhíonn an eilimint níos lú ná nó cothrom leis an mbonnlíne. Is é sin, tá súil le comparáid agus laghduithe ar luach an innéacs. Ar an lámh chlé nuair a bheidh an obair críochnaithe níos mó ná nó comhionann a luach. Anseo, na méaduithe luach comparáide.

Ag an gcéim seo den algartam partitioning a chuimsíonn quicksort, d'fhéadfadh dhá staideanna teacht chun cinn. Is é an chéad cheann ná go bhfuil an t-innéacs ar an taobh clé níos lú ná dheis. Léiríonn sé seo earráid, ansin tá eilimintí ar a dúradh sa liosta atá san ord mícheart. Aschur - athrú a n-áiteanna. Is é an dara scéal nuair is dá cheann de na colún cothrom le nó thrasnaigh. Léiríonn sé seo scaradh rathúil an liosta, is é sin, tá an obair críochnaithe anois.