Shell Sort

ကၽြန္ေတာ္တို႔ insertion sort မွာ ဂဏန္းေတြကို အစ ကေန စတယ္။ ၿပီးေတာ့ ေနာက္တစ္ခု နဲ႔ တိုက္သြားတယ္။ အကယ္၍ အငယ္ဆံုးက ေနာက္ဆုံးမွာ ရွိတယ္ ဆိုရင္ ေနာက္ဆံုး ထိ ေရာက္ၿပီးမွ ေနာက္ဆံုးမွာ ရွိသည့္ အငယ္ဆံုး ဂဏန္းကလည္း ေရွ႕ ဂဏန္းထက္ ငယ္ထား ဆိုၿပီး ေရွ႕ဆံုးထိ ေရာက္ေအာင္ ျပန္သြားရတယ္။

အခု shell sort ကေတာ့ insertion sort နဲ႔ တူပါတယ္။ သို႔ေပမယ့္ gap ေလးေတြ ထည့္ထားပါတယ္။ gap ေပၚမွာ မူတည္ၿပီးေတာ့ အခန္းကို ယွဥ္ၿပီး ေရႊ႕ပါတယ္။

code အပိုင္းကို မသြားခင္မွာ အရင္ဆံုး shell sort ဆိုတာ ဘာလဲ ၾကည့္ရေအာင္။

ကၽြန္ေတာ္တို႔ မွာ ေအာက္ေဖာ္ျပပါ အတိုင္း array အခန္း ရွိပါတယ္။

[5,6,4,7,12,9,1,8,32,49]

စုစု ေပါင္း အခန္း ၁၀ ခု ေပါ့။

gap ကို အရင္ ရွာဖို႔ လိုတယ္။

gap = len(array)//2

// ျဖစ္သည့္ အတြက္ေၾကာင့္ 3.5 ျဖစ္ခဲ့ရင္ 3 ကို ပဲ ယူမယ္လို႔ ဆိုထား ပါတယ္။

အခု က အခန္း ၁၀ ခန္း ရွိသည့္ အတြက္ေၾကာင့္

gap = 5

shell sort မွာ gap ကို gap နဲ႔ တဝက္ပိုင္းၿပီးေတာ့ ေနာက္ဆံုး 1 ထိ ေရာက္ေအာင္ သြားပါတယ္။

ဒီေတာ့

gap = 5
gap = 5//2 = 2
gap = 2//2 = 1

အခု ပထမဆံုး gap = 5 ကေန စရေအာင္။ အခန္း 1 နဲ႔ gap ကို စၿပီး ယွဥ္ပါတယ္။

gap = 5
[5<-,6,4,7,12,9<-,1,8,32,49]

5 ႏွင့္ 9 ကို ယွဥ္တယ္။ 9 က မငယ္သည့္ အတြက္ ဒီ အတိုင္းထားမယ္။ ေနာက္ တခန္းကို ထပ္ ေရႊ႕မယ္။

[5,6<-,4,7,12,9,1<-,8,32,49]

6 ႏွင့္ 1 ကို ယွဥ္တယ္။ 1 က ငယ္သည့္ အတြက္ လဲ မယ္။ insertion sort လိုပဲ ငယ္တာကို ထပ္ၿပီးေတာ့ ေနာက္မွာ သူ႔ထပ္ ငယ္တာ ရွိလား ဆိုၿပီး စစ္တယ္။ insertion sort နဲ႔ ကြာတာက ေနာက္က တစ္ခန္းကို မဟုတ္ပဲ gap value အကြာနဲ႔ စစ္တယ္။ အခု လက္ရွိ အခန္းက 1 - gap ဆိုေတာ့ 1-5 = -4 ေပါ့။ 0 ထက္ ငယ္ေနသည့္ အတြက္ ထပ္ၿပီး မစစ္ေတာ့ဘူး။ အကယ္၍ 0 သို႔မဟုတ္ 0 ထက္ ႀကီးေနရင္ အဲဒီ အခန္းနဲ႔ 1 ကို ထပ္ၿပီး စစ္ဖို႔ လိုပါတယ္။ အဲဒီေတာ့

[5,1,4,7,12,9,6,8,32,49]

အခု ေနာက္ထပ္ တခန္းကို ထပ္တိုးမယ္။

[5,1,4<-,7,12,9,6,8<-,32,49]

4 ႏွင့္ 8 ကို ယွဥ္တယ္။ 8 က ႀကီးေနေတာ့ ဒီ အတိုင္းထား။ ေနာက္ တစ္ခန္းကို ထပ္တိုး။

[5,1,4,7<-,12,9,6,8,32<-,49]

7 နဲ႔ 32 လည္း လဲ ဖို႔ မလိုဘူး။

[5,1,4,7,12<-,9,6,8,32,49<-]

12 နဲ႔ 49 လည္း လဲ ဖို႔ မလိုဘူး။ အခု ေရွ႕ဆံုး အခန္းကေန ေရႊ႕တာ gap ေနရာ ေရာက္ပါၿပီ။ ဒါေၾကာင့္ ထပ္ မေရႊ႕ေတာ့ပါဘူး။ အခု gap တန္ဖိုး ကို ျပန္ေျပာင္းပါမယ္။

gap = gap//2 == 5//2 = 2

အခု gap တန္ဖိုးက 2 ျဖစ္သည့္ အတြက္ အခန္း 0 နဲ႔ အခန္း 2 ကို ယွဥ္တာကေန စမယ္။

[5<-,1,4<-,7,12,9,6,8,32,49]

5 ႏွင့္ 4 ကို ယွဥ္တယ္။ ငယ္သည့္ အတြက္ေနရာလဲတယ္။ 0 - 2 က 0 ထက္ ငယ္သြားသည့္ အတြက္ ဆက္ၿပီး မယွဥ္ေတာ့ဘူး။ ေနာက္ အခန္း ထပ္သြားတယ္။

[4,1<-,5,7<-,12,9,6,8,32,49]

1 ႏွင့္ 7 က လဲ ဖို႔ မလိုဘူး။ ေနာက္ အခန္း ထပ္သြားတယ္။

[4,1,5<-,7,12<-,9,6,8,32,49]

5 နဲ႔ 12 လဲဖို႔ မလိုဘူး။

[4,1,5,7<-,12,9<-,6,8,32,49]

7 နဲ႔ 9 လဲ ဖို႔ မလိုဘူး။

[4,1,5,7,12<-,9,6<-,8,32,49]

12 နဲ႔ 6 မွာ 12 က ႀကီးေတာ့ လဲမယ္။ ၿပီးေတာ့ လက္ရွိ ေရာက္ေနသည့္ အခန္းနံပတ္ 4 - 2 (gap) = 2 ဆိုေတာ့ အခန္း 2 က value နဲ႔ ထပ္ယွဥ္တယ္။ 4 နဲ႔ 6 ဆိုေတာ့ လဲ စရာမလိုဘူး။

[4,1,5,7,6,9<-,12,8<-,32,49]

9 ႏွင့္ 8 ကို ယွဥ္တယ္။ အခန္းလဲ တယ္။ ၿပီးေတာ့ 7 နဲ႔ 8 ကို ထပ္ယွဥ္တယ္။ 7 က ငယ္ေနေတာ့ မလဲဘူး။

[4,1,5,7,6,8,12<-,9,32<-,49]

12 ႏွင့္ 32 လဲ ဖို႔ မလိုဘူး။

[4,1,5,7,6,8,12,9<-,32,49<-]

9 ႏွင့္ 49 လဲဖို႔ မလိုဘူး။

အခု gap က ေရႊ႕ဖို႔ အခန္း မရွိသည့္ အတြက္ေၾကာင့္ gap ကို ထပ္ၿပီးေတာ့ 2 နဲ႔ စားမယ္။

gap = gap//2 = 2//2 = 1

အခု gap က တစ္ခုပဲ ျဖစ္သြားသည့္ အတြက္ ေၾကာင့္ ၁ ခန္း စီပဲ လဲ ေတာ့မယ္။

[4<-,1<-,5,7,6,8,12,9,32,49]

4 နဲ႔ 1 လဲမယ္။

[1,4<-,5<-,7,6,8,12,9,32,49]

4 ႏွင့္ 7 ကို မလဲဘူး။

[1,4,5<-,7<-,6,8,12,9,32,49]

5 ႏွင့္ 7 ကို မလဲဘူး။

[1,4,5,7<-,6<-,8,12,9,32,49]

7 နဲ႔ 6 လဲတယ္။ ၿပီးေတာ့ 5 နဲ႔ 6 ထပ္ ယွဥ္တယ္။ မငယ္ေတာ့ မလဲေတာ့ဘူး။

[1,4,5,6,7<-,8<-,12,9,32,49]

7 ႏွင့္ 8 ယွဥ္တယ္။ 7 က ငယ္ေတာ့ မလဲဘူး။

[1,4,5,6,7,8<-,12<-,9,32,49]

8 နဲ႔ 12 မလဲဘူး။

[1,4,5,6,7,8,12<-,9<-,32,49]

12 နဲ႔ 9 လဲမယ္။ ၿပီးေတာ့ 8 နဲ႔ 9 ယွဥ္တယ္။ 8 က ငယ္ေတာ့ မလဲဘူး။

[1,4,5,6,7,8,9,12<-,32<-,49]

12 နဲ႔ 32 ယွဥ္တယ္။ မလဲဘူး။

[1,4,5,6,7,8,9,12,32<-,49<-]

32 ႏွင့္ 49 ယွဥ္တယ္။ မလဲဘူး။

gap က ဆက္ၿပီးသြားလို႔ မရေတာ့ဘူး။ 2 နဲ႔ ျပန္စားေတာ့ 0 ရေတာ့ loop မလုပ္ေတာ့ပဲ လက္ရွိ ရွိၿပိးသား array ကို sorting စီၿပီးသားလို႔ သတ္မွတ္လိုက္ပါၿပီ။

အခု

[1,4,5,6,7,8,9,12,32,49]

ဆိုၿပီး sorted array ထြက္လာပါၿပီ။

အခု ကၽြန္ေတာ္တို႔ python code ေလးကို ၾကည့္ရေအာင္။

def shellSort(array): gap = len(array) // 2 # loop over the gaps while gap > 0: # insertion sort for i in range(gap, len(array)): val = array[i] j = i while j >= gap and array[j - gap] > val: array[j] = array[j - gap] j -= gap array[j] = val gap //= 2 return array print(shellSort([5,6,4,7,12,9,1,8,32,49]))

code ကေတာ့ insertion sort နဲ႔ တူတူပါပဲ။ ကြာျခားခ်က္ကေတာ့

while gap > 0:

ဆိုၿပီး gap ေပၚမွာ မူတည္ၿပီး loop ပတ္ထားပါတယ္။ insertion sort တုန္းကေတာ့ - 1 ကို သံုးထားၿပီးေတာ့ အခု shell sort မွာေတာ့ - gap ကို အသံုးျပဳထားပါတယ္။

code တစ္ဆင့္ျခင္း ကိုေတာ့ ကိုယ္တိုင္ ျပန္ၿပီးေတာ့ trace လိုက္ၾကည့္ပါ။

results matching ""

    No results matching ""