តើ sorting algorithm មួយណាដើរលឿនជាងគេ? វាអាស្រ័យលើទិន្នន័យ។ ទំព័រនេះដាក់ algorithm រហូតដល់ 8 ឲ្យប្រណាំងគ្នាលើ array ដូចគ្នាបេះបិទ៖ bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, counting sort និង radix sort។ រាល់ tick នីមួយៗ algorithm ដំណើរការមួយជំហាន (ការប្រៀបធៀប, ការ swap ឬការសរសេរចូល array) ដូច្នេះ algorithm ណាដែលត្រូវការជំហានតិចជាងគេ នឹងបញ្ចប់មុនគេ។
ផ្លាស់ប្តូរ input នោះលទ្ធផលក៏នឹងប្រែប្រួល។ លើទិន្នន័យចៃដន្យ (random) ពួក sort O(n log n) នឹងនាំមុខពួក O(n²) យ៉ាងឆ្ងាយ។ លើទិន្នន័យដែលជិត sorted ស្រាប់ insertion sort នឹងឈ្នះភ្លាមៗ។ លើទិន្នន័យដែលរៀបបញ្ច្រាស quick sort ដែលប្រើ pivot ជាធាតុចុងក្រោយនឹងយឺតយ៉ាងខ្លាំង។ តារាង complexity នៅខាងក្រោមក៏បង្ហាញករណី best, average និង worst សម្រាប់ algorithm នីមួយៗផងដែរ។
របៀបប្រើឧបករណ៍ ប្រៀបធៀប Sorting Algorithm
- ធីកជ្រើសរើស algorithms ដែលអ្នកចង់ដាក់ប្រណាំង។
- ជ្រើសរើស ទំហំ array និងប្រភេទ input៖ random, ជិត sorted, បញ្ច្រាស ឬមានតម្លៃដដែលៗច្រើន។
- ចុច Play។ គន្លងនីមួយៗនឹងបង្ហាញរបារ, ចំនួនប្រៀបធៀប និងចំនួន swap ព្រមទាំងចំណាត់ថ្នាក់ពេលបញ្ចប់។
- ប្រើ Step, Back និងរបាររំកិលទីតាំងដើម្បីប្រៀបធៀបគ្រប់ពេល ហើយចុច New race ដើម្បីទទួលបានទិន្នន័យថ្មី។
ហេតុអ្វីប្រើ ប្រៀបធៀប Sorting Algorithm របស់ ToolOrca
- algorithm តម្រៀបរហូតដល់ 8 ប្រណាំងគ្នាលើទិន្នន័យតែមួយ
- ប្រភេទ input ចំនួន 4 និងទំហំពី 10 ដល់ 100
- រាប់ចំនួនប្រៀបធៀប, swap និងចំណាត់ថ្នាក់បញ្ចប់សម្រាប់គន្លងនីមួយៗ
- ប៊ូតុង Play, pause, ទៅមុខមួយជំហាន, ថយក្រោយ និងការកំណត់ល្បឿន
- តារាង complexity សម្រាប់គ្រប់ algorithm
- ដំណើរការលើទូរស័ព្ទ និងថេប្លេត
ការប្រៀបធៀប sorting algorithm តាមរយៈ Big O
វិធី sort សាមញ្ញៗ (bubble, selection, insertion) ប្រើពេលជាមធ្យម O(n²)៖ កាលណាទិន្នន័យកើនឡើងទ្វេដង ការងារនឹងកើនឡើងបួនដង។ Merge sort, heap sort និង quick sort (ជាមធ្យម) ប្រើពេល O(n log n)៖ កាលណាទិន្នន័យកើនឡើងទ្វេដង ការងារកើនឡើងជាងទ្វេដងបន្តិចបន្តួចប៉ុណ្ណោះ។ សម្រាប់ទិន្នន័យ 100 តម្លៃ វាប្រៀបដូចជា 5,000 ជំហានធៀបនឹង 700 ជំហាន។ សម្រាប់ទិន្នន័យមួយលាន វាស្មើនឹង 500 ពាន់លានធៀបនឹង 20 លាន។
ជាទូទៅ គ្មាន comparison-based sort ណាអាចលឿនជាង O(n log n) បានទេ។ ចំណែក counting sort និង radix sort អាចគេចផុតពីដែនកំណត់នេះ ដោយមិនធ្វើការប្រៀបធៀបទាល់តែសោះ គឺវាប្រើតម្លៃផ្ទាល់ជា index តែម្តង ដែលវិធីនេះដំណើរការបានល្អសម្រាប់ចំនួនគត់ក្នុងចន្លោះជាក់លាក់ណាមួយ។
តើគួរប្រើ sorting algorithm មួយណា?
ក្នុងការសរសេរកូដជាក់ស្តែង៖ ប្រើ built-in sort របស់ភាសាដែលអ្នកកំពុងប្រើ។ Python និង Java (សម្រាប់ object) ប្រើ Timsort ដែលជាការរួមបញ្ចូលគ្នារវាង merge និង insertion sort ប្រកបដោយ stability។ C++ std::sort ប្រើ introsort ដែលជា quick sort រួមផ្សំជាមួយ heap sort និង insertion sort ជាជំនួយ។ សម្រាប់ array តូចៗ ឬជិត sorted៖ ប្រើ insertion sort។ បើត្រូវការ stability ឬធានា O(n log n)៖ ប្រើ merge sort។ បើត្រូវការ memory បន្ថែមត្រឹម O(1) និងមានការធានា៖ ប្រើ heap sort។ ល្បឿនមធ្យមលឿនបំផុតលើ memory៖ quick sort ជាមួយ pivot ល្អ។ ចំនួនគត់តូចៗ៖ counting sort; ចំនួនគត់ដែលមានប្រវែងខ្ទង់ថេរច្រើន៖ radix sort។
ហេតុអ្វីបានជាការប្រណាំងរាប់ជាជំហាន មិនរាប់ជាវិនាទី
ការវាស់ជាមីលីវិនាទីក្នុង browser អាស្រ័យលើឧបករណ៍របស់អ្នក និងកម្មវិធីផ្សេងទៀតដែលកំពុងដំណើរការ។ ការរាប់ជំហាន (ចំនួនប្រៀបធៀប, swap និងការសរសេរ) បង្ហាញពីភាពខុសគ្នានៃ algorithm យ៉ាងច្បាស់លាស់។ រយៈពេលដំណើរការជាក់ស្តែងក៏អាស្រ័យលើ cache និងកត្តា constant ផ្សេងៗផងដែរ ដែលជាហេតុធ្វើឲ្យ quick sort ច្រើនតែឈ្នះ merge sort ក្នុងការអនុវត្តជាក់ស្តែង ទោះបីជាមានចំនួនជំហានប្រហាក់ប្រហែលគ្នាក៏ដោយ។
រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយនឹងប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, ទៅមុខមួយជំហាន, ថយក្រោយមួយជំហាន និងរបារកំណត់ល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីផ្លោះទៅជំហានណាមួយ ឬចុចលើផ្ទាំងរូបភាពរួចប្រើ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។
សំណួរដែលសួរញឹកញាប់
តើ sorting algorithm មួយណាដំណើរការលឿនជាងគេ?
គ្មាន algorithm ណាឈ្នះគ្រប់ពេលនោះទេ។ Quick sort ជាទូទៅលឿនជាងគេលើទិន្នន័យ random ក្នុង memory, insertion sort ឈ្នះលើទិន្នន័យតូច ឬជិត sorted ហើយ counting sort ឬ radix sort ឈ្នះលើលេខចំនួនគត់តូចៗ។ Built-in hybrid sort បានរួមបញ្ចូលចំណុចខ្លាំងទាំងនេះជាមួយគ្នា។
ហេតុអ្វីបានជា insertion sort ឈ្នះលើទិន្នន័យដែលជិត sorted?
ពេលវេលាដំណើរការរបស់វាកើនឡើងតាមចំនួនគូដែលខុសលំដាប់។ Array ដែលជិត sorted មានគូខុសលំដាប់តិចតួចបំផុត ដូច្នេះ insertion sort ដំណើរការប្រហែល n ជំហានប៉ុណ្ណោះ។
Why is quick sort slow on sorted or reversed input here?
កំណែនេះប្រើធាតុចុងក្រោយជា pivot។ លើទិន្នន័យ sorted ឬបញ្ច្រាស pivot នោះតែងតែជាតម្លៃធំបំផុត ឬតូចបំផុតជានិច្ច ដូច្នេះការបែងចែក (partition) នីមួយៗកាត់បន្ថយបានតែមួយធាតុប៉ុណ្ណោះ ដែលធ្វើឲ្យពេលវេលាក្លាយជា O(n²)។
Which sorting algorithms are stable?
Bubble, insertion, merge, counting និង radix sort គឺជា stable sort។ ចំណែក selection, quick និង heap sort គឺមិន stable ទេក្នុងទម្រង់ទូទៅរបស់វា។
What sorting algorithm does Python or Java use?
sorted() និង list.sort() របស់ Python ប្រើ Timsort។ Java ប្រើ Timsort សម្រាប់ object និង dual-pivot quick sort សម្រាប់ primitive array។ C++ std::sort ប្រើ introsort។