Quicksort mar phrògraman dòigh

Ann an 1960, K. A. Hoar a leasachadh airson an dòigh luath Seòrsachadh fiosrachaidh, dh'fhàs as ainmeile. Diugh tha e air a chleachdadh ann am prògraman, mar a tha tòrr de na feartan matha: a ghabhas a chleachdadh airson cùisean coitcheann, tha e ag iarraidh àrdachadh beag anns a bharrachd cuimhne, co-chòrdail le diofar sheòrsaichean de liostaichean agus furasta a chur an gnìomh. Ach tha drawbacks, a tha Quicksort: a 'cleachdadh obair ceadaichte tòrr mhearachdan, agus tha e caran neo-sheasmhach.

Ach, tha e a 'chuid as motha de sgrùdadh dreach. Às dèidh a 'chiad phàigheadh Hoare, mòran a dhèanamh tiugh sgrùdadh. mòr ionad a stèidheachadh air teòiridheach ceistean a lorg an ùine a chur seachad air an obair, a tha stèidhichte air fianais deuchainneach. Bha fìor molaidhean gus bun-algairim agus barrachd astar.

Quicksort tha e glè chumanta, lorgar e anns gach àite. Air a 'bhunait a chur an gnìomh an dòigh TList.Sort, an làthair ann a h-uile tionndaidhean (ach a-mhàin 1) Delphi, an leabharlainn gnìomh ùine a thug e airson a lìonadh, qsort ann an C ++.

Tha na phrionnsapal bunaiteach obrachaidh urrainn a chur ri chèile mar "divide agus Conquer". Tha e a 'nochdadh a' briseadh an liosta ann an dà buidhnean agus a 'cur ann an ordugh airson gach pàirt leis fhèin. Tha e a 'leantainn gu bheil barrachd aire a bu chòir a phàigheadh dhan phròiseas dealachaidh, nuair a tha na leanas a' tachairt: a shuidheachadh le bonn eileamaid agus tha an ìre mhath air fad aige troimhe liosta. Chaidh a thogail air an taobh chlì de bhuidheann de thagraichean, an luach a tha nas lugha na na h-uile gluasad eile riaghailtean. Tha e a 'tionndadh a-mach gur e am prìomh eileamaid ann an cur ann an ordugh liosta ann a dligheach àite. Tha an ath ìre - dùbhlan recursive Seòrsachadh gnìomhan airson gach taobh de na h-eileamaidean buntainneach a 'bhonn. Tha e a 'crìochnachadh air a' phròiseas ag obair a-mhàin ma tha an liosta mu ach aon eileamaid, a tha gu bhith air an rèiteach. Mar sin, gus daingneachadh prògramaidh dhreuchd mar grad-seòrsa, tha e riatanach gus fios obair aig ìre ìosal aontaran: a) an roghainn de stèidh ball; b) liosta de na permutation èifeachdach a thoirt gu buil dà sheata le nas lugha agus nas motha luachan.

Le eòlas a 'chiad prionnsabalan. Nuair a bhios a 'taghadh an t-ionad bhall, bu chòir a bhith air a thaghadh bho liosta de na a' chuibheasachd. An uair sin air an fois a roinn ann an dà leth co-ionann. Dìreach obrachadh a-mach na cuibheasachd luach anns an liosta e glè dhuilich, mar sin, fiù 's na bu luaithe Seòrsachadh seachnadh seo calculus taobh. Ach tha an roghainn de na eileamaid bhunaiteach leis a 'char as motha no as lugha luach - cuideachd nach eil an roghainn as fheàrr. Ann an cùis leithid co-dhùnadh a 'cruthachadh aon falamh liostaichean thèid an urras, agus an dara h-iomlan. Uime sin tha na cho-dhùnadh gu bheil mar an t-ionad bu chòir ball a chaidh a thaghadh aon a tha nas fhaisge air an cuibheasach, ach air a 'char as motha agus as lugha.

Nuair a roghainn air a shuidheachadh, faodaidh tu a dhol air adhart gus an lobhadh algairim. Tha a 'cho-ghairm a-staigh lùban luath seòrsa. Everything air a thogail air dà Rapid Cothrom clàran-amais: a 'chiad dol a-null na h-eileamaidean bho chlì gu deas, an dara, air an aghaidh, bho dheas gu clì. Tòiseachadh obrachadh bàs deas: an clàr-amais a tha air an liosta agus coimeas a dhèanamh eadar na h-uile luachan a 'phrìomh. Tha an cearcall deiseil nuair a chaidh an eileamaid a tha nas lugha na no co-ionann ris na bun-loidhne. 'S e sin, tha coimeas agus lùghdachadh luach an clàr-amais. Air an làimh chlì nuair a bhios an obair a tha e deiseil nas motha na no co-ionnan luach. An seo, an coimeas an luach àrdachadh.

Aig an ìre seo de eatorra algairim a tha a 'gabhail a-steach quicksort, dà suidheachaidhean a dh'fhaodadh tighinn am bàrr. Tha a 'chiad a' chlàr-innse air an taobh chlì tha nas lugha na làimh dheis. Tha seo a 'comharrachadh mearachd, agus an uair sin tha na h-eileamaidean air a bheil e a chaidh aithris ann an liosta ann an òrdugh ceàrr. Species - atharrachadh an àiteachan. Tha an dàrna suidheachadh nuair a tha an dà chuid an colbh tha co-ionann ri no a 'dol tarsainn. Seo a 'sealltainn soirbheachail dealachadh an liosta,' se sin, an obair a tha a-nis deiseil.