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

Insertion sort បង្កើត array ដែលបានតម្រៀបរួចម្តងមួយតម្លៃ ដូចរបៀបដែលមនុស្សភាគច្រើនរៀបសន្លឹកបៀមួយក្តាប់ដូច្នោះដែរ។ វាទាញយកតម្លៃបន្ទាប់ជា key រួចរំកិលរាល់តម្លៃដែលធំជាងនៅក្នុងផ្នែកដែលបានតម្រៀបរួចទៅស្តាំមួយកន្លែង រហូតទាល់តែមានកន្លែងទំនេរសម្រាប់ key នោះ។ ឧបករណ៍ visualizer នេះបង្ហាញ key ជាពណ៌ស្វាយរុញទៅឆ្វេងរំលងតម្លៃធំៗ ដោយមានផ្នែកដែលបានតម្រៀបរួចជាពណ៌បៃតង។

សាកល្បងទិន្នន័យបញ្ចូលដែលស្ទើរតែរៀបរយ៖ key នីមួយៗរំកិលត្រឹមតែមួយឬពីរជំហានប៉ុណ្ណោះ ដូច្នេះការតម្រៀបទាំងមូលចំណាយពេលស្ទើរតែលីនេអ៊ែរ (linear time)។ នេះហើយជាមូលហេតុដែល insertion sort យកឈ្នះ quick sort និង merge sort លើ array តូចៗ ឬស្ទើរតែរៀបរយរួច ហើយត្រូវបានគេប្រើប្រាស់នៅក្នុងក្បួនតម្រៀបកូនកាត់ ដូចជា Timsort និង introsort។

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

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

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

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

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

សម្រាប់ i នីមួយៗពី 1 ទៅ n − 1 រក្សាទុក key = a[i] និងកំណត់ j = i − 1។ ខណៈពេលដែល j ≥ 0 និង a[j] > key សូមចម្លង a[j] ទៅ a[j + 1] ហើយបន្ថយតម្លៃ j។ នៅពេល loop បញ្ឈប់ a[j + 1] គឺជាកន្លែងរបស់ key៖ សរសេរវាចូលទីនោះ។ ទីតាំងពី 0 ទៅ i ឥឡូវត្រូវបានតម្រៀបរួចរាល់។ នៅក្នុងចលនាបង្ហាញ ការរំកិលត្រូវបានគូរឡើងដោយបន្ទះ key ផ្លាស់ប្តូរទីតាំងជាមួយបន្ទះដែលធំជាងនីមួយៗ ដែលផ្តល់លទ្ធផលដូចគ្នា។

Time និង space complexity នៃ insertion sort

ចំនួននៃការរំកិលគឺស្មើនឹងចំនួន inversions (គូធាតុដែលខុសលំដាប់)។ Array បញ្ច្រាសមាន n(n − 1)/2 inversions ដូច្នេះករណីអាក្រក់បំផុត និងករណីមធ្យមគឺ O(n²)។ Array ដែលរៀបរយស្រេចគឺគ្មាន inversions ទេ៖ មួយការប្រៀបធៀបក្នុងមួយតម្លៃ គឺ O(n)។ និយាយឱ្យទូលំទូលាយ វាដំណើរការក្នុងរយៈពេល O(n + d) ដែល d ជាចំនួន inversions។ វាដំណើរការតម្រៀបលើទីតាំងផ្ទាល់ដោយប្រើអង្គចងចាំ O(1), មានលក្ខណៈ stable និងជាប្រភេទ online៖ វាអាចតម្រៀបតម្លៃបានភ្លាមៗនៅពេលទិន្នន័យចូលមកដល់។

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

Insertion sort គឺជាក្បួនតម្រៀបកម្រិតសាមញ្ញដ៏ល្អបំផុត៖ ប្រើវាសម្រាប់ array តូចៗ (រហូតដល់ប្រហែល 16 ទៅ 32 តម្លៃ), សម្រាប់ទិន្នន័យដែលស្ទើរតែរៀបរយរួចស្រេច និងសម្រាប់បន្ថែមតម្លៃថ្មីមួយចំនួនចូលទៅក្នុងបញ្ជីដែលបានតម្រៀបរួច។ Timsort របស់ Python និង Java ព្រមទាំង introsort របស់ C++ ផ្លាស់ប្តូរមកប្រើ insertion sort សម្រាប់ផ្នែកតូចៗ ពីព្រោះ overhead ដ៏ទាបរបស់វាដំណើរការល្អជាងក្បួនដោះស្រាយ O(n log n) នៅក្នុងទំហំទាំងនោះ។

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