Insertion Sort

ေနာက္ထပ္ sort တနည္းကေတာ့ Insertion sort လို႔ ေခၚပါတယ္။ သူကေတာ့ selection sort နဲ႔ ဆင္တယ္။ sorted အပိုင္း နဲ႔ unsorted အပိုင္း ၂ ပိုင္း ခြဲၿပီးေတာ့ sort လုပ္ပါတယ္။

[5,6,4,7,12,9]

ဆိုရင္ ပထမဆံုး အခန္းကို sorted လုပ္ထားတယ္ဆိုၿပီး ယူလိုက္တယ္။ ဒါေၾကာင့္ စၿပီဆိုရင္ 5 ႏွင့္ 6 နဲ႔ကို ယွဥ္တယ္။ ငယ္သလား။ မငယ္ဘူး။ ဒါဆိုရင္ sorted ပိုင္းက 5,6 ျဖစ္သြားၿပီ။

[5,6,|4,7,12,9]

အခု ေနာက္တစ္ႀကိမ္မွာဆိုရင္ေတာ့ ဒုတိယ အခန္းက စမယ္။ 6 နဲ႔ 4 ယွဥ္တယ္။ 4 က 6 ထက္ငယ္တယ္။ ဒီေတာ့ 6 ႏွင့္ 4 ေနရာလဲတယ္။

ၿပီးရင္ 5 နဲ႔ 4 ထပ္ယွဥ္တယ္။ 4 က 5 ထပ္ငယ္တယ္။ ဒီေတာ့ ထပ္ေနရာလဲတယ္။

[4,5,6,|7,12,9]

sorted ပိုင္းက 4,5,6 ျဖစ္သြားၿပီးေတာ့ unsorted ကေတာ့ 7,12,9 ေပါ့။

6 ႏွင့္ 7 ယွဥ္တယ္။ ေနာက္က အခန္းက မႀကီးဘူး။ ဒီေတာ့ ဒီအတိုင္းထားတယ္။

[4,5,6,7,|12,9]

sorted က 4,5,6,7 ႏွင့္ unsorted ကေတာ့ 12,9 ပါ။

7 ႏွင့္ 12 ယွဥ္တယ္။ 7 က ငယ္ေနတယ္။ ဒီေတာ့ ေနရာ မေရႊ႕ဘူး။

[4,5,6,7,12,|9]

sorted က 4,5,6,7,12 ႏွင့္ unsorted ကေတာ့ 9 ပါ။

12 ႏွင့္ 9 ယွဥ္တယ္။ 9 က ငယ္ေနတယ္။ ဒီေတာ့ ေရႊ႕တယ္။ 7 ႏွင့္ 9 ယွဥ္တယ္။ 7 က ငယ္ေတာ့ ထပ္မေရႊ႕ေတာ့ဘူး။ ဒီေတာ့ အကုန္လံုး ၿပီးသြားၿပီးေတာ့ result က ေအာက္ကလို ထြက္လာပါၿပီ။

[4,5,6,7,9,12]

ဒီ Insertion sort မွာ အဓိက ကေတာ့ ေရွ႕အလံုး နဲ႔ ေနာက္ အလံုးကို ယွဥ္တယ္။ ငယ္ရင္ အဲဒီ အလံုးကို ကိုင္ထားၿပီးေတာ့ ေရွ႕က အလံုး နဲ႔ ငယ္လား စစ္ေနတာပါပဲ။

အခုဆိုရင္ေတာ့ Insertion Sort အေၾကာင္းကို သေဘာေပါက္ေလာက္ပါၿပီ။ ဒီေတာ့ code ေရးၾကည့္ရေအာင္။

ဒီ code က နည္းနည္း ရႈပ္သည့္ အတြက္ ကၽြန္ေတာ္တို႔ Pseudo code ေလး ေရးၾကည့္ရေအာင္။

for i = 1 to n-1
element = array[i]
j = i
while (j > 0 and array[j-1] > element) {
    array[j] = array[j-1]
    j = j -1
}
array[j] = element

ဒီ code မွာ

for i = 1 to n-1

ပထမဆံုး အခန္းက sorted လုပ္ထားၿပီးလို႔ သေဘာထားသည့္ အတြက္ ကၽြန္ေတာ္တို႔ေတြ အခန္း ကို 1 ကေန စၿပီး loop ပတ္ထားပါတယ္။

element = array[i]
j = i
while (j > 0 and array[j-1] > element) {

အခု loop ထဲမွာ ေရာက္ေနသည့္ position ေပၚမွာ မူတည္ၿပီးေတာ့ value ယူလိုက္တယ္။ ေနာက္ထပ္ loop တစ္ခု ကို i အစား ကၽြန္ေတာ္တို႔ေတြ variable j ထဲမွာ ထည့္ထားလိုက္တယ္။ ဘာလို႔လည္းဆိုေတာ့ j က ေနာက္က အခန္းနဲ႔ စစ္ၿပီးေတာ့ ေလွ်ာ့ေလွ်ာ့သြားဖို႔လိုတယ္။ ဘယ္ အထိ ေလ်ာ့ရမွာလဲ ဆိုေတာ့ ေနာက္က အခန္းက အခု အခန္းထက္ ႀကီးေနသ၍။ ေနာက္ၿပီးေတာ့ j က 0 ထက္ႀကီးေနသ၍ေပါ့။ 0 ျဖစ္သြားရင္ေတာ့ ထပ္ေလ်ာ့လို႔ မရေတာ့ဘူး။ ေရွ႕ဆံုး အခန္း ေရာက္ေနၿပီ။

array[j] = array[j-1]
j = j -1

ဒါကေတာ့ အခန္းေရႊ႕သည့္ သေဘာပါ။ ေနာက္ အခန္းက ႀကီးေနရင္ ေနာက္အခန္းကို အခု အခန္းထဲ ထည့္။ ၿပီးရင္ j ကို တခန္း ထပ္ေလ်ာ့။ ၿပီးရင္ သူ႔ရဲ႕ ေနာက္က value နဲ႔ လက္ရွိ element နဲ႔ ႀကီးလား ထပ္စစ္တယ္။ ႀကီးတယ္ဆိုရင္ ထပ္ေရႊ႕။

array[j] = element

loop ၿပီးသြားရင္ေတာ့ element ကို ေနာက္ဆံုး j ရွိသည့္ အခန္းမွာ ထည့္လိုက္ရံုပါပဲ။

code ကို နားလည္ၿပီဆိုရင္ python နဲ႔ ေရးၾကည့္ရေအာင္။

def insertionsort(array): for i in range(1,len(array)): element = array[i] j = i while j > 0 and array[j-1] > element : array[j] = array[j-1] j = j - 1 array[j] = element return array print(insertionsort([5,6,4,7,12,9]))

အခုဆိုရင္ေတာ့ ကၽြန္ေတာ္တို႔ insertion sort အေၾကာင္းကို သိေလာက္ပါၿပီ။

results matching ""

    No results matching ""