ការតម្រៀបបែបបញ្ចូលគ្នា
ក្បួនដោះស្រាយការតម្រៀបប្រកបដោយប្រសិទ្ធភាព ស្ថិរភាព និងផ្អែកលើការប្រៀបធៀប ដោយប្រើវិធីសាស្ត្របែងចែក និងយកឈ្នះ។
Visualization
Details
Analogy
គិតពីបណ្ណារក្សពីរនាក់ ដែលម្នាក់ៗមានសៀវភៅមួយគំនរដែលបានតម្រៀបតាមអក្ខរក្រម។ ដើម្បីបង្កើតគំនរធំមួយដែលបានតម្រៀប ពួកគេប្រៀបធៀបសៀវភៅខាងលើสุดของគំនរនីមួយៗ យកเล่มที่មកก่อน ហើយដាក់វាលើគំនរថ្មី។ ពួកគេធ្វើបែបនេះដដែលៗរហូតដល់សៀវភៅទាំងអស់ត្រូវបានបញ្ចូលគ្នាទៅជាគំនរថ្មីមួយដែលបានតម្រៀប។
Purpose
ដើម្បីតម្រៀបអារេដោយបែងចែកវាជាពីរផ្នែក តម្រៀបផ្នែកទាំងនោះឡើងវិញ ហើយបន្ទាប់មកបញ្ចូលផ្នែកដែលបានតម្រៀបរួចចូលគ្នា។
Use Cases
ល្អសម្រាប់ទិន្នន័យធំ ហើយពិសេសមានប្រយោជន៍នៅពេលភាពថេរត្រូវបានទាមទារ (ធាតុស្មើគ្នារក្សាលំដាប់សម្រាប់របស់ពួកគេ)។ ប្រើក្នុងកម្មវិធីដែលទាមទារដំណើរការធាតុយ៉ាងច្រើនប្រកបដោយប្រសិទ្ធភាព។
Algorithm Steps
function mergeSort(arr, left, right):
if left < right:
mid = (left + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
function merge(arr, left, mid, right):
create temp arrays L and R
copy data to L and R
merge L and R back into arr
Explanation
What's Happening?
អារេដំបូង។ ក្បួនដោះស្រាយនឹងបែងចែកវាឡើងវិញ។
Code Implementation
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(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
return arr