Radix sort តម្រៀបលេខតាមខ្ទង់ម្តងមួយៗដោយមិនបាច់ប្រៀបធៀបឡើយ។ ប្រភេទ least significant digit (LSD) ដែលបង្ហាញនៅទីនេះ ដំបូងតម្រៀបគ្រប់តម្លៃតាមខ្ទង់រាយ បន្ទាប់មកតាមខ្ទង់ដប់ និងតាមខ្ទង់រយ។ ជុំនីមួយៗគឺជា stable counting sort ដែលមាន 10 buckets ដូច្នេះតម្លៃដែលមានខ្ទង់បច្ចុប្បន្នស្មើគ្នា នឹងរក្សាលំដាប់ពីជុំមុនដដែល។ បន្ទាប់ពីខ្ទង់ចុងក្រោយ array ទាំងមូលនឹងត្រូវបានតម្រៀបត្រឹមត្រូវ។
ឧបករណ៍បង្ហាញនេះបង្ហាញចំនួនរាប់ខ្ទង់ទាំង 10 ផលបូកសរុបបន្ត និង output array សម្រាប់ជុំនីមួយៗ ហើយសារបញ្ជាក់ពីខ្ទង់ដែលកំពុងប្រើ។ សង្កេតមើលរបៀបដែលរបារមើលទៅច្របូកច្របល់បន្ទាប់ពីជុំដំបូង ប៉ុន្តែត្រូវបានតម្រៀបយ៉ាងស្អាតបន្ទាប់ពីជុំខ្ទង់រយ។
របៀបប្រើឧបករណ៍ បង្ហាញដំណើរការ Radix Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស ឬមានតម្លៃដូចគ្នាច្រើន។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរមួយការប្រៀបធៀប ឬមួយការ swap ម្តង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ របារពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប ពណ៌ក្រហមកំពុង swap ឬសរសេរ ហើយពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយត្រឹមត្រូវ។
- អានសារខាងក្រោមប៊ូតុងបញ្ជា និងបន្ទាត់ pseudocode ដែលបាន highlight ដើម្បីដឹងច្បាស់ពីអ្វីដែល algorithm កំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបចំនួនរាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ បង្ហាញដំណើរការ Radix Sort របស់ ToolOrca
- របារមានចលនាជាមួយប៊ូតុង play, pause, step និង step back
- របាររំកិលល្បឿន និងរបាររំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយ
- ចំនួនរាប់ខ្ទង់ និង output array សម្រាប់គ្រប់ជុំ
- ទិន្នន័យចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស និងមានតម្លៃដូចគ្នាច្រើន ឬលេខផ្ទាល់ខ្លួន
- Highlight បន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជាភាសា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរស័ព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល LSD radix sort ដំណើរការ
ស្វែងរកតម្លៃអតិបរមាដើម្បីដឹងពីចំនួនខ្ទង់ d ដែលត្រូវដំណើរការ។ សម្រាប់ exp = 1, 10, 100 និងបន្តបន្ទាប់៖ យកខ្ទង់របស់តម្លៃនីមួយៗ (x / exp) mod 10 រាប់ចំនួនធាតុដែលមានខ្ទង់នីមួយៗ បំប្លែងចំនួនរាប់ទៅជាផលបូកបន្ត និងដាក់តម្លៃចូលក្នុង output array ពីស្តាំទៅឆ្វេង។ ចម្លង output ត្រឡប់មកវិញ រួចបន្តទៅខ្ទង់បន្ទាប់។
ចំណុចពិសេសគឺ stability។ នៅពេលតម្រៀបតាមខ្ទង់ដប់ លេខ 31 និង 37 ស្មើគ្នា ប៉ុន្តែជុំមុនបានដាក់ 31 នៅពីមុខ 37 រួចហើយ ហើយការតម្រៀបបែប stable នឹងរក្សាវាទុកដដែល។ ដូច្នេះបន្ទាប់ពីដំណើរការខ្ទង់ដប់ តម្លៃទាំងអស់ត្រូវបានតម្រៀបតាមពីរខ្ទង់ចុងក្រោយ ហើយបន្តបែបនេះរហូតដល់ខ្ទង់ធំបំផុត។
Time និង space complexity នៃ radix sort
ជុំនីមួយៗជា counting sort ដែលមានគោល b = 10 ដោយចំណាយ O(n + b)។ សម្រាប់ខ្ទង់ចំនួន d សរុបគឺ O(d × (n + b))។ សម្រាប់ key ដែលមានទំហំថេរដូចជា integer 32-bit នោះ d គឺជាចំនួនថេរ ដូច្នេះ radix sort ដំណើរការក្នុង linear time។ វាត្រូវការ memory បន្ថែម O(n + b) សម្រាប់ output និង count arrays។ ការអនុវត្តជាក់ស្តែងច្រើនតែប្រើគោល 256 និងតម្រៀបមួយ byte ក្នុងមួយជុំ។
ពេលណាគួរប្រើ radix sort
Radix sort ល្អបំផុតលើ array ធំៗនៃចំនួនគត់ ខ្សែអក្សរមានប្រវែងថេរ កាលបរិច្ឆេទ អាសយដ្ឋាន IP ឬ keys ផ្សេងទៀតដែលផ្សំឡើងពីខ្ទង់ ឬតួអក្សរ។ GPU និង database engine ប្រើវិធីនេះ។ វាមិនមែនជាការតម្រៀបទូទៅទេ៖ វាត្រូវការ keys ដែលអាចបំបែកជាខ្ទង់បាន ហើយសម្រាប់ array តូចៗ ការដំណើរការជុំនីមួយៗចំណាយច្រើនជាង comparison sort ធម្មតា។
រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងរបាររំកិលល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ radix sort គឺជាអ្វី?
O(d × (n + b)) ដែល d ជាចំនួនខ្ទង់ n ជាចំនួនធាតុ និង b ជាគោល (base 10 នៅទីនេះ)។
ហេតុអ្វីបានជា LSD radix sort ចាប់ផ្តើមពីខ្ទង់ចុងក្រោយ?
ពីព្រោះរាល់ជុំបន្ទាប់សុទ្ធតែជា stable sort វាអាចរក្សាលំដាប់ដែលបង្កើតឡើងដោយខ្ទង់តូចៗសម្រាប់តម្លៃដែលស្មើគ្នា។ បន្ទាប់ពីខ្ទង់ធំបំផុតរួចរាល់ លំដាប់នឹងត្រឹមត្រូវទាំងស្រុង។
តើ LSD និង MSD radix sort ខុសគ្នាយ៉ាងណា?
LSD ដំណើរការខ្ទង់ពីស្តាំបំផុតទៅឆ្វេងបំផុត និងតម្រូវឱ្យគ្រប់ key មានចំនួនខ្ទង់ស្មើគ្នា (ដោយថែមលេខសូន្យ)។ MSD ចាប់ផ្តើមពីខ្ទង់ឆ្វេងបំផុត និងតម្រៀប bucket នីមួយៗតាម recursion ដែលស័ក្តិសមសម្រាប់ string ដែលមានប្រវែងខុសៗគ្នា។
តើ radix sort លឿនជាង quick sort ដែរឬទេ?
សម្រាប់ key ចំនួនគត់ទំហំថេរជាច្រើន វាអាចលឿនជាងព្រោះវាជា linear។ សម្រាប់ array តូច ទិន្នន័យចម្រុះ ឬ keys ស្មុគស្មាញ quick sort ឬ built-in sort ជាទូទៅលឿនជាង និងសាមញ្ញជាង។