Quicksort ជាវិធីសាស្រ្តសរសេរកម្មវិធីមួយ

នៅឆ្នាំ 1960 ឃេក Hoar បានបង្កើតវិធីសាស្រ្តមួយសម្រាប់ការតម្រៀបយ៉ាងលឿននៃពបានក្លាយជាល្បីបំផុត។ សព្វថ្ងៃនេះវាត្រូវបានគេប្រើប្រាស់ក្នុងការសរសេរកម្មវិធី, ដូចដែលវាមានលក្ខណៈសម្បត្តិជាច្រើនវិជ្ជមាន: វាអាចត្រូវបានប្រើសម្រាប់ករណីទូទៅវាតម្រូវឱ្យមានការកើនឡើងនៅក្នុងសតិបន្ថែមតូចមួយនេះឆបគ្នាជាមួយប្រភេទផ្សេងគ្នានៃបញ្ជីនិងងាយស្រួលក្នុងការអនុវត្ត។ ប៉ុន្តែមានគុណវិបត្តិដែលមាន Quicksort: ដោយប្រើការងារអនុញ្ញាតឱ្យមានកំហុស, ហើយវាគឺជាមិនស្ថិតស្ថេរបន្តិច។

ទោះជាយ៉ាងណា, វាគឺជាកំណែដែលបានសិក្សាច្រើនបំផុត។ បន្ទាប់ពី Hoare បង់ប្រាក់លើកដំបូង, មនុស្សជាច្រើនបានធ្វើការសិក្សាក្រាស់របស់ខ្លួន។ មូលដ្ឋានធំត្រូវបានបង្កើតឡើងនៅលើទ្រឹស្តីនៃការស្វែងរកសំណួរវេលាដែលបានចំណាយលើការងារដែលត្រូវបានគាំទ្រដោយភស្តុតាងជាក់ស្ដែង។ មានសំណើពិតប្រាកដដើម្បីកែលម្អក្បួនដោះស្រាយជាមូលដ្ឋាននិងបង្កើនល្បឿនបាន។

Quicksort ជារឿងធម្មតាណាស់, វាអាចត្រូវបានរកឃើញនៅគ្រប់ទីកន្លែង។ នៅលើមូលដ្ឋានរបស់ខ្លួនវិធីសាស្រ្តនេះត្រូវបានអនុវត្ត TList.Sort មានវត្តមាននៅក្នុងកំណែទាំងអស់ (លើកលែងតែ 1) Delphi, មុខងារបណ្ណាល័យនៃពេលវេលាដែលវាបានយកដើម្បីបញ្ចប់, qsort ក្នុង C ++ ។

គោលការណ៍ជាមូលដ្ឋាននៃការប្រតិបត្ដិការនេះអាចត្រូវបានបង្កើតជា "បែងចែកត្រួតត្រា" ។ វាបានកើតឡើងបំបែកបញ្ជីជាពីរក្រុមហើយត្រូវបានតម្រៀបសម្រាប់ជាផ្នែកមួយគ្នាបានដោយខ្លួនវាផ្ទាល់។ វាធ្វើតាមដែលគួរតែត្រូវបានយកចិត្តទុកដាក់កាន់តែច្រើនដើម្បីដំណើរការញែកចេញពីគ្នាបានបង់ដែលពេលនោះមានដូចខាងក្រោមនេះបានកើតឡើង: ត្រូវបានកំណត់ដោយធាតុមូលដ្ឋាននិងបានរៀបចំទាក់ទងបញ្ជីទាំងមូលរបស់គាត់។ បានសាងសង់ឡើងទៅខាងឆ្វេងនៃក្រុមបេក្ខជនតម្លៃនៃការដែលមានតិចជាងវិធានការផ្ទេរផ្សេងទៀតទាំងអស់។ វាប្រែថាធាតុសំខាន់នៅក្នុងបញ្ជីដែលបានតម្រៀបគឺស្ថិតនៅក្នុងកន្លែងស្របច្បាប់របស់ខ្លួន។ ដំណាក់កាលបន្ទាប់ - បញ្ហាប្រឈមមួយមុខងារតម្រៀបហៅខ្លួនឯងសម្រាប់ភាគីទាំងពីរនៃធាតុដែលទាក់ទងទៅនឹងមូលដ្ឋាន។ វាបានបញ្ចប់ដំណើរការនេះធ្វើការតែប្រសិនបើបញ្ជីនេះមានធាតុតែមួយប៉ុណ្ណោះ, ដែលត្រូវបានតម្រៀប។ ដូច្នេះក្នុងគោលបំណងដើម្បីធ្វើជាម្ចាស់នៃមុខងារការសរសេរកម្មវិធីមួយជាប្រភេទរហ័ស, វាគឺជាការចាំបាច់ដើម្បីឱ្យដឹងថាការងាររបស់ក្បួនដោះស្រាយថ្នាក់ទាប: មួយ) ជម្រើសរបស់សមាជិកមូលដ្ឋាននេះ; ខ) បញ្ជីនៃសំនុំឆ្លាស់មានប្រសិទ្ធិភាពបំផុតមួយដើម្បីផលិតដោយតម្លៃចំនួនពីរតូចនិងធំ។

ស្គាល់តាមគោលការណ៍ជាលើកដំបូង។ នៅពេលជ្រើសរើសយកសមាជិកមូលដ្ឋាន, គួរតែត្រូវបានជ្រើសពីបញ្ជីនៃមធ្យម។ បន្ទាប់មកនៅលើសម្រាកត្រូវបានបែងចែកជាខ្សែការពារស្មើពីរ។ គ្រាន់តែជាការគណនា តម្លៃមធ្យម នៅក្នុងបញ្ជីនេះគឺមានការលំបាកខ្លាំងណាស់ដូច្នេះសូម្បីតែតម្រៀបលឿនបំផុត bypasses ម្ខាងគណនានេះ។ ប៉ុន្តែជម្រើសនៃធាតុជាមូលដ្ឋានដោយមានតម្លៃអតិបរមាឬអប្បបរមានេះ - មិនមែនជម្រើសល្អបំផុតផងដែរ។ ក្នុងករណីការប្តេជ្ញាចិត្តបែបនេះពីមួយបង្កើតបញ្ជីទទេនឹងត្រូវបានធានានិងពេញលើកទីពីរ។ ហេតុនេះការសន្និដ្ឋានថាជាសមាជិកមូលដ្ឋានដែលគួរតែត្រូវបានជ្រើសរើសមួយដែលនៅជិតទៅនឹងមធ្យម, ប៉ុន្តែនៅលើអតិបរមានិងអប្បបរមា។

នៅពេលជម្រើសត្រូវបានកំណត់, អ្នកអាចបន្តទៅក្បួនដោះស្រាយការ decomposition នេះ។ នេះគេហៅថាផ្នែកខាងក្នុងប្រភេទរហ័សរង្វិលជុំ។ អ្វីគ្រប់យ៉ាងត្រូវបានសាងសង់ឡើងនៅលើការចូលដំណើរការរហ័សពីរលិបិក្រម: ជាលើកដំបូងទៅលើធាតុពីឆ្វេងទៅស្តាំទីពីរនៅលើផ្ទុយមកវិញ, ពីស្តាំទៅឆ្វេង។ ចាប់ផ្តើមប្រតិបត្តិការប្រតិបត្ដិខាងស្ដាំ: លិបិក្រមគឺនៅក្នុងបញ្ជីនិងការប្រៀបធៀបតម្លៃទាំងអស់នេះទៅមេ។ វដ្តនេះត្រូវបានបញ្ចប់នៅពេលដែលធាតុគឺតិចជាងឬស្មើទៅនឹងបន្ទាត់គោល។ នោះគឺជា, គឺមានប្រៀបធៀបជាមួយនិងការថយចុះតម្លៃនៃលិបិក្រម។ នៅលើដៃខាងឆ្វេងពេលដែលការងារនេះត្រូវបានបញ្ចប់ធំជាងឬតម្លៃស្មើគ្នា។ នៅទីនេះតម្លៃប្រៀបធៀបការកើនឡើង។

នៅក្នុងដំណាក់កាលនៃក្បួនដោះស្រាយចែកភាគថាសដែលមានសមាសភាព quicksort នេះអាចកើតឡើងស្ថានភាពពីរ។ ទីមួយគឺថាសន្ទស្សន៍នៅខាងឆ្វេងគឺតិចជាងខាងស្ដាំ។ នេះបង្ហាញកំហុសបន្ទាប់មកមានធាតុនៅលើដែលវាត្រូវបានចែងនៅក្នុងបញ្ជីគឺមាននៅក្នុងលំដាប់មិនត្រឹមត្រូវទេ។ ទិន្នផល - ផ្លាស់ប្តូរទីកន្លែងរបស់ពួកគេ។ ស្ថានភាពទីពីរគឺនៅពេលដែលទាំងពីរនៃជួរឈរនេះគឺស្មើឬឆ្លងកាត់។ នេះបង្ហាញពីការបំបែកទទួលបានជោគជ័យនៃបញ្ជីនេះគឺថាការងារនេះគឺឥឡូវនេះបានបញ្ចប់។