Bubble sort គឺជាក្បួនដោះស្រាយតម្រៀបលំដាប់ (sorting algorithm) ដែលងាយយល់បំផុត៖ វាដើរកាត់ array ដោយប្រៀបធៀបគូធាតុជិតខាងនីមួយៗ ហើយប្តូរទីតាំងពួកវាប្រសិនបើខុសលំដាប់។ បន្ទាប់ពីជុំនីមួយៗ តម្លៃធំជាងគេដែលនៅសល់នឹង “ផុសឡើង” ទៅកាន់ទីតាំងចុងក្រោយរបស់វា។ ឧបករណ៍ visualizer នេះបង្ហាញចលនានៃការប្រៀបធៀប និងការប្តូរទីតាំងជាបន្ទះឈរមានចលនា ព្រមទាំងបន្លិចបន្ទាត់ pseudocode ដែលកំពុងដំណើរការ។
សាកល្បង array ដែលបញ្ច្រាសដើម្បីមើលករណីអាក្រក់បំផុត (worst case) ដែលការប្រៀបធៀបទាំងអស់សុទ្ធតែនាំឱ្យមានការប្តូរទីតាំង និង array ដែលស្ទើរតែរៀបរយហើយដើម្បីមើលការបញ្ចប់មុនកំណត់៖ ប្រសិនបើមួយជុំពេញមិនមានការប្តូរទីតាំងទេ array ត្រូវបានរៀបរួចរាល់ហើយ ហើយក្បួននឹងឈប់។ កុងទ័ររាប់បង្ហាញពីទំហំការងារដែលកើនឡើងយ៉ាងលឿន ប្រហែល n²/2 ការប្រៀបធៀបសម្រាប់ n តម្លៃ។
របៀបប្រើឧបករណ៍ កម្មវិធីបង្ហាញ Bubble Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស ឬមានតម្លៃទោលតិចតួច។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរទៅមុខម្តងមួយការប្រៀបធៀប ឬមួយការប្តូរទីតាំង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ បន្ទះពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប, បន្ទះពណ៌ក្រហមកំពុងត្រូវបានប្តូរទីតាំង ឬសរសេរចូល, បន្ទះពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយរបស់វា។
- អានសារនៅខាងក្រោមកុងត្រូល និងបន្ទាត់ pseudocode ដែលបានបន្លិច ដើម្បីដឹងច្បាស់ពីអ្វីដែលក្បួនកំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន, ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបកុងទ័ររាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ កម្មវិធីបង្ហាញ Bubble Sort របស់ ToolOrca
- បន្ទះមានចលនាជាមួយមុខងារ play, pause, step ទៅមុខ និង step ថយក្រោយ
- គ្រាប់រំកិលល្បឿន និងគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយភ្លាមៗ
- កុងទ័ររាប់ចំនួនប្រៀបធៀប និងចំនួនប្តូរទីតាំង
- ទិន្នន័យបញ្ចូលបែបចៃដន្យ, ស្ទើរតែរៀបរយ, បញ្ច្រាស និងមានតម្លៃទោលតិចតួច ឬលេខផ្ទាល់ខ្លួនរបស់អ្នក
- បន្លិចបន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរសព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល bubble sort ដំណើរការ
Bubble sort ធ្វើការរត់កាត់ array ច្រើនដង។ ក្នុងការរត់ម្តងៗ វាប្រៀបធៀប a[j] និង a[j + 1] សម្រាប់គ្រប់ j ហើយប្តូរទីតាំងពួកវាពេលដែល a[j] ធំជាង។ តម្លៃធំបំផុតតែងតែឈ្នះការប្រៀបធៀប ដូច្នេះវារំកិលរហូតដល់ខាងចុងក្នុងការរត់ជុំទីមួយ។ ការរត់ជុំទីពីរក៏ធ្វើដូចគ្នាសម្រាប់តម្លៃធំទីពីរ ហើយបន្តបន្ទាប់ទៀត ដូច្នេះការរត់ជុំនីមួយៗអាចឈប់មុនមួយទីតាំង។
កំណែដែលបានកែលម្អ (optimized) ដែលបង្ហាញនៅទីនេះ នឹងចាំថាតើការរត់មួយជុំមានការប្តូរទីតាំងដែរឬទេ។ បើគ្មានទេ គូធាតុជិតខាងទាំងអស់គឺត្រូវតាមលំដាប់ហើយ ដូច្នេះ array ទាំងមូលត្រូវបានតម្រៀបរួចរាល់ ហើយក្បួននឹងឈប់ភ្លាម។ នេះហើយជាមូលហេតុដែលធ្វើឱ្យ bubble sort មានកម្រិត O(n) លើ array ដែលបានរៀបរួចរាល់ហើយ។
Time និង space complexity នៃ bubble sort
ក្នុងករណីអាក្រក់បំផុត (array បញ្ច្រាស) និងជាមធ្យម bubble sort ធ្វើការប្រៀបធៀបប្រហែល n(n − 1)/2 ដង និងការប្តូរទីតាំងក្នុងចំនួនប្រហាក់ប្រហែលគ្នា ដែលជា O(n²)៖ ការតម្រៀប 1,000 តម្លៃត្រូវចំណាយការប្រៀបធៀបប្រហែល 500,000 ដង។ ករណីល្អបំផុត គឺ array ដែលបានរៀបរួចស្រេច ត្រូវការការរត់មួយជុំដែលមាន n − 1 ការប្រៀបធៀប៖ O(n)។ វាដំណើរការតម្រៀបលើទីតាំងផ្ទាល់ (in place) ដោយប្រើអង្គចងចាំបន្ថែម O(1) និងមានលក្ខណៈ stable ពីព្រោះតម្លៃស្មើគ្នាមិនដែលត្រូវបានប្តូរទីតាំងឡើយ។
ពេលណាគួរប្រើ bubble sort
Bubble sort ត្រូវបានប្រើជាចម្បងសម្រាប់ការបង្រៀន។ វាងាយស្រួលសរសេរកូដ និងងាយស្រួលផ្ទៀងផ្ទាត់ភាពត្រឹមត្រូវ ប៉ុន្តែយឺតជាង insertion sort លើស្ទើរតែគ្រប់ទិន្នន័យបញ្ចូលទាំងអស់។ សូមប្រើ insertion sort សម្រាប់ array តូចៗ ឬស្ទើរតែរៀបរយរួច ហើយប្រើ merge sort, quick sort ឬ built-in sort របស់ភាសាអ្នកសម្រាប់ទិន្នន័យជាក់ស្តែង។ ប្រៀបធៀបពួកវាទាំងអស់នៅក្នុង ការប្រណាំង sorting algorithm។
គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយឧបករណ៍បញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីលោតទៅកាន់ជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ bubble sort គឺជាអ្វី?
O(n²) ក្នុងករណីមធ្យម និងករណីអាក្រក់បំផុត ហើយ O(n) ក្នុងករណីល្អបំផុតនៅពេល array ត្រូវបានរៀបរយរួចស្រេច និងមានការប្រើប្រាស់ការត្រួតពិនិត្យដើម្បីចាកចេញមុនកំណត់។
តើ bubble sort មានលក្ខណៈ stable ដែរឬទេ?
បាទ/ចាស។ វាប្តូរទីតាំងធាតុជិតខាងតែនៅពេលធាតុខាងឆ្វេងធំជាងដាច់ខាតប៉ុណ្ណោះ ដូច្នេះតម្លៃស្មើគ្នានៅតែរក្សាលំដាប់ដើមដដែល។
ហេតុអ្វីបានជាគេហៅថា bubble sort?
ពីព្រោះតម្លៃធំៗផុសឡើងទៅខាងចុង array ដូចជាពពុះទឹកផុសឡើងទៅលើផ្ទៃទឹក តាមរយៈការប្តូរទីតាំងម្តងមួយៗ។
តើ bubble sort ត្រូវការរត់ប៉ុន្មានជុំ?
យ៉ាងច្រើនបំផុត n − 1 ជុំសម្រាប់ n តម្លៃ។ ជាមួយនឹង flag ត្រួតពិនិត្យការប្តូរទីតាំង វាឈប់ភ្លាមៗនៅពេលការរត់មួយជុំមិនមានការប្តូរទីតាំង។
តើគេធ្លាប់ប្រើ bubble sort ក្នុងការអនុវត្តជាក់ស្តែងដែរឬទេ?
កម្រណាស់។ Insertion sort ធ្វើការងារដូចគ្នានេះបានលឿនជាង។ Bubble sort នៅតែមានវត្តមានពីព្រោះវាជាឧទាហរណ៍ដំបូងដ៏ច្បាស់លាស់មួយនៃ sorting algorithm និងការកើនឡើងកម្រិត O(n²)。