Counting sort មិនធ្វើការប្រៀបធៀបតម្លៃទាល់តែសោះ។ វារាប់ចំនួនដងដែលតម្លៃនីមួយៗលេចឡើង បំប្លែងចំនួនទាំងនោះទៅជាផលបូកសរុបបន្ត (prefix sums) ដែលបង្ហាញពីកន្លែងបញ្ចប់នៃក្រុមតម្លៃនីមួយៗ រួចដាក់តម្លៃទាំងអស់ចូលទៅក្នុងទីតាំងចុងក្រោយក្នុង output array តែម្តង។ ឧបករណ៍បង្ហាញនេះបង្ហាញ array រាប់ និង output array នៅខាងក្រោមរបារ ព្រមទាំង highlight ប្រឡោះដែលកំពុងត្រូវបានកែប្រែនៅជំហាននីមួយៗ។
វាដំណើរការក្នុងរយៈពេល O(n + k) ដែល k ជាចន្លោះតម្លៃ ដូច្នេះវាឈ្នះ comparison sort ទាំងអស់នៅពេលតម្លៃជាចំនួនគត់តូចៗ ដូចជា អាយុ ពិន្ទុ ឬខ្ទង់លេខ។ តម្លៃនៅទីនេះមានចន្លោះពី 0 ដល់ 15 ដើម្បីឱ្យ array រាប់បង្ហាញល្មមលើអេក្រង់។ អ្នកអាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនរហូតដល់ 50 ដើម្បីសាកល្បងចន្លោះធំជាងនេះ។
របៀបប្រើឧបករណ៍ កម្មវិធីបង្ហាញ Counting Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស ឬមានតម្លៃដូចគ្នាច្រើន។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរមួយការប្រៀបធៀប ឬមួយការ swap ម្តង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ របារពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប ពណ៌ក្រហមកំពុង swap ឬសរសេរ ហើយពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយត្រឹមត្រូវ។
- អានសារខាងក្រោមប៊ូតុងបញ្ជា និងបន្ទាត់ pseudocode ដែលបាន highlight ដើម្បីដឹងច្បាស់ពីអ្វីដែល algorithm កំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបចំនួនរាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ កម្មវិធីបង្ហាញ Counting Sort របស់ ToolOrca
- របារមានចលនាជាមួយប៊ូតុង play, pause, step និង step back
- របាររំកិលល្បឿន និងរបាររំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយ
- បង្ហាញ array រាប់ និង output array មួយជំហានម្តងៗ
- ទិន្នន័យចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស និងមានតម្លៃដូចគ្នាច្រើន ឬលេខផ្ទាល់ខ្លួន
- Highlight បន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជាភាសា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរស័ព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល counting sort ដំណើរការ
1. រាប់៖ បង្កើត array count ដែលមានទំហំ max + 1 ពោរពេញដោយលេខ 0 ហើយបូក 1 ទៅ count[x] សម្រាប់តម្លៃ x នីមួយៗ។ 2. Prefix sums៖ សម្រាប់ v ពី 1 ដល់ max បូក count[v − 1] ទៅ count[v]។ ពេលនេះ count[v] គឺជាចំនួននៃតម្លៃ ≤ v ដែលជាទីតាំងលើសមួយបន្ទាប់ពីទីតាំងចុងក្រោយរបស់ v។ 3. ដាក់ទីតាំង៖ រត់កាត់ទិន្នន័យបញ្ចូលពីស្តាំទៅឆ្វេង សម្រាប់ x នីមួយៗ បន្ថយ count[x] និងសរសេរ x នៅ output[count[x]]។ 4. ចម្លង output ត្រឡប់មកវិញ។
ការរត់ពីស្តាំទៅឆ្វេងក្នុងជំហានទី 3 រក្សាតម្លៃស្មើគ្នាតាមលំដាប់ដើមរបស់វា ដែលធ្វើឱ្យ counting sort ក្លាយជា stable sort។ ភាព stable នេះហើយដែលអនុញ្ញាតឱ្យ radix sort យកវាទៅប្រើតាមខ្ទង់នីមួយៗបាន។
Time និង space complexity នៃ counting sort
ការរាប់ចំណាយ O(n) ការធ្វើ prefix sums ចំណាយ O(k) និងការដាក់ទីតាំងចំណាយ O(n) ដូច្នេះសរុបគឺ O(n + k) សម្រាប់ time និង O(n + k) សម្រាប់ space បន្ថែម ដែល k ជាតម្លៃធំបំផុត។ នៅពេល k មានទំហំប្រហាក់ប្រហែល n ឬតូចជាង វានឹងដំណើរការក្នុងកម្រិត linear time ដែលលឿនជាង O(n log n) នៃ comparison sorts ព្រោះវាមិនមានការប្រៀបធៀបទាល់តែសោះ។
ពេលណាគួរប្រើ counting sort
ប្រើ counting sort សម្រាប់ចំនួនគត់ (ឬ keys ដែលផ្គូផ្គងនឹងចំនួនគត់) ក្នុងចន្លោះតូចមួយ៖ ពិន្ទុប្រឡង 0 ដល់ 100, អាយុ, តួអក្សរ ឬខ្ទង់លេខក្នុង radix sort។ កុំប្រើវានៅពេលចន្លោះតម្លៃធំខ្លាំងធៀបនឹងចំនួនធាតុ ឧទាហរណ៍ តម្រៀបលេខ 10 ខ្ទង់ដែលមានតម្លៃរហូតដល់មួយពាន់លាន ព្រោះ array រាប់នឹងមានទំហំធំសម្បើមខ្លាំង។
រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងរបាររំកិលល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ counting sort គឺជាអ្វី?
O(n + k) ដែល n ជាចំនួនធាតុ និង k ជាចន្លោះតម្លៃ (តម្លៃធំបំផុតបូក 1)។
ហេតុអ្វី counting sort អាចលឿនជាង O(n log n)?
ដែនកំណត់ O(n log n) អនុវត្តចំពោះតែវិធីតម្រៀបដែលដំណើរការដោយការប្រៀបធៀបតម្លៃប៉ុណ្ណោះ។ Counting sort ប្រើប្រាស់តម្លៃទាំងនោះធ្វើជា index របស់ array ជំនួសវិញ។
តើ counting sort អាចប្រើជាមួយលេខអវិជ្ជមានបានទេ?
បាន ដោយការរំកិលតម្លៃ (shifting)៖ ដកតម្លៃអប្បបរមាចេញពី key នីមួយៗដើម្បីឱ្យតម្លៃតូចបំផុតក្លាយជា 0 រួចបូកវាត្រឡប់មកវិញនៅពេលសរសេរ output។
តើ counting sort ជា stable sort ដែរឬទេ?
ពិតប្រាកដណាស់ នៅពេលដែលជំហានដាក់ទីតាំងរត់កាត់ទិន្នន័យបញ្ចូលពីស្តាំទៅឆ្វេង ដូចដែលបានបង្ហាញនៅទីនេះ។