Quick Sort

Quick sort ဆိုတာကေတာ့ pivot နဲ႔ ယွဥ္ၿပီးေတာ့ အပိုင္း ၂ ပိုင္း ခြဲပါတယ္။ pivot ကေတာ့ ပံုမွန္ အားျဖင့္ array အခန္းထဲက အခန္းတစ္ခုကို random ခ်ၿပီးေတာ့ အဲဒီ အခန္းထဲက value ကို ယူပါတယ္။ အခု ကၽြန္ေတာ္တို႔ random မခ်ပဲနဲ႔ ပထမဆံုး အခန္းက value ကို ယူပါမယ္။

array = [4,7,8,1,6,3,2]

ဆိုၿပီး array ရွိပါတယ္။

ကၽြန္ေတာ္တို႔ pivot အေနနဲ႔ ေရွ႕ဆံုး အခန္းကိုပဲ ယူမယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = []
more = []
pivotList = []

less ဆိိုတာကေတာ့ pivot ထက္ ငယ္သည့္ value ေတြ အတြက္ပါ။ more ကေတာ့ pivot ထက္ႀကီးသည့္ value အတြက္ပါ။ pivotList ကေတာ့ pivot နဲ႔ တူသည့္ value ေတြ အတြက္ပါ။

ပထမဆံုး 4 ကို array ထဲမွာ ၾကည့္တယ္။ တူေနရင္ pivotList ထဲကို ထည့္မယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = []
more = []
pivotList = [4]

ၿပီးရင္ ေနာက္ တစ္ခန္းသြားမယ္။ 7 ကို pivot နဲ႔ စစ္တယ္။ ႀကီးေနသည့္အတြက္ေၾကာင့္ more ထဲကို ထည့္မယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = []
more = [7]
pivotList = [4]

ေနာက္တခန္း 8 ကလည္း ႀကီးေနသည့္ အတြက္ေၾကာင့္ more ထဲကို ထည့္မယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = []
more = [7,8]
pivotList = [4]

ေနာက္တစ္ခန္း ဆက္ၿပီးသြားေတာ့ 1 ထဲမွာျဖစ္တယ္။ 4 နဲ႔ ယွဥ္ေတာ့ ငယ္တယ္။ ဒါေၾကာင့္ less ထဲမွာ ထည့္တယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = [1]
more = [7,8]
pivotList = [4]

ေနာက္တစ္ခန္းမွာေတာ့ 6 ျဖစ္တယ္။ 4 နဲ႕ ယွဥ္တယ္။ ႀကီးသည့္ အတြက္ more ထဲမွာ ထည့္တယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = [1]
more = [7,8,6]
pivotList = [4]

ေနာက္တစ္ခန္းတိုးၿပီးေတာ့ စစ္ေတာ့ 3 က pivot ထက္ ငယ္ေတာ့ less ထဲမွာ ထည့္တယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = [1,3]
more = [7,8,6]
pivotList = [4]

ေနာက္တစ္ခန္း 2 ကလည္း pivot ထက္ငယ္ေတာ့ less မွာ သိမ္းတယ္။

array = [4,7,8,1,6,3,2]
pivot = 4
less = [1,3,2]
more = [7,8,6]
pivotList = [4]

အခု ဆိုရင္ ကၽြန္ေတာ္တို႔ array ၃ ခု ရၿပီ။ pivot နဲ႔ တူတာ။ ငယ္တာ။ ႀကီးတာ ဆိုၿပီးေတာ့ ရပါတယ္။ ငယ္သည့္ array ကိုလည္း recursive လုပ္ၿပီးေတာ့ ထပ္စီ ဖို႔လိုတယ္။ pivot value 1 ကို ထားၿပီးေတာ့ [1,3,2] ကို ခြဲၿပီး စီဖို႔လိုတယ္။ ေနာက္ဆံုး array အခန္း တစ္ခုပဲ က်န္သည့္ အထိ recusrive စစ္ဖို႔ လိုပါတယ္။

အဲလို စစ္လိုက္ရင္ ေနာက္ဆုံး

array = [4,7,8,1,6,3,2]
pivot = 4
less = [1,2,3]
more = [6,7,8]
pivotList = [4]

ဆိုၿပီး ျဖစ္သြားမယ္။ အဲဒီအခါ less+pivotList+more ဆိုတဲ့ array ၃ ခု ေပါင္းၿပီး ေတာ့ sorting ရလဒ္ကို ထုတ္ႏိုင္ပါၿပီ။

def quickSort(arr): less = [] pivotList = [] more = [] if len(arr) <= 1: return arr else: pivot = arr[0] for i in arr: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quickSort(less) more = quickSort(more) return less + pivotList + more qs = [4,7,8,1,6,3,2] print(quickSort(qs))

ဒါကေတာ့ ကၽြန္ေတာ္ အလြယ္သေဘာ ရွင္းလိုက္တာပါ။ ဒီ ပံုစံ အတိုင္း ဆိုရင္ေတာ့ memory ေနရာ အမ်ားႀကီး ယူပါတယ္။

သမာ႐ိုးက quick sort ပံုစံကေတာ့

array = [4,7,8,1,6,3,2]

ဆိုၿပီး ရွိမယ္။ ကၽြန္ေတာ္တို႔ pivot ယူရပါမယ္။ ၿပီးေတာ့ left , right ဆိုၿပီး index ေထာက္ဖို႔ ရွိပါမယ္။ left ကေတာ့ အစကေန စၿပီးေတာ့ right ကေတာ့ ေနာက္ဆံုး အခန္းကေတာ့ စပါမယ္။

pivot = 6
left = 0
right = 6

ၿပီးရင္ array[left] က pivot ထက္ ငယ္သလား စစ္မယ္။ ငယ္ရင္ ေနာက္ တစ္ခန္းတိုးေပါ့။ ႀကီးတာကို မေတြ႕မျခင္း ေရွ႕တိုးသြားပါမယ္။ right ကေတာ့ pivot ထက္ႀကီးသလား ဆိုၿပီး စစ္ပါမယ္။ ငယ္တာ မေတြ႕မျခင္း ေရွ႕ကို တိုးလာပါမယ္။ quick sort ရဲ႕ အဓိက အပိုင္းကေတာ့ ဘယ္ဘက္မွာ pivot ထက္ ငယ္တာ ျဖစ္ၿပီးေတာ့ ညာဘက္မွာေတာ့ pivot ထက္ႀကီးသည့္ value ေတြ ျဖစ္ရပါမယ္။

pivot = 6
left = 1 # 7 > 6
right = 6

အခု left အခန္းနဲ႔ right အခန္းကို လဲပါမယ္။ ၿပီးရင္ left ကို တစ္ခန္းတိုးၿပီးေတာ့ right ကိုေတာ့ တစ္ခန္း ထပ္ေလ်ာ့ပါမယ္။

array = [4,2,8,1,6,3,7]
pivot = 6
left = 2
right = 5

ၿပီးရင္ အစကေန ျပန္စစ္မယ္။ ဘယ္အခ်ိန္ထိလဲ ဆိုေတာ့ left က right ကို ေက်ာ္သြားသည့္ အထိပါ။

array = [4,2,8,1,6,3,7]
pivot = 6
left = 2 # 8 > 6
right = 5 # 3 < 6

အခု ရလာသည့္ value ကို ထပ္စစ္တယ္။ ၿပီးေတာ့ လဲတယ္။ left ကို တစ္ခန္းတိုး။ right ကို တစ္ခန္းေလ်ာ့။

array = [4,2,3,1,6,8,7]
pivot = 6
left = 3
right = 4

အစကေန ျပန္စစ္မယ္။

array = [4,2,3,1,6,8,7]
pivot = 6
left = 4
right = 4

အခု left နဲ႔ right တူသြားၿပီ။ ေနရာလဲေပမယ့္ အခုေနရာက ေနရာပဲ။ left ကို တစ္ခန္းတိုး။ right ကို တစ္ခန္းထပ္ေလ်ာ့။

array = [4,2,3,1,6,8,7]
pivot = 6
left = 5
right = 3

အခု left က right ထက္ႀကီးသြားၿပီ။ ဒါဆိုရင္ pivot ရဲ႕ ဘယ္ဘက္က pivot value ထက္ ငယ္တာေတြ ျဖစ္ၿပီးေတာ့ ညာဘက္ကေတာ့ သူ႔ထက္ႀကီးတာေတြပါ။

တစ္နည္းေျပာရင္ partion ၂ ခု ျဖစ္သြားၿပီ။ pivot ရဲ႕ left , right ေပၚမွာ မူတည္ၿပီး ၂ ခု ခြဲလိုက္ၿပီးေတာ့ ထပ္စီရပါမယ္။ အခန္း 0 ကိုေန right ထိက တစ္ခု။ left ကေန ၿပီးေတာ့ array အခန္း ကုန္ထိ က တစ္ခုပါ။

[4,2,3,1]
[8,7]

ကို ကၽြန္ေတာ္တို႔ အစက စီသလို ျပန္ၿပီး စီဖို႔ လိုပါတယ္။

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

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left <= right
            while array[left] < pivot && left < lenght of array
                left := left + 1
            while array[right] > pivot && right >= 0
                right := right - 1
            if left < right
                swap array[left] with array[right]
                left = left + 1
                right = right - 1
            else if left == right
                left = left + 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

ဒီ pseudo ေလးကို အေျခခံၿပီးေတာ့ python code ျပန္ေရးၾကည့္ရေအာင္။

from random import randint def quickSort(array): if len(array) <= 1: return array room = randint(0,len(array) - 1) pivot = array[room] left = 0 right = len(array) - 1 while left <= right: while left < len(array) and array[left] < pivot: left += 1 while right >= 0 and array[right] > pivot: right -= 1 if left < right: temp = array[left] array[left] = array[right] array[right] = temp left += 1 right -= 1 elif left == right: left += 1 leftSort = quickSort(array[0:right+1]) rightSort = quickSort(array[left:len(array)]) return leftSort+rightSort array = [4,2,3,1,6,8,7] print(quickSort(array))

from random import randint

ဆိုတာကေတာ့ random number ကို generate လုပ္ဖိ့ အတြက္ပါ။

room = randint(0,len(array) - 1)

ဆိုတာကေတာ့ အခန္း နံပတ္ 0 ကေန စၿပီးေတာ့ array အခန္း ေနာက္ဆံုးထိ random number ကို generate လုပ္မယ္လို႔ ဆိုတာပါ။

အခု ဆိုရင္ေတာ့ quick sort သေဘာတရားကို နားလည္ေလာက္ပါၿပီ။ အခု chapter မွာ array ထဲမွာ value ရွာျခင္း ႏွင့္ array sorting ပိုင္းကို ရွင္းျပသြားပါတယ္။ အခု အခန္းမွာ ပါသည့္ အေၾကာင္း အရာ တစ္ခု ျခင္း စီကို ေသခ်ာ လိုက္ဖတ္ၿပီးေတာ့ ကိုယ္တိုင္ ေရးႏိုင္မယ္ ေတြးႏိုင္မယ္ဆိုရင္ေတာ့ programming ရဲ႕ ျပႆနာေတြကို စဥ္းစားတတ္လာပါလိမ့္မယ္။

results matching ""

    No results matching ""