ស្វែងយល់ពីរបៀបប្រើប្រាស់មុខងារ Python Sort សម្រាប់តម្រៀបបញ្ជី អារេ វចនានុក្រម ។ល។ ដោយប្រើវិធីតម្រៀប និងក្បួនដោះស្រាយផ្សេងៗនៅក្នុង Python៖
ការតម្រៀបគឺជាបច្ចេកទេសដែលប្រើសម្រាប់តម្រៀប ទិន្នន័យតាមលំដាប់លំដោយតាមលំដាប់ឡើង ឬចុះ។
ភាគច្រើន ទិន្នន័យនៃគម្រោងធំៗមិនត្រូវបានរៀបចំតាមលំដាប់លំដោយត្រឹមត្រូវទេ ហើយវាបង្កើតបញ្ហានៅពេលចូលប្រើ និងទាញយកទិន្នន័យដែលត្រូវការប្រកបដោយប្រសិទ្ធភាព។
បច្ចេកទេសតម្រៀបត្រូវបានប្រើដើម្បីដោះស្រាយបញ្ហានេះ។ Python ផ្តល់នូវបច្ចេកទេសតម្រៀបផ្សេងៗ ឧទាហរណ៍ ការតម្រៀបពពុះ ការតម្រៀបការបញ្ចូល ការតម្រៀបបញ្ចូលគ្នា ការតម្រៀបរហ័ស។
Python Sort
Syntax of Python Sort
ដើម្បីអនុវត្តការតម្រៀប Python ផ្តល់នូវមុខងារដែលភ្ជាប់មកជាមួយ ពោលគឺមុខងារ “sort()”។ វាត្រូវបានប្រើដើម្បីតម្រៀបធាតុទិន្នន័យនៃបញ្ជីតាមលំដាប់ឡើង ឬតាមលំដាប់ចុះ។
តោះយល់ពីគោលគំនិតនេះជាឧទាហរណ៍។
ឧទាហរណ៍ 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
លទ្ធផល៖
ក្នុងឧទាហរណ៍នេះ បញ្ជីដែលមិនបានតម្រៀបដែលបានផ្តល់ឱ្យត្រូវបានតម្រៀបទៅជាលំដាប់ឡើងដោយប្រើមុខងារ “តម្រៀប()” .
ឧទាហរណ៍ 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
លទ្ធផល
ក្នុងឧទាហរណ៍ខាងលើ បញ្ជីដែលមិនរៀបចំដែលបានផ្តល់ឲ្យត្រូវបានតម្រៀបតាមលំដាប់បញ្ច្រាសដោយប្រើមុខងារ “ sort(បញ្ច្រាស = True )”។
Timeកន្លែង តម្រៀបពពុះ O(n) O(n2) O(n2) O(1) បាទ/ចាស បាទ/ចាស ការតម្រៀបការបញ្ចូល O(n) O(n2) O(n2) O(1) បាទ បាទ តម្រៀបរហ័ស O(n log(n)) O(n log(n)) O(n2) O(N) ទេ បាទ/ចាស បញ្ចូលចូលគ្នា តម្រៀប O(n log(n)) O(n log(n)) O(n log(n)) O(N) បាទ/ចាស ទេ ការតម្រៀបជួរ O(n log (n)) O(n log(n)) O(n log(n)) O(1) ទេ បាទ/ចាស
នៅក្នុងតារាងប្រៀបធៀបខាងលើ “O” គឺជាសញ្ញាណ Big Oh ដែលបានពន្យល់ខាងលើ ចំណែក “n” និង “N” មានន័យថាទំហំនៃការបញ្ចូល .
សំណួរដែលគេសួរញឹកញាប់
សំណួរ #1) តើអ្វីជាតម្រៀប () នៅក្នុង Python?
ចម្លើយ៖ នៅក្នុង Python sort() គឺជាមុខងារដែលប្រើដើម្បីតម្រៀបបញ្ជី ឬអារេក្នុងលំដាប់ជាក់លាក់មួយ។ មុខងារនេះជួយសម្រួលដំណើរការនៃការតម្រៀបពេលកំពុងធ្វើការលើគម្រោងធំៗ។ វាមានប្រយោជន៍ខ្លាំងណាស់សម្រាប់អ្នកអភិវឌ្ឍន៍។
សំណួរ #2) តើអ្នកតម្រៀបនៅក្នុង Python ដោយរបៀបណា?
ចម្លើយ៖ Python ផ្តល់នូវបច្ចេកទេសតម្រៀបផ្សេងៗ ដែលត្រូវបានប្រើដើម្បីតម្រៀបធាតុ។ ឧទាហរណ៍ តម្រៀបរហ័ស តម្រៀបបញ្ចូលគ្នា តម្រៀបពពុះ តម្រៀបបញ្ចូល។ល។ បច្ចេកទេសតម្រៀបទាំងអស់មានប្រសិទ្ធភាព និងងាយស្រួលយល់។
សំណួរ #3) តើ Python តម្រៀប () ការងារ?
ចម្លើយ៖ តម្រៀប()មុខងារយកអារេដែលបានផ្តល់ឱ្យជាការបញ្ចូលពីអ្នកប្រើប្រាស់ ហើយតម្រៀបវាតាមលំដាប់ជាក់លាក់មួយដោយប្រើក្បួនដោះស្រាយតម្រៀប។ ជម្រើសនៃក្បួនដោះស្រាយអាស្រ័យលើជម្រើសរបស់អ្នកប្រើ។ អ្នកប្រើប្រាស់អាចប្រើ Quick sort, Merge sort, Bubble sort, Insertion sort ជាដើម អាស្រ័យលើតម្រូវការរបស់អ្នកប្រើប្រាស់។
Conclusion
នៅក្នុងមេរៀនខាងលើ យើងបានពិភាក្សាអំពីបច្ចេកទេសតម្រៀបនៅក្នុង Python រួមជាមួយនឹង បច្ចេកទេសតម្រៀបទូទៅ។
- ការតម្រៀបពពុះ
- ការតម្រៀបការបញ្ចូល
- តម្រៀបរហ័ស
យើងបានសិក្សាអំពីភាពស្មុគស្មាញពេលវេលា និងអត្ថប្រយោជន៍របស់ពួកគេ & គុណវិបត្តិ។ យើងក៏បានប្រៀបធៀបបច្ចេកទេសខាងលើទាំងអស់។
ភាពស្មុគស្មាញនៃក្បួនដោះស្រាយការតម្រៀបភាពស្មុគស្មាញនៃពេលវេលាគឺជាចំនួនពេលវេលាដែលប្រើដោយកុំព្យូទ័រដើម្បីដំណើរការក្បួនដោះស្រាយជាក់លាក់មួយ។ វាមានបីប្រភេទនៃករណីស្មុគស្មាញពេលវេលា។
- ករណីអាក្រក់បំផុត៖ ពេលវេលាអតិបរមាដែលប្រើដោយកុំព្យូទ័រដើម្បីដំណើរការកម្មវិធី។
- ករណីជាមធ្យម៖ ពេលវេលាដែលប្រើចន្លោះអប្បបរមា និងអតិបរមាដោយកុំព្យូទ័រដើម្បីដំណើរការកម្មវិធី។
- ករណីល្អបំផុត៖ ពេលវេលាអប្បបរមាដែលប្រើដោយកុំព្យូទ័រដើម្បីដំណើរការកម្មវិធី។ វាជាករណីដ៏ល្អបំផុតនៃភាពស្មុគស្មាញនៃពេលវេលា។
កំណត់ចំណាំស្មុគស្មាញ
Big Oh Notation, O: Big oh notation គឺជាវិធីផ្លូវការដើម្បីបង្ហាញពីព្រំដែនខាងលើ នៃពេលវេលាដំណើរការនៃក្បួនដោះស្រាយ។ វាត្រូវបានប្រើដើម្បីវាស់ស្ទង់ភាពស្មុគស្មាញនៃពេលវេលាដ៏អាក្រក់បំផុត ឬយើងនិយាយថាចំនួនពេលវេលាដ៏ធំបំផុតដែលប្រើដោយក្បួនដោះស្រាយដើម្បីបញ្ចប់។
Big omega Notation, : Big omega notation គឺ វិធីផ្លូវការដើម្បីបង្ហាញពីដែនកំណត់ទាបបំផុតនៃពេលវេលាដំណើរការនៃក្បួនដោះស្រាយ។ វាត្រូវបានប្រើដើម្បីវាស់ស្ទង់ភាពស្មុគស្មាញនៃករណីល្អបំផុត ឬយើងនិយាយថាចំនួនដ៏ល្អបំផុតនៃពេលវេលាដែលត្រូវបានយកដោយក្បួនដោះស្រាយ។
Theta Notation, : ការសម្គាល់ Theta គឺជាមធ្យោបាយផ្លូវការក្នុងការបញ្ជូន ទាំងព្រំដែន ពោលគឺ ទាប និងខាងលើនៃពេលវេលាដែលយកដោយក្បួនដោះស្រាយដើម្បីបញ្ចប់។
តម្រៀបវិធីសាស្ត្រក្នុង Python
តម្រៀបពពុះ
ការតម្រៀបពពុះគឺជាវិធីសាមញ្ញបំផុតក្នុងការតម្រៀបទិន្នន័យ ដែលប្រើបច្ចេកទេស brute force ។ វានឹងធ្វើឡើងវិញទៅធាតុទិន្នន័យនីមួយៗ ហើយប្រៀបធៀបវាជាមួយនឹងធាតុផ្សេងទៀត។ដើម្បីផ្តល់ឱ្យអ្នកប្រើប្រាស់នូវទិន្នន័យដែលបានតម្រៀប។
អនុញ្ញាតឱ្យយើងយកឧទាហរណ៍មួយដើម្បីយល់ពីបច្ចេកទេសនេះ៖
- យើងត្រូវបានផ្តល់ជូនជាមួយនឹងអារេដែលមានធាតុ " 10, 40, 7, 3, 15 "។ ឥឡូវនេះ យើងត្រូវរៀបចំអារេនេះតាមលំដាប់ឡើងដោយប្រើបច្ចេកទេសតម្រៀប Bubble នៅក្នុង Python ។
- ជំហានដំបូងបំផុតគឺត្រូវរៀបចំអារេតាមលំដាប់ដែលបានផ្តល់ឱ្យ។
- នៅក្នុង "ការធ្វើឡើងវិញ 1" យើងកំពុងប្រៀបធៀបធាតុដំបូងនៃអារេជាមួយធាតុផ្សេងទៀតម្តងមួយៗ។
- ព្រួញក្រហមកំពុងពិពណ៌នាអំពីការប្រៀបធៀបធាតុដំបូងជាមួយធាតុផ្សេងទៀតនៃអារេមួយ។
- ប្រសិនបើអ្នកសម្គាល់ឃើញថា “10” តូចជាង “40” ដូច្នេះ វានៅតែដដែល កន្លែង ប៉ុន្តែធាតុបន្ទាប់ "7" តូចជាង "10" ។ ដូច្នេះវាត្រូវបានជំនួស ហើយមកដល់កន្លែងដំបូង។
- ដំណើរការខាងលើនឹងត្រូវបានអនុវត្តម្តងហើយម្តងទៀតដើម្បីតម្រៀបធាតុ។
-
- នៅក្នុង "ការធ្វើឡើងវិញ 2" ធាតុទីពីរត្រូវបានប្រៀបធៀបជាមួយធាតុផ្សេងទៀតនៃអារេមួយ។
- ប្រសិនបើធាតុដែលបានប្រៀបធៀបគឺតូច នោះវានឹង ជំនួសមកវិញ បើមិនដូច្នេះទេ វានឹងនៅដដែល។
-
- នៅក្នុង “ការបំប្លែង 3” ធាតុទីបីត្រូវបានប្រៀបធៀបជាមួយធាតុផ្សេងទៀតនៃអារេមួយ។
-
- នៅចុងក្រោយ “ ការធ្វើឡើងវិញទី 4 “ ធាតុចុងក្រោយទីពីរត្រូវបានប្រៀបធៀបជាមួយធាតុផ្សេងទៀតនៃអារេ។
- នៅក្នុងជំហាននេះ អារេត្រូវបានតម្រៀបតាមលំដាប់ឡើង។
កម្មវិធីសម្រាប់តម្រៀបពពុះ
``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ```
លទ្ធផល
ភាពស្មុគស្មាញពេលវេលានៃប្រភេទពពុះ
- ករណីអាក្រក់បំផុត៖ ភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុតសម្រាប់ការតម្រៀបពពុះគឺ O( n 2)។
- ករណីជាមធ្យម៖ ភាពស្មុគស្មាញពេលវេលាជាមធ្យមសម្រាប់ការតម្រៀបពពុះគឺ O( n 2។ 2>
- វាភាគច្រើនត្រូវបានប្រើប្រាស់ និងងាយស្រួលអនុវត្ត។
- យើងអាចប្តូរធាតុទិន្នន័យដោយមិនប្រើប្រាស់ទំហំផ្ទុករយៈពេលខ្លី។
- វាទាមទារតិចជាង space។
គុណវិបត្តិ
- វាមិនដំណើរការល្អទេ ខណៈពេលដែលកំពុងដោះស្រាយជាមួយនឹងធាតុទិន្នន័យធំមួយចំនួនធំ។
- វា ត្រូវការ n 2 ជំហានសម្រាប់ចំនួន "n" នៃធាតុទិន្នន័យនីមួយៗ ដើម្បីតម្រៀប។
- វាពិតជាមិនល្អសម្រាប់កម្មវិធីក្នុងពិភពពិតទេ។
ការបញ្ចូល តម្រៀប
ការតម្រៀបបញ្ចូលគឺជាបច្ចេកទេសតម្រៀបដ៏ងាយស្រួល និងសាមញ្ញ ដែលដំណើរការស្រដៀងនឹងការតម្រៀបសន្លឹកបៀ។ ការតម្រៀបការបញ្ចូលតម្រៀបធាតុដោយការប្រៀបធៀបធាតុនីមួយៗពីមួយទៅមួយ។ ធាតុត្រូវបានជ្រើសរើស និងប្តូរជាមួយធាតុផ្សេងទៀត ប្រសិនបើធាតុធំជាង ឬតូចជាងធាតុផ្សេងទៀត។
តោះយកឧទាហរណ៍មួយ
- យើងផ្តល់ជូនជាមួយ អារេដែលមានធាតុ “100, 50, 30, 40, 10”។
- ដំបូង យើងរៀបចំអារេ ហើយចាប់ផ្តើមប្រៀបធៀបវា។
- នៅក្នុងជំហានដំបូង “100” ត្រូវបានប្រៀបធៀបជាមួយធាតុទីពីរ “50”។ “ 50 ” ត្រូវបានប្តូរជាមួយ “ 100 ” ព្រោះវាធំជាង។
- នៅក្នុងជំហានទីពីរ ធាតុទីពីរ “100” ត្រូវបានប្រៀបធៀបជាមួយធាតុទីបី “30” ហើយត្រូវបានប្តូរ។
- ឥឡូវនេះ ប្រសិនបើអ្នកសម្គាល់ឃើញថា “30” មកដល់កន្លែងដំបូងព្រោះវាតូចជាង “50”។
- ការប្រៀបធៀបនឹងកើតឡើងរហូតដល់ធាតុចុងក្រោយនៃអារេ ហើយនៅចុងបញ្ចប់ យើងនឹងទទួលបាន ទិន្នន័យដែលបានតម្រៀប។
កម្មវិធីសម្រាប់តម្រៀបការបញ្ចូល
``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ```
លទ្ធផល
0ភាពស្មុគស្មាញនៃពេលវេលានៃការបញ្ចូលតម្រៀប
- ករណីអាក្រក់បំផុត៖ ភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុតសម្រាប់តម្រៀបការបញ្ចូលគឺ O( n 2។ ករណីល្អបំផុត៖ ភាពស្មុគស្មាញនៃពេលវេលាដ៏ល្អបំផុតសម្រាប់ការតម្រៀបការបញ្ចូលគឺ O(n)។
គុណសម្បត្តិ
- វាសាមញ្ញ និងងាយស្រួលអនុវត្ត។
- វាដំណើរការបានល្អ ខណៈពេលដែលដោះស្រាយជាមួយធាតុទិន្នន័យមួយចំនួនតូច។
- វាមិនត្រូវការកន្លែងបន្ថែមសម្រាប់ការអនុវត្តរបស់វាទេ។
គុណវិបត្តិ
- វាមិនមានប្រយោជន៍ក្នុងការតម្រៀបធាតុទិន្នន័យមួយចំនួនធំនោះទេ។
- បើប្រៀបធៀបទៅនឹងបច្ចេកទេសតម្រៀបផ្សេងទៀត វាមិនដំណើរការល្អទេ។
តម្រៀបបញ្ចូលគ្នា
វិធីសាស្ត្រតម្រៀបនេះប្រើវិធីសាស្ត្របែងចែក និងយកឈ្នះ ដើម្បីតម្រៀបធាតុតាមលំដាប់ជាក់លាក់មួយ។ ខណៈពេលដែលការតម្រៀបដោយមានជំនួយពីការតម្រៀបបញ្ចូលគ្នាធាតុត្រូវបានបែងចែកទៅជាពាក់កណ្តាល ហើយបន្ទាប់មកពួកវាត្រូវបានតម្រៀប បន្ទាប់ពីតម្រៀបផ្នែកទាំងអស់ហើយ ធាតុទាំងអស់ត្រូវបានបញ្ចូលគ្នាជាថ្មីម្តងទៀតដើម្បីបង្កើតលំដាប់ដ៏ល្អឥតខ្ចោះ។
សូមលើកឧទាហរណ៍មួយដើម្បីយល់ពីបច្ចេកទេសនេះ
- យើងត្រូវបានផ្តល់ជូន អារេ "7, 3, 40, 10, 20, 15, 6, 5" ។ អារេមានធាតុ 7 ។ ប្រសិនបើយើងបែងចែកវាទៅជាពាក់កណ្តាល ( 0 + 7 / 2 = 3 )។
- នៅជំហានទីពីរ អ្នកនឹងឃើញថាធាតុត្រូវបានបែងចែកជាពីរផ្នែក។ ធាតុនីមួយៗមាន 4 ធាតុនៅក្នុងវា។
- លើសពីនេះ ធាតុត្រូវបានបែងចែកម្តងទៀត និងមាន 2 ធាតុនីមួយៗ។
- ដំណើរការនេះនឹងបន្តរហូតដល់មានធាតុតែមួយនៅក្នុងអារេមួយ។ យោងទៅជំហានលេខ។ 4 នៅក្នុងរូបភាព។
- ឥឡូវនេះ យើងនឹងតម្រៀបធាតុ ហើយចាប់ផ្តើមភ្ជាប់ពួកវាដូចដែលយើងបានបែងចែក។
- នៅក្នុងជំហានលេខ។ 5 ប្រសិនបើអ្នកសម្គាល់ឃើញថា 7 ធំជាង 3 ដូច្នេះយើងនឹងផ្លាស់ប្តូរពួកវា ហើយចូលរួមវានៅជំហានបន្ទាប់ ហើយច្រាសមកវិញ។
- នៅចុងបញ្ចប់ អ្នកនឹងសម្គាល់ឃើញថា អារេរបស់យើងត្រូវបានតម្រៀបតាមលំដាប់ឡើង។
កម្មវិធីសម្រាប់តម្រៀបបញ្ចូលគ្នា
``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i len(L) and j len(R): if L[i] R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i len(L): arr[k] = L[i] i += 1 k += 1 while j len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ```
លទ្ធផល
ភាពស្មុគស្មាញនៃពេលវេលានៃការតម្រៀបបញ្ចូលគ្នា
- ករណីដ៏អាក្រក់បំផុត៖ ភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុតសម្រាប់ការតម្រៀបបញ្ចូលគ្នាគឺ O( n log( n )).
- ករណីជាមធ្យម៖ ភាពស្មុគស្មាញនៃពេលវេលាជាមធ្យមសម្រាប់ការតម្រៀបបញ្ចូលគ្នាគឺ O( n log( n )).
- ករណីល្អបំផុត៖ ភាពស្មុគស្មាញនៃពេលវេលាល្អបំផុតសម្រាប់ការតម្រៀបបញ្ចូលគ្នាគឺ O( n log( n )).
អត្ថប្រយោជន៍
- ទំហំឯកសារមិនសំខាន់សម្រាប់បច្ចេកទេសតម្រៀបនេះទេ។
- បច្ចេកទេសនេះគឺល្អសម្រាប់ទិន្នន័យដែលជាទូទៅត្រូវបានចូលប្រើតាមលំដាប់លំដោយ។ ឧទាហរណ៍ បញ្ជីដែលបានភ្ជាប់ ដ្រាយវ៍កាសែត។ បច្ចេកទេសតម្រៀប។
- វាមានប្រសិទ្ធភាពតិចជាងការប្រៀបធៀបផ្សេងទៀត។
តម្រៀបរហ័ស
ការតម្រៀបរហ័សម្តងទៀតប្រើវិធីសាស្ត្របែងចែក និងយកឈ្នះ ដើម្បីតម្រៀបធាតុនៃបញ្ជី ឬអារេមួយ។ វាកំណត់គោលដៅធាតុ pivot និងតម្រៀបធាតុយោងទៅតាមធាតុ pivot ដែលបានជ្រើសរើស។
ឧទាហរណ៍
- យើងត្រូវបានផ្តល់ឱ្យនូវអារេដែលមានធាតុ “ 1 ,8,3,9,4,5,7”។
- អនុញ្ញាតឱ្យយើងសន្មត់ថា “7” ជាធាតុសាកល្បង។
- ឥឡូវនេះយើងនឹងបែងចែកអារេតាមរបៀបដែល ផ្នែកខាងឆ្វេងមានធាតុដែលតូចជាងធាតុ pivot “7” ហើយផ្នែកខាងស្តាំមានធាតុដែលធំជាងធាតុ pivot “7”។
- ឥឡូវនេះយើងមានអារេពីរ “1,3,4,5 ” និង “ 8, 9 ”។
- ជាថ្មីម្តងទៀត យើងត្រូវបែងចែកអារេទាំងពីរដូចគ្នាទៅនឹងអ្វីដែលយើងបានធ្វើខាងលើ។ ភាពខុសប្លែកគ្នាតែមួយគត់គឺថាធាតុ pivot ត្រូវបានផ្លាស់ប្តូរ។
- យើងត្រូវបែងចែក array រហូតដល់យើងទទួលបានធាតុតែមួយនៅក្នុង array។
- នៅចុងបញ្ចប់ ប្រមូលធាតុ pivot ទាំងអស់នៅក្នុង a លំដាប់ពីឆ្វេងទៅស្តាំ ហើយអ្នកនឹងទទួលបានតម្រៀបអារេ។
កម្មវិធីសម្រាប់តម្រៀបរហ័ស
``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```
លទ្ធផល
ភាពស្មុគស្មាញពេលវេលានៃតម្រៀបរហ័ស
- ករណីអាក្រក់បំផុត៖ ភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុតសម្រាប់តម្រៀបរហ័សគឺ O( n 2)។
- ករណីជាមធ្យម៖ ភាពស្មុគស្មាញនៃពេលវេលាជាមធ្យមសម្រាប់ការតម្រៀបរហ័សគឺ O( n log( n ) )។
- ករណីល្អបំផុត៖ ភាពស្មុគស្មាញនៃពេលវេលាដ៏ល្អបំផុតសម្រាប់ការតម្រៀបរហ័សគឺ O( n log( n ))។
គុណសម្បត្តិ
- វាត្រូវបានគេស្គាល់ថាជាក្បួនដោះស្រាយការតម្រៀបដ៏ល្អបំផុតនៅក្នុង Python។
- វាមានប្រយោជន៍នៅពេលគ្រប់គ្រងទិន្នន័យយ៉ាងច្រើន។
- វាមិនតម្រូវឱ្យមានទំហំបន្ថែមទេ។
គុណវិបត្តិ
- ភាពស្មុគស្មាញករណីដ៏អាក្រក់បំផុតរបស់វាគឺស្រដៀងទៅនឹងភាពស្មុគស្មាញនៃប្រភេទពពុះ និង ការតម្រៀបបញ្ចូល។
- វិធីសាស្ត្រតម្រៀបនេះមិនមានប្រយោជន៍ទេ នៅពេលដែលយើងមានបញ្ជីតម្រៀបរួចហើយ។
តម្រៀបហេប
ការតម្រៀបហេបគឺជាកំណែកម្រិតខ្ពស់នៃមែកធាងស្វែងរកប្រព័ន្ធគោលពីរ . ក្នុងការតម្រៀបជាបណ្តុំ ធាតុដ៏អស្ចារ្យបំផុតនៃអារេមួយត្រូវបានដាក់នៅលើឫសនៃមែកធាងជានិច្ច ហើយបន្ទាប់មកធៀបនឹងឫសជាមួយថ្នាំងស្លឹក។
ឧទាហរណ៍៖
- យើងត្រូវបានផ្តល់ឱ្យនូវអារេមួយដែលមានធាតុ “ 40, 100, 30, 50, 10”។
- ក្នុង “ ជំហានទី 1 ” យើងបានបង្កើតដើមឈើមួយតាម វត្តមានរបស់ធាតុនៅក្នុងអារេ។
- នៅក្នុង “ ជំហានទី 2” យើងកំពុងបង្កើត heap អតិបរមា ពោលគឺដើម្បីរៀបចំ ធាតុនៅក្នុងលំដាប់ចុះ។ ធាតុដ៏អស្ចារ្យបំផុតនឹងស្ថិតនៅផ្នែកខាងលើ (ឫស) ហើយធាតុតូចបំផុតស្ថិតនៅខាងក្រោម (ថ្នាំងស្លឹក)។ អារេដែលបានផ្តល់ឱ្យក្លាយជា “100, 50, 30, 40, 10”។
- នៅក្នុង “ ជំហានទី 3 ” យើង កំពុងបង្កើត heap អប្បបរមា ដូច្នេះយើងអាចស្វែងរកធាតុអប្បបរមានៃអារេមួយ។ តាមរយៈការធ្វើដូចនេះ យើងទទួលបានធាតុអតិបរមា និងអប្បបរមា។
- នៅក្នុង “ ជំហានទី 4” ដោយអនុវត្តជំហានដូចគ្នា យើងទទួលបានអារេដែលបានតម្រៀប។
កម្មវិធីសម្រាប់តម្រៀប Heap
``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left n and arr[ larger_element ] arr[ left ]: larger_element = left if right n and arr[ larger_element ] arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```
លទ្ធផល
ភាពស្មុគស្មាញនៃពេលវេលានៃការតម្រៀប Heap
- ករណីអាក្រក់បំផុត៖ ភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុតសម្រាប់ការតម្រៀប Heap គឺ O( n log( n ))។
- ករណីជាមធ្យម៖ ភាពស្មុគស្មាញពេលវេលាជាមធ្យមសម្រាប់ការតម្រៀប Heap គឺ O( n log( n ))។
- ករណីល្អបំផុត៖ ភាពស្មុគស្មាញពេលវេលាល្អបំផុតសម្រាប់ការតម្រៀប Heap isO( n log( n )).
គុណសម្បត្តិ
- វាត្រូវបានគេប្រើភាគច្រើនដោយសារតែផលិតភាពរបស់វា។
- វាអាច ត្រូវបានអនុវត្តជាក្បួនដោះស្រាយនៅនឹងកន្លែង។
- វាមិនតម្រូវឱ្យមានទំហំផ្ទុកធំទេ។
គុណវិបត្តិ
- ត្រូវការទំហំសម្រាប់ តម្រៀបធាតុ។
- វាបង្កើតមែកធាងសម្រាប់តម្រៀបធាតុ។
ការប្រៀបធៀបរវាងបច្ចេកទេសតម្រៀប
វិធីសាស្ត្រតម្រៀប ភាពស្មុគស្មាញនៃពេលវេលាករណីល្អបំផុត ភាពស្មុគស្មាញនៃករណីជាមធ្យម ភាពស្មុគស្មាញនៃករណីដ៏អាក្រក់បំផុត ភាពស្មុគស្មាញនៃលំហ ស្ថេរភាព នៅក្នុង -