Merge Sort

အရင္ဆံုး merge sort အေၾကာင္းကို မေျပာခင္မွာ sorted array ၂ ခုကို merge နဲ႔ sort တစ္ခါတည္း လုပ္သည့္ အေၾကာင္း ရွင္းျပပါမယ္။

sorted_array1 = [4,5,9,18]
sorted_array2 = [8,10,11,15]

ဒီလို sorted array ၂ ခု ရွိပါတယ္။ merge လုပ္ဖို႔ အတြက္ array ၂ ခု ရဲ႕ ေရွ႕ဆံုး ၂ ခန္းကို ယွဥ္မယ္။ ငယ္သည့္ အခန္းကို ယူၿပီး sorted ထဲမွာ ထည့္မယ္။

အခု ေရွ႕ဆံုး အခန္း 4 နဲ႔ 8 မွာ ဆိုရင္ 4 ကို ယူမယ္။ ၿပီးရင္ 5 နဲ႔ 8 မွာ ဆိုရင္ 5 ကို ယူမယ္။ array အခန္း ၂ ခု လံုးကို ကုန္သြားေအာင္ ထိ စီသြားပါမယ္။

sorted_array1 = [5,9,18]
sorted_array2 = [8,10,11,15]
sorted = [4]
sorted_array1 = [9,18]
sorted_array2 = [8,10,11,15]
sorted = [4,5]
sorted_array1 = [9,18]
sorted_array2 = [10,11,15]
sorted = [4,5,8]
sorted_array1 = [18]
sorted_array2 = [10,11,15]
sorted = [4,5,8,9]
sorted_array1 = [18]
sorted_array2 = [11,15]
sorted = [4,5,8,9,10]
sorted_array1 = [18]
sorted_array2 = [15]
sorted = [4,5,8,9,10,11]
sorted_array1 = [18]
sorted_array2 = []
sorted = [4,5,8,9,10,11,15]
sorted_array1 = []
sorted_array2 = []
sorted = [4,5,8,9,10,11,15,188]

အခု ဆိုရင္ merge လုပ္ၿပီး sort လုပ္တာကို နားလည္ ေလာက္ပါၿပီ။ အခု merge sort အေၾကာင္း ထပ္ရွင္းပါမယ္။

array = [5,4,18,9,8,10,15,11]

ဒီလို array ကို sort လုပ္ဖို႔အတြက္ ထက္ဝက္ ပိုင္းသြားပါမယ္။

[5,4,18,9]
[8,10,15,11]
[5,4]
[18,9]

[8,10]
[15,11]
[5]
[4]

[18]
[9]

[8]
[10]

[15]
[11]

အခု လို အပိုင္းေလးေတြ ပိုင္းၿပီးေတာ့ ၁ ခန္းထဲ က်န္သည့္ အထိ ပိုင္းသြားပါတယ္။ ၿပီးေတာ့ merge လုပ္သည့္ အခါမွာ တစ္ခါတည္း sort လုပ္ပါမယ္။

[4,5]

[9,18]

[8,10]

[11,15]
[4,5,9,18]

[8,10,11,15]
[4,5,8,9,10,11,15,18]

ဒါဆိုရင္ေတာ့ merge sort အေၾကာင္း နားလည္သြားၿပီ။

ကၽြန္ေတာ္တို႔ ဒီ code ေလးကို recursive သံုးၿပီး ေရးသားပါမယ္။ အဓိကေတာ့ array ၂ ခုကို ျပန္ၿပီး merge ရသည့္ အပိုင္းပါ။

def merge(left, right): result = [] left_idx, right_idx = 0, 0 while left_idx < len(left) and right_idx < len(right): if left[left_idx] <= right[right_idx]: result.append(left[left_idx]) left_idx += 1 else: result.append(right[right_idx]) right_idx += 1 if left_idx < len(left): result.extend(left[left_idx:]) if right_idx < len(right): result.extend(right[right_idx:]) return result def mergesort(w): if len(w)<2: return w else: mid=len(w)//2 return merge(mergesort(w[:mid]), mergesort(w[mid:])) print(mergesort([4,5,1,3,9,7,2,10]))

အျခား code ေတြကိုေတာ့ နားလည္ ပါလိမ့္မယ္။ ထူးျခားတာကေတာ့ ေအာက္က code ေလးပါ။

result.extend(left[left_idx:])

extend ကေတာ့ လက္ရွိ array ထဲကို ေနာက္ထပ္ array က လာၿပီးေတာ့ ထည့္သည့္ သေဘာပါ။

array_1 = [12,34,44] array_2 = [6,8] array_1.extend(array_2) print(array_1)

ေအာက္က code ေလးကို အနည္းငယ္ ထပ္ရွင္းျပပါအံုးမယ္။

if left_idx < len(left):
    result.extend(left[left_idx:])
if right_idx < len(right):
    result.extend(right[right_idx:])

ကၽြန္ေတာ္တို႔ array ကို merge လုပ္သည့္ အခါမွာ အငယ္ဆံုးေတြကို အရင္ merge လုပ္သြားသည့္ အတြက္ အခ်ဳိ့ အခန္းေတြ အကုန္ မၿပီးသြားဘူးေပါ့။

ဥပမာ

left = [2,4,5,8] #left_idx =  4
right = [6,9,10] #right_idx = 1
result = [2,4,5,6,8] #9,10 not merge yet

အခု code မွာ ဆိုရင္ left က ကုန္သြားၿပီ။ right က [9,10] က်န္ေသးတယ္။ အဲဒီေတာ့ extend ကို အသံုးျပဳၿပီး result ထဲကို merge လုပ္လိုက္တာပါ။

အခု ဆိုရင္ေတာ့ ကၽြန္ေတာ္တို႔ merge sort ကို ေရးလို႔ ရသြားပါၿပီ။ code ကို နားလည္ေအာင္ ကိုယ္တိုင္ တဆင့္ျခင္းစီ trace လိုက္ဖို႔ လိုပါတယ္။

results matching ""

    No results matching ""