Selection sort បំបែក array ជាពីរគឺ ផ្នែកដែលបានតម្រៀបរួចនៅខាងឆ្វេង និងផ្នែកមិនទាន់តម្រៀបនៅខាងស្តាំ។ ក្នុងការរត់ម្តងៗ វាស្កេនផ្នែកមិនទាន់តម្រៀបដើម្បីរកតម្លៃតូចបំផុត បន្ទាប់មកប្តូរវាចូលទៅទីតាំងដំបូងគេនៃផ្នែកមិនទាន់តម្រៀប។ ឧបករណ៍ visualizer នេះបង្ហាញការស្កេនដោយមានតម្លៃតូចបំផុតបច្ចុប្បន្នជាពណ៌ស្វាយ និងបេក្ខភាពនីមួយៗជាពណ៌ទឹកក្រូច ដូច្នេះអ្នកអាចឃើញការផ្លាស់ប្តូរតម្លៃតូចបំផុតនៅពេលរកឃើញតម្លៃដែលតូចជាង។
សង្កេតមើលកុងទ័ររាប់៖ selection sort តែងតែធ្វើការប្រៀបធៀបក្នុងចំនួនដដែល គឺប្រហែល n²/2 មិនថាទិន្នន័យបញ្ចូលបែបណាក៏ដោយ ប៉ុន្តែធ្វើការប្តូរទីតាំងយ៉ាងច្រើនបំផុត n − 1 ដងប៉ុណ្ណោះ។ ចំណុចនេះធ្វើឱ្យវាមានប្រយោជន៍នៅពេលការសរសេរចូលអង្គចងចាំមានតម្លៃថ្លៃជាងការអានខ្លាំង។
របៀបប្រើឧបករណ៍ បង្ហាញដំណើរការ Selection Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស ឬមានតម្លៃទោលតិចតួច។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរទៅមុខម្តងមួយការប្រៀបធៀប ឬមួយការប្តូរទីតាំង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ បន្ទះពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប, បន្ទះពណ៌ក្រហមកំពុងត្រូវបានប្តូរទីតាំង ឬសរសេរចូល, បន្ទះពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយរបស់វា។
- អានសារនៅខាងក្រោមកុងត្រូល និងបន្ទាត់ pseudocode ដែលបានបន្លិច ដើម្បីដឹងច្បាស់ពីអ្វីដែលក្បួនកំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន, ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបកុងទ័ររាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ បង្ហាញដំណើរការ Selection Sort របស់ ToolOrca
- បន្ទះមានចលនាជាមួយមុខងារ play, pause, step ទៅមុខ និង step ថយក្រោយ
- គ្រាប់រំកិលល្បឿន និងគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយភ្លាមៗ
- កុងទ័ររាប់ចំនួនប្រៀបធៀប និងចំនួនប្តូរទីតាំង
- ទិន្នន័យបញ្ចូលបែបចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស និងមានតម្លៃទោលតិចតួច ឬលេខផ្ទាល់ខ្លួនរបស់អ្នក
- បន្លិចបន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរសព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល selection sort ដំណើរការ
សម្រាប់ i ពី 0 ទៅ n − 2 កំណត់ min = i បន្ទាប់មកប្រៀបធៀប a[min] ជាមួយគ្រប់ a[j] សម្រាប់ j ពី i + 1 ទៅ n − 1 ដោយធ្វើបច្ចុប្បន្នភាព min រាល់ពេលដែលឃើញតម្លៃតូចជាង។ បន្ទាប់ពីស្កេនចប់ ប្តូរទីតាំង a[i] ជាមួយ a[min]។ ពេលនេះទីតាំងពី 0 ទៅ i ផ្ទុកតម្លៃតូចបំផុតចំនួន i + 1 តាមលំដាប់ ហើយការរត់ជុំបន្ទាប់ចាប់ផ្តើមរំកិលទៅស្តាំមួយទីតាំង។
Time និង space complexity នៃ selection sort
ការស្កេនធ្វើឡើងចំនួន (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 ការប្រៀបធៀបក្នុង គ្រប់ ករណីទាំងអស់ ដូច្នេះរយៈពេលដំណើរការគឺ O(n²) ទាំងល្អបំផុត មធ្យម និងអាក្រក់បំផុត ទោះបីជាទិន្នន័យបញ្ចូលបានរៀបរួចក៏មិនជួយដែរ។ វាធ្វើការប្តូរទីតាំងច្រើនបំផុត n − 1 ដង, តម្រៀបលើទីតាំងផ្ទាល់ដោយប្រើអង្គចងចាំបន្ថែម O(1) និង មិន stable ទេ៖ ការប្តូរទីតាំងឆ្លងកាត់ចម្ងាយឆ្ងាយអាចផ្លោះរំលងតម្លៃដែលស្មើគ្នា។ ឧទាហរណ៍ ការតម្រៀប [4a, 4b, 1] នឹងប្តូរ 4a ទៅចុងក្រោយ នៅពីក្រោយ 4b។
ពេលណាគួរប្រើ selection sort
Selection sort មានទម្រង់សាមញ្ញ និងធ្វើការសរសេរតិចតួចបំផុត ដែលចំណុចនេះសំខាន់សម្រាប់ flash memory ឬនៅពេលការរំកិលធាតុនីមួយៗត្រូវចំណាយខ្ពស់។ សម្រាប់ការប្រើប្រាស់ទូទៅ insertion sort លឿនជាងលើ array តូចៗ ឬស្ទើរតែរៀបរយរួច ហើយក្បួនតម្រៀបប្រភេទ O(n log n) គឺលឿនជាងឆ្ងាយណាស់លើ array ធំៗ។ Heap sort គឺជា selection sort ដែលប្រើ heap ដើម្បីស្វែងរកតម្លៃតូចបំផុត (ឬធំបំផុត) យ៉ាងឆាប់រហ័ស។
គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយឧបករណ៍បញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅកាន់ជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ selection sort គឺជាអ្វី?
O(n²) ក្នុងករណីល្អបំផុត មធ្យម និងអាក្រក់បំផុត ពីព្រោះវាត្រូវតែស្កេនផ្នែកមិនទាន់តម្រៀបទាំងមូលជានិច្ច។
តើ selection sort មានលក្ខណៈ stable ដែរឬទេ?
មិន stable ទេក្នុងទម្រង់ធម្មតារបស់វា។ ការប្តូរតម្លៃតូចបំផុតទៅកាន់ទីតាំងត្រឹមត្រូវ អាចរំកិលធាតុមួយរំលងកាត់ធាតុមួយទៀតដែលមានតម្លៃស្មើគ្នា។
តើ selection sort ធ្វើការប្តូរទីតាំងប៉ុន្មានដង?
ច្រើនបំផុត n − 1 ដង ពោលគឺម្តងក្នុងការរត់មួយជុំ ដែលតិចជាង bubble sort ឬ insertion sort។
តើ selection sort និង bubble sort ខុសគ្នាយ៉ាងដូចម្តេច?
ទាំងពីរមានកម្រិត O(n²) ដូចគ្នា ប៉ុន្តែ selection sort ប្តូរទីតាំងម្តងប៉ុណ្ណោះក្នុងមួយជុំបន្ទាប់ពីរកឃើញតម្លៃតូចបំផុត ខណៈ bubble sort ប្តូរទីតាំងធាតុជិតខាងច្រើនដងក្នុងមួយជុំ។ Bubble sort អាចឈប់មុនកំណត់លើទិន្នន័យដែលបានរៀបរយរួច ប៉ុន្តែ selection sort មិនអាចទេ។