Quick sort គឺជាវិធីតម្រៀបដែលបណ្ណាល័យកូដភាគច្រើនប្រើ ព្រោះវាលឿនក្នុងការអនុវត្តជាក់ស្តែង។ វាជ្រើសរើសតម្លៃ pivot មួយ បន្ទាប់មកបែងចែក (partition) array ដើម្បីឱ្យរាល់តម្លៃតូចជាងស្ថិតនៅខាងឆ្វេង pivot ហើយតម្លៃធំជាងនៅខាងស្តាំ។ ពេលនោះ pivot ស្ថិតនៅទីតាំងចុងក្រោយរបស់វា ហើយ quick sort ធ្វើដំណើរការនេះឡើងវិញនៅលើផ្នែកទាំងពីរ។ ឧបករណ៍បង្ហាញនេះបង្ហាញ pivot ពណ៌ស្វាយ សន្ទស្សន៍ព្រំដែន i ជាមួយពណ៌ផ្ទាល់ខ្លួន និងបន្ថយពណ៌ផ្នែកដែលមិនទាន់ partition។
វាប្រើវិធីសាស្ត្រ Lomuto partition ដោយយកធាតុចុងក្រោយជា pivot។ សាកល្បងបញ្ចូលទិន្នន័យដែលបានតម្រៀបរួច ឬបញ្ច្រាស ដើម្បីមើលករណីអាក្រក់បំផុត (worst case)៖ pivot តែងតែជាតម្លៃធំបំផុត ឬតូចបំផុត ការបែងចែកលំអៀង ហើយចំនួនប្រៀបធៀបកើនឡើងដល់ n²/2។
របៀបប្រើឧបករណ៍ បង្ហាញដំណើរការ Quick Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស ឬមានតម្លៃដូចគ្នាច្រើន។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរមួយការប្រៀបធៀប ឬមួយការ swap ម្តង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ របារពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប ពណ៌ក្រហមកំពុង swap ឬសរសេរ ហើយពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយត្រឹមត្រូវ។
- អានសារខាងក្រោមប៊ូតុងបញ្ជា និងបន្ទាត់ pseudocode ដែលបាន highlight ដើម្បីដឹងច្បាស់ពីអ្វីដែល algorithm កំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបចំនួនរាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ បង្ហាញដំណើរការ Quick Sort របស់ ToolOrca
- របារមានចលនាជាមួយប៊ូតុង play, pause, step និង step back
- របាររំកិលល្បឿន និងរបាររំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយ
- ការរាប់ចំនួនប្រៀបធៀប និងចំនួន swap
- ទិន្នន័យចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស និងមានតម្លៃដូចគ្នាច្រើន ឬលេខផ្ទាល់ខ្លួន
- Highlight បន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជាភាសា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរស័ព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល quick sort ដំណើរការ
Partition (Lomuto): យក pivot = a[hi] និង i = lo។ សម្រាប់ j នីមួយៗពី lo ដល់ hi − 1 ប្រសិនបើ a[j] តូចជាង pivot នោះ swap a[i] និង a[j] ហើយបង្កើន i។ នៅចុងបញ្ចប់ swap a[i] ជាមួយ a[hi]៖ pivot ធ្លាក់នៅ index i ដោយមានតម្លៃតូចជាងនៅខាងឆ្វេង និងតម្លៃផ្សេងទៀតនៅខាងស្តាំ។ បន្ទាប់មកតម្រៀប lo..i − 1 និង i + 1..hi តាមវិធីដដែល។ ចន្លោះដែលមានធាតុសូន្យ ឬមួយ គឺត្រូវបានតម្រៀបរួចរាល់ហើយ។
Hoare partition ដែលរំកិល pointer ពីរទល់មុខគ្នា ធ្វើការ swap តិចជាង ហើយត្រូវបានប្រើច្រើនក្នុងកូដជាក់ស្តែង។ កូដ production ក៏ជ្រើសរើស pivot កាន់តែប្រុងប្រយ័ត្នផងដែរ៖ យក median នៃតម្លៃ 3 ឬធាតុចៃដន្យណាមួយ។
Time និង space complexity នៃ quick sort
ប្រសិនបើ pivot នីមួយៗបំបែកចន្លោះរបស់វាប្រហែលពាក់កណ្តាល វានឹងមានប្រហែល log₂ n កម្រិតដោយកម្រិតនីមួយៗដំណើរការ O(n)៖ O(n log n) ដែលជាមធ្យមលើទិន្នន័យចៃដន្យ។ ប្រសិនបើ pivot តែងតែជាតម្លៃតូចបំផុត ឬធំបំផុត ម្ខាងនឹងទទេរាល់ពេល ហើយរយៈពេលដំណើរការក្លាយជា O(n²)។ ការយកធាតុចុងក្រោយជា pivot នឹងជួបករណីនេះលើទិន្នន័យដែលតម្រៀបរួច។ Quick sort តម្រៀបលើទីតាំងផ្ទាល់ (in-place) និងត្រូវការ stack space ជាមធ្យម O(log n) (O(n) ក្នុងករណីអាក្រក់បំផុត លើកលែងតែអ្នក recurse លើផ្នែកតូចជាងមុន)។ វាមិនមែនជា stable sort ទេ។
ពេលណាគួរប្រើ quick sort
Quick sort គឺជាជម្រើសលំនាំដើមសម្រាប់តម្រៀប array ក្នុង memory៖ C++ std::sort ប្រើ introsort (quick sort ដែលប្តូរទៅ heap sort ប្រសិនបើ recursion ជ្រៅពេក និង insertion sort សម្រាប់ទំហំតូច) ហើយ Java តម្រៀប primitive arrays ជាមួយ dual-pivot quick sort។ ជៀសវាង naive version លើទិន្នន័យដែលប្រហែលជាតម្រៀបរួច ហើយប្រើ merge sort នៅពេលអ្នកត្រូវការ stability។
រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងរបាររំកិលល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ quick sort គឺជាអ្វី?
O(n log n) ជាមធ្យម និងក្នុងករណីល្អបំផុត, O(n²) ក្នុងករណីអាក្រក់បំផុតនៅពេល pivot បំបែក array មិនស្មើគ្នាយ៉ាងខ្លាំង។
ហេតុអ្វីបានជា quick sort លឿន បើ worst case របស់វាគឺ O(n²)?
ការជ្រើសរើស pivot ល្អ (ចៃដន្យ ឬ median នៃ 3) ធ្វើឱ្យករណីអាក្រក់បំផុតស្ទើរតែមិនកើតឡើង ហើយ in-place partitioning របស់ quick sort ប្រើប្រាស់ overhead តិច និងដំណើរការជាមួយ CPU cache បានយ៉ាងល្អ។
តើ pivot គឺជាអ្វី?
ជាតម្លៃដែល array ត្រូវបានបែងចែកជុំវិញវា។ បន្ទាប់ពី partition រួច pivot នឹងស្ថិតនៅទីតាំងតម្រៀបចុងក្រោយត្រឹមត្រូវ ដោយតម្លៃតូចជាងនៅខាងឆ្វេង និងតម្លៃធំជាងនៅខាងស្តាំ។
តើ quick sort ជា stable sort ដែរឬទេ?
មិនមែនទេ ព្រោះការ partition ធ្វើការ swap តម្លៃឆ្លងកាត់ចម្ងាយឆ្ងាយ ដែលអាចផ្លាស់ប្តូរលំដាប់នៃតម្លៃស្មើគ្នា។
តើ Lomuto និង Hoare partition ខុសគ្នាយ៉ាងណា?
Lomuto ប្រើ index មួយរត់ពីឆ្វេងទៅស្តាំ និងងាយយល់ជាង។ Hoare ប្រើ index ពីររត់រកគ្នា និងធ្វើការ swap តិចជាងប្រហែល 3 ដងជាមធ្យម។