កម្មវិធីបង្ហាញ Merge Sort

Merge sort គឺជាក្បួនតម្រៀបបែប divide and conquer ដ៏ល្បីល្បាញ។ វាពុះ array ជាពីរផ្នែក តម្រៀបផ្នែកនីមួយៗតាមបែប recursive រួចបញ្ចូលផ្នែកទាំងពីរដែលបានតម្រៀបរួចឱ្យទៅជាមួយវិញ។ ឧបករណ៍ visualizer នេះបន្លិចផ្នែកនៃ array ដែលកំពុងដំណើរការ បង្ហាញ temp array ដែលប្រើពេលបញ្ចូលគ្នា និងបង្កើតចលនានៃការប្រៀបធៀបព្រមទាំងការសរសេរត្រឡប់ចូលទៅក្នុង array វិញ។

ខុសពីក្បួនតម្រៀបកម្រិត O(n²) សាមញ្ញ merge sort តែងតែចំណាយពេល O(n log n) ជានិច្ច មិនថាទិន្នន័យបញ្ចូលបែបណានោះទេ៖ ចៃដន្យ, រៀបរួច ឬបញ្ច្រាស។ ប៉ុន្តែវាត្រូវចំណាយអង្គចងចាំបន្ថែមសម្រាប់ temp array។ សង្កេតមើលកុងទ័រសរសេរ៖ កម្រិតនីមួយៗនៃ recursion សរសេរគ្រប់ n តម្លៃម្តង ហើយមានកម្រិតចំនួនប្រហែល log₂ n។

របៀបប្រើឧបករណ៍ កម្មវិធីបង្ហាញ Merge Sort

1. ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស ឬមានតម្លៃទោលតិចតួច។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
2. ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរទៅមុខម្តងមួយការប្រៀបធៀប ឬមួយការប្តូរទីតាំង។ Back ថយក្រោយមួយជំហាន។
3. តាមដានពណ៌៖ បន្ទះពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប, បន្ទះពណ៌ក្រហមកំពុងត្រូវបានប្តូរទីតាំង ឬសរសេរចូល, បន្ទះពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយរបស់វា។
4. អានសារនៅខាងក្រោមកុងត្រូល និងបន្ទាត់ pseudocode ដែលបានបន្លិច ដើម្បីដឹងច្បាស់ពីអ្វីដែលក្បួនកំពុងធ្វើ។
5. ផ្លាស់ប្តូរ ល្បឿន, ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបកុងទ័ររាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។

ហេតុអ្វីប្រើ កម្មវិធីបង្ហាញ Merge Sort របស់ ToolOrca

• បន្ទះមានចលនាជាមួយមុខងារ play, pause, step ទៅមុខ និង step ថយក្រោយ
• គ្រាប់រំកិលល្បឿន និងគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយភ្លាមៗ
• Temp array បង្ហាញក្នុងពេលបញ្ចូលគ្នា (merge) គ្រប់ជំហាន
• កុងទ័ររាប់ចំនួនប្រៀបធៀប និងចំនួនប្តូរទីតាំង
• ទិន្នន័យបញ្ចូលបែបចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស និងមានតម្លៃទោលតិចតួច ឬលេខផ្ទាល់ខ្លួនរបស់អ្នក
• បន្លិចបន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
• កូដជា C++, Java, Python និង JavaScript
• ដំណើរការលើទូរសព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន

របៀបដែល merge sort ដំណើរការ

Divide: ពុះចន្លោះ lo..hi ត្រង់ mid = (lo + hi) / 2។ Conquer: តម្រៀប lo..mid និង mid + 1..hi តាមបែប recursive; ចន្លោះដែលមានធាតុមួយគឺត្រូវបានតម្រៀបរួចរាល់ហើយ។ Combine: បញ្ចូលផ្នែកទាំងពីរដែលបានតម្រៀបរួចចូលគ្នា។ ចម្លងពួកវាទៅ temp array រួចប្រៀបធៀបតម្លៃខាងមុខនៃផ្នែកទាំងពីរម្តងហើយម្តងទៀត ហើយសរសេរតម្លៃតូចជាងត្រឡប់ទៅ array វិញ។ នៅពេលផ្នែកម្ខាងអស់ធាតុ សូមចម្លងធាតុដែលនៅសល់នៃផ្នែកម្ខាងទៀត។

ការយកតម្លៃខាងឆ្វេងនៅពេលតម្លៃទាំងពីរស្មើគ្នា ធ្វើឱ្យ merge sort មានលក្ខណៈ stable ដែលជាមូលហេតុធ្វើឱ្យវាត្រូវបានគេប្រើដើម្បីតម្រៀប records តាម keys ច្រើន។

Time និង space complexity នៃ merge sort

កម្រិតនៃការបំបែកនីមួយៗធ្វើការងារកម្រិត O(n) ដើម្បី merge ហើយការបំបែកជាពីរលើ n ម្តងហើយម្តងទៀតបង្កើតបាន log₂ n កម្រិត ដូច្នេះ merge sort ដំណើរការក្នុងកម្រិត O(n log n) ទាំងករណីល្អបំផុត មធ្យម និងអាក្រក់បំផុត។ ការតម្រៀបមួយលានតម្លៃចំណាយពេលប្រហែល 20 លានជំហាន ជំនួសឱ្យ 500 ពាន់លានជំហានសម្រាប់ក្បួនតម្រៀបប្រភេទ O(n²)。 កំណែ array ត្រូវការអង្គចងចាំបន្ថែម O(n) សម្រាប់ temp array ចំណែក linked lists អាចធ្វើ merge sort ដោយប្រើអង្គចងចាំបន្ថែមត្រឹមតែ O(1) ប៉ុណ្ណោះ។

ពេលណាគួរប្រើ merge sort

សូមប្រើ merge sort នៅពេលអ្នកត្រូវការរយៈពេលដំណើរការ O(n log n) ជាក់លាក់មួយ ការតម្រៀបដែលមានស្ថិរភាព (stable sort) ឬដើម្បីតម្រៀប linked list ឬទិន្នន័យដែលធំពេកមិនអាចផ្ទុកក្នុង memory បាន (external sorting ធ្វើការ merge ផ្នែកដែលបានតម្រៀបរួចពី disk)។ Java ប្រើវ៉ារ្យ៉ង់របស់ merge sort (Timsort) សម្រាប់ objects ហើយ sorted() របស់ Python ក៏ជា Timsort ដែរ។ នៅពេលអង្គចងចាំមានកម្រិត ហើយមិនត្រូវការ stability ទេ quick sort ឬ heap sort អាចជាជម្រើសល្អជាង។

គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយឧបករណ៍បញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅកាន់ជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។