The Algorithms

Intro

က်ေနာ္ကေတာ့ ဘယ္လိုေလ့လာလဲဆိုရင္ ကိုသက္ခိုင္တို႕ ၊ ကိုထက္ေဝယံစိုးတို႕ေျပာေျပာေနတဲ့ CS50 ဆိုတဲ့ Course ကို ၾကည့္လိုက္ပါတယ္၊ တကယ္လဲေကာင္းပါတယ္။ အဲဒီ Course ကိုၾကည့္လိုက္ရင္ Programming ကိုစိတ္ပ်က္တဲ့သူေတာင္ မပ်က္ေလာက္ေတာ့ဘူးထင္တာပဲ။ က်ေနာ္ကေတာ့ ေတာ္ေတာ္ၾကိုက္တယ္ ၊ ရွင္းျပသြားတာ ေတာ္ေတာ္ကိုေကာင္းတယ္။ ေကာင္းဆို Harvard မွာသင္တာလဲျဖစ္တာကိုး၊ ကံေကာင္းတာကေတာ့ Open ျဖစ္တဲ့အတြက္ Online ကေနေလ့လာလို႕ရတာျဖစ္ပါတယ္။ က်ေနာ္ေရးထားတာကေတာ့ Note သက္သက္ပါ။ က်ေနာ္မေမ့ခ်င္ဘူး အဲဒါေၾကာင့္ေရးထားတာပါ။ တကယ္နားလည္ဖို႕ကေတာ့ http://cs50.tv မွာ Course အစအဆံုးအားလံုးရွိပါတယ္။

ကိုသက္ခိုင္ေရးထားတဲ့ Data Structures & Algorithms ကိုဘယ္လိုေလ့လာမလဲဆိုတာေလးကလဲ အေထာက္ကူေပးပါလိမ့္မယ္။ [ kept in programming-collection ]

ဘာလို႕ေလ့လာလဲဆိုရင္ေတာ့ရွင္းတယ္၊ Problem solving ဗ် ၊ လိုကိုလိုတယ္ ၊ အခ်ိန္ေပးရတာအင္မတန္တန္တယ္။ ဒါပဲ ။ ဒါက notes တစ္ခုပါပဲ ၊ က်ေနာ္ေမ့မသြားခ်င္လို႕ မွတ္ထားတဲ့သေဘာပါပဲ အစံုအလင္ေတာ့ မဟုတ္ပါဘူး။

What is Algorithm?

Algorithm ဆိုတာကေတာ့ instructions ေတြပါပဲ၊ ဘာျပီးရင္ဘာလုပ္မယ္ဆိုတဲ့ instructions ေတြေပါ့ ၊ Problem တစ္ခု ၾကံုလာျပီဆိုရင္ အဆင့္ဆင့္ဘယ္လိုေျဖရွင္းမယ္ဆိုတဲ့ ၾကိဳတင္ predict လုပ္ထားတဲ့ instructions ေတြဆိုလဲမမွားပါဘူး။ Problem solving ဆိုတဲ့ေနရာမွာ ထိေရာက္တဲ့ Solution ျဖစ္ဖို႕လိုပါတယ္ ၊ ဒါေၾကာင့္ programming ေလ့လာတဲ့သူပဲျဖစ္ျဖစ္ ၊ Hacking ေလ့လာတဲ့သူပဲျဖစ္ျဖစ္ သိထားသင့္တဲ့ အရာတစ္ခုျဖစ္တယ္။

Searching Algorithms

Linear Search

Linear Search ဆိုတာကေတာ့ ပံုေလးမွာပါတဲ့အတိုင္းပဲ၊ က်ေနာ္တို႕မွာ Number Sequence တစ္ခုရွိတယ္ဆိုပါေတာ့။ Array ထဲမွာထည့္ထားမယ္။ Sequence က ေတာ့ Sort လုပ္ထားတာေတြ႕ရမယ္။ ဒီထဲမွာ 33 ဆိုတဲ့ number ကို က်ေနာ္တို႕ကလိုခ်င္တာျဖစ္တယ္။ ဒါကို တစ္ခုခ်င္း 33 ဟုတ္မဟုတ္စစ္တယ္။ 33 ကိုေတြ႕တဲ့အထိ ရွာတာကိုေတြ႕ရမယ္။ ဒီေတာ့ ကိုသက္ခိုင္ရဲ႕အဆိုအရ pseudo code ေလး တစ္ခုအရင္ဆံုးရွာၾကည့္ျပီးေလ့လာလို႕ရတယ္။ ကိုယ့္ဘာကိုလဲ မရွာခင္စဥ္းစားလို႕ရတယ္။

pseudo code

int linearsearch(number array, size of array, our number){
for (int i = 0; i < size of array; i++){
if (i in array == our number)
return true;
}
return false;
}

Binary Search

CS50 ထဲမွာ စလာလာခ်င္းပဲ Phone book နဲ႕ ဥပမာျပသြားတာအရမ္းေကာင္းပါတယ္။ Binary Search က Number Sequence တစ္ခုရွိတယ္ဆိုပါေတာ့ တစ္ဝက္ဝက္လိုက္မယ္။ ေရာက္ေနတဲ့ ေနရာထက္ၾကီးတယ္ဆို ၾကီးတဲ့ဘက္ျခမ္းကို တစ္ဝက္ထပ္ပိုင္းမယ္၊ တကယ္လို႕ငယ္တယ္ဆိုရင္ ငယ္တဲ့ဘက္ျခမ္းကိုတစ္ဝက္ထပ္ပိုင္းမယ္။ ဒီေတာ့ တစ္ျခမ္းကို အလိုလုိေနရင္းရွာစရာမလိုေတာ့ဘူးေပါ့။ linear search နဲ႕ယွဥ္ရင္ binary search က အဆင့္ပိုနည္းသြားတာကိုေတြ႕ရမယ္။ ဒါေပမဲ့ sort လုပ္ထားမွပဲအဆင္ေျပမွာျဖစ္တယ္။

pseudo code

int binarysearch(number array, 0 as left, array size -1 as right, our number)
{
if (right >= left)
{
int mid = left + (right – left)/2;
if (arr[mid] == our number) return mid;
if (arr[mid] > ournumber)
return binarysearch(number array, 0 as left, mid-1, our number);
else
return binarysearch(number array, mid+1, array size -1 as right, our number);
}
return not found;
}

Other searching algorithms

ဒီ၂ခုကိုၾကည့္ျခင္းအားျဖင့္ က်ေနာ္တို႕သိလိုက္ရတာက Binary Search က ပိုျပီးျမန္တယ္ဆိုတာကို သိနိုင္တယ္။ ဒါေပမဲ့ Linear Search နဲ႕ Binary Search မွာ Linear Search က Binary Search က Sort လုပ္ထားဖို႕လိုေနတာကိုလည္းေတြ႕ရမွာျဖစ္တယ္။ ဒါေၾကာင့္ Sorting alogrithms ေတြလိုအပ္လာတယ္။

Sorting Algorithms

Insertion Sort

Array ထဲကေန ဒုတိယ number ကိုယူလိုက္မယ္၊ ျပီးရင္ ပထမ number နဲ႕ တူသလား ငယ္သလား? ငယ္တယ္ဆိုရင္ ေနရာလဲလိုက္မယ္။ ၾကီးရင္ေတာ့ သူ႕ေနရာသူျပန္ထားမယ္။ ဒီလုိပဲ တတိယ number ကိုလဲ ဒုတိယေနရာနဲ႕စစ္တယ္ ၊ ျပီးရင္ တတိယေနရာနဲ႕စစ္တယ္၊ ငယ္ေနရင္ေတာ့ သူနဲ႕ေနရာလဲလိုက္တယ္။ ဒီလိုနည္းနဲ႕ sorting စီသြားတာျဖစ္တယ္။

Pseudo code

for j <- 2 to length[A]
do key <- A[j]
Insert A[j] into the sorted sequence A[1 . . j – 1].
i <- j – 1
while i > 0 and A[i] > key
do A[i + 1] <- A[i]
i <- i – 1
A[i + 1] <- key

Selection Sort

Selection sort ကေတာ့ ပထမဆံုးတစ္ခုကစျပီးေတာ့ အနည္းဆံုး value အျဖစ္သတ္မွတ္လိုက္တယ္။ ျပီးရင္ က်န္တဲ့ဟာေတြမွာ သူ႕ထက္ငယ္တာေတြ႕ရင္ အဲဒါကို အငယ္ဆံုးအျဖစ္နဲ႕ ျပန္ယူတယ္၊ အဲ့လိုလုပ္လာရင္းကုန္သြားျပီးဆိုရင္ အငယ္ဆံုးဟာကို ခုေနရာနဲ႕ swap လိုက္တယ္။ ျပီးရင္ ဒုတိယတစ္ခုကို အငယ္ဆံုး value အျဖစ္ျပန္ယူတယ္ ၊ ျပီးရင္ ထံုးစံအတိုင္း အငယ္ဆံုးဟာကိုျပန္ရွာျပီးေနရာျပန္လဲတယ္။

Pseudo code

put 1 into j — j is used to step through the B list
repeat until j > N
put minimum(A[j]…A[N],N-j+1) into min
swap A[j], A[min]
add 1 to j
end repeat
return A
end selectionSort

Bubble Sort

Bubble Sort ကေတာ့ ၂ လံုးခ်င္းစီတိုက္စစ္သြားတာျဖစ္ပါတယ္၊ ပထမဆံုးဟာနဲ႕ ဒုတိယဟာနဲ႕တိုက္စစ္မယ္၊ ဒုတိယဟာက ငယ္ေနရင္ swap မယ္၊ ျပီးရင္ ဒုတိယနဲ႕ တတိယကိုတိုက္စစ္တယ္၊ ငယ္ေနရင္ swap လိုက္တယ္၊ ဒီေတာ့ အၾကီးဆံုးတစ္ခုကေတာ့ ေနာက္ဆံုးမွာ ေသခ်ာေပါက္ေရာက္သြားမယ္၊ ျပီးရင္ အစကေန အစံုလိုက္ထပ္တိုက္စစ္တယ္ ၊ ေနာက္ထပ္အၾကီးဆံုးတစ္လံုး ေနာက္မွာထပ္ေရာက္သြားတယ္၊ ဒီလိုနည္းနဲ႕လုပ္လိုက္ရင္ေနာက္ဆံုး sort ျဖစ္သြားမယ္။

pseudo code

bubblesort (A, N)

{ repeat the following steps until the list is sorted
put 1 into i
repeat while i < N
if A[i] > A[i+1]
then swap A[i], A[i+1]
end if
add 1 to i
end repeat
end repeat
}     end bubblesort

Merge Sort

Merger Sort ကေတာ့ Binary Search လိုပဲ ၂ ပိုင္းခြဲလိုက္တယ္၊ ၂ ခုပဲက်န္တဲ့ထိခြဲလိုက္တာျဖစ္ပါတယ္။ ျပီးရင္ အဲ့ ၂ ခုကိုနွိုင္းယွဥ္ျပီး swap လိုက္တယ္၊ ျပီးရင္ အဲ့၂ခုနဲ႕ အျခား ၂ခုကို ျပန္ နွုိင္းယွဥ္ျပီး swap တယ္၊ ေနာက္ဆံုး ၂ ပိုင္းပဲက်န္ျပီး swap တယ္။

pseudo code

MergeSort (Array(First..Last))
Begin
If Array contains only one element Then
Return Array
Else
Middle= ((Last + First)/2) rounded down to the nearest integer
LeftHalfArray = MergeSort(Array(First..Middle))
RightHalfArray = MergeSort(Array(Middle+1..Last))
ResultArray = Merge(LeftHalfArray, RightHalfArray)
Return ResultArray
EndIf
End MergeSort

other sorting algorithms

အားသာခ်က္ အားနည္းခ်က္ေတြေတာ့ရွိပါတယ္၊ ဘယ္ဟာအျမန္ဆံုးလဲ ၊ ဘယ္ဟာအၾကာဆံုးလဲစတာေတြကိုေတာ့ ေအာက္က Link မွာ ႏွိုင္းယွဥ္ျပထားတာေတြ႕ရပါမယ္

Action in sorting 

References

https://github.com/TheAlgorithms/Python

https://www.ee.ryerson.ca/~courses/coe428/

https://commons.wikimedia.org/wiki/