Quicksort fel dull rhaglennu

Ym 1960, datblygodd K. A. Hoar dull ar gyfer didoli cyflym o wybodaeth, oedd y mwyaf enwog. Heddiw mae'n cael ei ddefnyddio'n eang mewn rhaglennu, gan ei fod ganddo lawer o eiddo cadarnhaol: gellir ei ddefnyddio ar gyfer achosion cyffredinol, mae angen cynnydd bychan yn y cof ychwanegol, yn gydnaws â gwahanol fathau o restrau ac yn hawdd i'w gweithredu. Ond mae yna anfanteision, sydd wedi Quicksort: ddefnyddio gwaith yn caniatáu llawer o gamgymeriadau, ac mae'n braidd yn ansefydlog.

Fodd bynnag, ei fod yn y fersiwn mwyaf a astudiwyd. Ar ôl y taliad cyntaf Hoare, mae llawer yn gwneud ei astudiaeth trwchus. sylfaen fawr ei sefydlu ar gwestiynau damcaniaethol o ddod o hyd yr amser a dreuliwyd ar y swydd, a ategir gan dystiolaeth empirig. Roedd cynigion gwirioneddol i wella algorithm sylfaenol a mwy o gyflymder.

Quicksort yn gyffredin iawn, gellir dod o hyd ym mhob man. Ar ei sail y dull yn cael ei weithredu TList.Sort, yn bresennol mewn pob fersiwn (ac eithrio 1) Delphi, swyddogaeth llyfrgell amser a gymerwyd i gwblhau, qsort yn C ++.

Gall yr egwyddor sylfaenol o weithredu yn cael ei ffurfio fel "rhaniad a goncro". Mae'n digwydd torri'r rhestr yn ddau grŵp ac yn cael eu datrys ar gyfer pob rhan ei ben ei hun. Mae'n dilyn y dylai mwy o sylw yn cael ei dalu i'r broses wahanu, yn ystod y mae'r canlynol yn digwydd: yn cael ei bennu gan elfen sylfaenol ac yn gymharol wedi aildrefnu ei rhestr gyfan. Adeiladwyd ar y chwith i grŵp o ymgeiswyr, mae'r gwerth sy'n llai na holl reolau trosglwyddo eraill. Mae'n ymddangos bod y brif elfen yn y rhestr didoli yn ei lle priodol. Y cam nesaf - yn her swyddogaethau didoli recursive gyfer y ddwy ochr o'r elfennau cymharol at y sylfaen. Mae'n dod i ben mae'r broses yn gweithio dim ond os yw'r rhestr yn cynnwys dim ond un elfen, sydd i'w datrys. Felly, er mwyn meistroli swyddogaeth rhaglennu fel math cyflym, mae angen i ni wybod y gwaith o algorithmau lefel is-: a) y dewis o aelod sylfaen; b) rhestr o'r permutation mwyaf effeithiol i gynhyrchu dwy set gyda gwerthoedd llai a mwy.

Ymgyfarwyddo ag egwyddorion sylfaenol. Wrth ddewis yr aelod sylfaen, dylid yn ddelfrydol yn cael eu dewis o'r rhestr o gyfartaledd. Yna, ar y toriad yn cael ei rannu yn ddau hanner cyfartal. Dim ond yn cyfrifo gwerth cyfartalog yn y rhestr yn anodd iawn, felly hyd yn oed y didoli cyflymaf ffyrdd osgoi sgîl-calcwlws hwn. Ond mae'r dewis yr elfen sylfaenol â'r gwerth uchaf neu isaf - hefyd nad oedd y dewis gorau. Mewn achos benderfyniad o'r fath o un yn creu bydd rhestri gwag yn cael eu gwarantu, ac mae'r ail yn llawn. Felly y casgliad y dylai'r fel yr aelod sylfaen yn cael ei ddewis yn un sy'n agosach at y cyfartaledd, ond ar yr uchafswm ac isafswm.

Unwaith y bydd dewis yn cael ei bennu, gallwch symud ymlaen i'r algorithm dadelfennu. Mae hyn yn hyn a elwir yn dolenni mewnol didoli gyflym. Mae popeth wedi ei adeiladu ar ddau mynegeion Mynediad Cyflym: yn gyntaf yn mynd dros yr elfennau o'r chwith i'r dde, yr ail, ar y groes, o'r dde i'r chwith. Dechrau gweithrediad gweithredu dde: y mynegai ar y rhestr a chymharu holl werthoedd i'r prif. Mae'r cylch yn gyflawn pan fydd yr elfen yn llai na neu'n hafal i llinell sylfaen. Hynny yw, mae yna cymharu a gostwng gwerth y mynegai. Ar y llaw chwith pan fydd y gwaith wedi'i orffen fwy na neu'n werth cyfartal. Yma, mae'r gwerth cymharu yn cynyddu.

Ar y cam hwn o algorithm ymrannu sy'n cynnwys quicksort, gall ddwy sefyllfa godi. Y cyntaf yw bod y mynegai ar y chwith yn llai na gywir. Mae hyn yn dangos gwall, yna mae yna elfennau y cafodd ei nodi yn y rhestr yn y drefn anghywir. Allbwn - newid eu lleoedd. Yr ail sefyllfa yw pan yw'r ddau o'r golofn yn hafal i neu'n croesi. Mae hyn yn dangos gwahanu llwyddiannus y rhestr, hynny yw, mae'r gwaith bellach wedi'i gwblhau.