WLC_Programming Knowledge

မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမမ်ား အားလံုးပဲ မဂၤလာပါဗ်ာ။ က်ေနာ္တို႔ ဒီေန႔ Gnome Sort ဆိုတဲ့ Sorting Algorithm ေလးတစ္ခုအေၾကာင္းကို ေလ့လာၾကည့္ပါမယ္။ Gnome Sort ကို Stupid Sort လို႔လည္း ေခၚၾကပါေသးတယ္ဗ်။ ဒီ Algorithm ကေတာ့ ဥယ်ာဥ္တစ္ခုအတြင္းမွာ ပန္းအိုးေတြကို အစီအစဥ္တက် စီယူတဲ့အေပၚ အေျခခံထားပါတယ္။

int i = 1; while (i < array.Length;) { if (array [i - 1] <= array[i]) { ++i; } else { swap(array [i], array [i-1]); --i; if (i == 0) i = 1; } } အလုပ္ လုပ္သြားတဲ့ ပံုကေတာ့ Insertion Sort နဲ႔ Bubble Sort ကို ေပါင္းစပ္ အသံုးျပဳထားတာနဲ႔ အလားသ႑န္တူပါတယ္။ ဒီေကာင္က Sorting စီရာမွာ ကပ္လွ်က္ Element ႏွစ္လံုးကို ႏိႈင္းယွဥ္ပါတယ္။ ႏိႈင္းယွဥ္ခံ Element ႏွစ္ခုအတြင္း ျခားနားခ်က္ရွိသြားၿပီး တစ္နည္းအားျဖင့္ else(Condition) မွန္သြားၿပီ ဆိုရင္ေတာ့ Element ႏွစ္ခုကို ေနရာခ်ိန္းယူပါတယ္။ ေနာက္ၿပီး loop ကို else(Condition) မွားသည္အထိ backwards(i--) ျပန္သြားၿပီး left order Element ေတြနဲ႔ ျပန္ႏိႈင္းယွဥ္ ၾကည့္ပါတယ္ဗ်။ If(Condition) ျပန္မွန္တဲ့အခ်ိန္ေရာက္ရင္ေတာ့ Right order Element ေတြနဲ႔ တစ္ခါျပန္ႏႈိင္းယွဥ္ၿပီး Algorithm ကို ဆက္အလုပ္ လုပ္ပါတယ္ဗ်။ ဒီသေဘာတရားအတိုင္း Sorted List မျဖစ္မျခင္း Algorithm ကို ထပ္ခါတလဲလဲ အလုပ္ လုပ္ေစမွာ ျဖစ္ပါတယ္။ ငယ္စဥ္ႀကီးလိုက္အတြက္ Algorithm အလုပ္ လုပ္သြားပံုကို က်ေနာ္တို႔ ဥပမာေလးနဲ႔ ေလ့လာၾကည့္ပါ့မယ္။ နားလည္ႏိုင္ၾကလိမ့္မယ္လို႔ ထင္ပါတယ္ဗ်ာ။

For only one Loop : O(n) For Variable Index : O(n^2) -gets incremented and decremented ဒီ Algorithm ကေတာ့ Stupid Sort အမ်ိဳးအစားထဲမွာပါေပမဲ့ Sorting Method ေတြထဲမွာ Adaptive ျဖစ္ၿပီး သံုးသင့္တဲ့ ထဲမွာပါ၀င္ပါတယ္ဗ်။ Processing Time ၾကာတယ္/မၾကာဘူးကေတာ့ အသံုးျပဳမယ့္ Array/List အေပၚမွာ မူတည္ပါလိမ့္မယ္။ Algorithm ကိုက loop တစ္ခုအတြင္းမွာ increase and decrease ႏွစ္မ်ိဳးစလံုးကို သံုးထားတာကိုး။ ဒါေၾကာင့္ အသံုးျပဳမည့္ Array/List မွာ Sorted ျဖစ္ၿပီးသား Element ေတြ မ်ားမ်ား order ျဖစ္ေနရင္ Processing Time ျမန္မွာျဖစ္ၿပီး မဟုတ္ရင္ေတာ့ ၾကာႏိုင္ပါလိမ့္မယ္ဗ်။

ကဲ… ေသခ်ာနားလည္သြားေအာင္ ေအာက္မွာ C# နဲ႔ေရးထားတဲ့ ကုဒ္အျပည့္အစံုေလးကို ေလ့လာၾကည့္ၾကစို႔ဗ်ာ။ using System; using System.Diagnostics; namespace SortingMethods { class Program { static void Main(string[] args) { int[] data = { -1, 925, -58, 885, -11, -525, -6,100,10,1,31,-45 }; Stopwatch sw = new Stopwatch(); sw.Start(); Console.WriteLine("Gnome Sort Algorithm\n=======================\n"); Console.WriteLine("UnSorted Array"); printArray(data); Console.WriteLine("\n\nSorted Array"); GnomeSort(ref data); printArray(data); Console.WriteLine("\n\nProcessing Time: \n\t" + sw.Elapsed.ToString("c")); sw.Stop(); Console.ReadKey(); } static void printArray(int[] arr) { int len = arr.Length; for (int i = 0; i < len; i++) { Console.Write(arr[i] + ", "); } } private static void GnomeSort(ref int[] data) { int i = 1; while (i < data.Length) { int tmp; if (data[i-1] <= data[i]) { i++; } else { tmp = data[i - 1]; data[i - 1] = data[i]; data[i] = tmp; i--; if (i==0) { i = 1; } } } } } }
မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမအားလံုး ေလ့လာျခင္းျဖင့္ ေက်နပ္ႏိုင္ၾကပါေစ။

မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမမ်ား အားလံုးပဲ မဂၤလာပါဗ်ာ။ က်ေနာ္တို႔ ဒီေန႔ Bogo Sort ဆိုတဲ့ Sorting Algorithm ေလးတစ္ခုအေၾကာင္းကို ေလ့လာၾကည့္ပါမယ္။ က်ေနာ့္ ေလ့က်င့္ခန္းေတြကေတာ့ စတင္ ေလ့လာသူမ်ားအတြက္သာ ရည္ရြယ္ပါတရ္။ ဒါေၾကာင့္ သိေနၿပီးသား သူမ်ားအေနနဲ႔ နားလည္ေပးၾကဖို႔နဲ႔ က်ေနာ္ရဲ႕ တင္ျပပံု မွားယြင္းတာမ်ားရွိခဲ့ရင္ ျပန္လည္ေထာက္ျပေပးႏိုင္ဖို႔ ေမွ်ာ္လင့္ပါတရ္ဗ်။

Bogo Sort ကိုေတာ့…  Permutation Sort,  Stupid Sort,  Slow Sort,  Shotgun Sort or  Monkey Sort ဆိုၿပီး အမ်ိဳးမ်ိဳး ေခၚေ၀ၚၾကပါတယ္။ ေခါင္းစဥ္ခြဲေတြကို ၾကည့္လိုက္တာနဲ႔တင္ Bogo Sort ရဲ႕ အက်ိဳးသက္ေရာက္မႈကို သိႏိုင္ပါလိမ့္မယ္။ ဒီေကာင္က အစီအစဥ္က်နစြာ အလုပ္,လုပ္ျခင္းမ်ိဳးမဟုတ္ဘဲ မ်က္ကန္းလမ္းေလွ်ာက္ ဆန္ေနပါတယ္။ Key Generator တစ္ခုက ခ်ေပးလိုက္တဲ့ ကိန္းစဥ္တန္းေပၚမူတည္ၿပီး Sorted List ျဖစ္/မျဖစ္ စစ္ပါတယ္။ Sorted List မျဖစ္မျခင္း ကိန္းစဥ္တန္းကို Key Generator ကိုျဖတ္ခိုင္းၿပီး ေနာက္တစ္ဖန္ Input အတြက္ ကိန္းစဥ္တန္းတစ္ခု Generate လုပ္ယူပါတယ္။ Sorted List ျဖစ္သြားမွသာ ရပ္တန္႔သြားမွာျဖစ္ပါတယ္။ Key Generator ကလည္း Random သေဘာ အလုပ္,လုပ္ေနတာျဖစ္တဲ့အတြက္ လက္ေတြ႔အရ အန္စာတုံးေခါက္ယူတာနဲ႔ ဆင္တူပါတယ္။

Pseudocode ကေတာ့ ရိုးရွင္းပါတယ္။ ေအာက္မွာ ေလ့လာၾကည့္လိုက္ပါ။ while not Sorted(list) do shuffle(list) done Example: Let us consider an example array (3 2 5 1 0 4) 4 5 0 3 2 1 (1st shuffling) 4 1 3 2 5 0 (2nd shuffling) 1 0 3 2 5 4 (3rd shuffling) 3 1 0 2 4 5 (4th shuffling) 1 4 5 0 3 2 (5th shuffling) . . . 0 1 2 3 4 5 (nth shuffling)—— Sorted Array Pseudocode နဲ႔ Exmaple ကိုၾကည့္လိုက္ရင္ေတာ့ Bogo Sort ရဲ႕ အလုပ္ လုပ္သြားပံုကို အနည္းငယ္ နားလည္ႏိုင္လိမ့္မယ္ ထင္ပါတယ္။ အန္စာတံုး ဥပမာနဲ႔ ျပန္ေျပာရရင္ေတာ့… 1. Shuffle( ) function ထဲမွာ ကိန္းစဥ္တန္း အေရအတြက္အတိုင္း အန္စာေခါက္မယ္၊ ရလာတဲ့ ကိန္းေတြကို အစဥ္တိုင္း ခ်ေရးမယ္၊ ၿပီးရင္ေတာ့ Sorted( ) function ကို Sorted List ျဖစ္/မျဖစ္ အစစ္ေဆးခံနိုင္ရန္ ပို႔ေပး ရပါတယ္။ 2. Sorted( ) function ကေတာ့ Shuffle( ) function က Generate လုပ္ၿပီး ပို႔လာတဲ့ ကိန္းစဥ္တန္းကို Sorted List ျဖစ္/မျဖစ္ ကိန္းလံုး အခ်င္းခ်င္း ႏႈိင္းယွဥ္ၿပီး စစ္ေဆးပါတယ္။ Sorted List ျဖစ္တယ္ဆို ရင္ေတာ့ End ကိုခုန္ၿပီး Sorted List ကို ထုတ္ျပေပးပါတယ္။ Sorted List မျဖစ္ခဲ့ရင္ေတာ့ အဆင့္(၁)၊ Shuffle( ) function ကိုျပန္သြားေစၿပီး ေနာက္တစ္ႀကိမ္ Input အတြက္ ကိန္းစဥ္တန္းကို Generate ထပ္လုပ္ခုိင္းပါတယ္။ ဒီသေဘာတရားအတိုင္း Sorted List မျဖစ္မျခင္း Algorithm ကို ထပ္ခါတလဲလဲ အလုပ္ လုပ္ေစမွာ ျဖစ္ပါတယ္။ Time Complexity ကေတာ့ ေအာက္ပါအတိုင္းပါပဲဗ်ာ။ Worst Case : O(∞) (since this algorithm has no upper bound) Average Case : O(n*n!) Best Case : O(n) (when array given is already sorted) အလုပ္ လုပ္ေနမယ့္ Shuffling ကေတာ့ အကန္႔အသတ္မရွိ n အႀကိမ္ေျမာက္ထိ ျဖစ္ႏိုင္ပါတယ္။ ဒါေၾကာင့္ အသံုးျပဳသင့္တဲ့ Sorting Algorithm တစ္ခုေတာ့ မဟုတ္ပါဘူး။ အျခားေသာ Algorithm ေတြနဲ႔ ႏႈိင္းယွဥ္ ေဖာ္ျပဖို႔အတြက္ ပညာေရးဆိုင္ရာ နယ္ပယ္ေတြမွာ သီအိုရီအရ သိသင့္တဲ့ Sorting Method တစ္ခုလို႔ပဲ ေျပာပါ ရေစ။ မွတ္ခ်က္။ ။ ၆ မ်က္ႏွာပဲရွိတဲ့ အန္စာတံုးမွာေတာင္မွ မိမိလိုခ်င္တဲ့ ကိန္းတစ္ခုကို ရဖို႔ အႀကိမ္အေတာ္ ၾကာၾကာ ေခါက္ယူရတာျဖစ္တဲ့အတြက္ Bogo Sort ရဲ႕ ကိန္းစဥ္တန္းဟာလည္း မ်ားရင္ မ်ားသလို Shuffling အႀကိမ္အေရအတြက္ ပိုမ်ားႏိုင္ၿပီး Compile Time ပိုၾကာႏိုင္ပါတယ္။ ဒါေပသိ ကိန္းစဥ္တန္းကို Generator နဲ႔ ထုတ္ေပးေနတာျဖစ္လို႔ ကံအေၾကာင္း သင့္ခဲ့ရင္ေတာ့ Sorted List ကို Shuffling အႀကိမ္ အနည္းငယ္အတြင္း မွာလည္း ရႏိုင္ပါတယ္ဗ်။

ေအာက္မွာ C# Code အျပည့္အစံုေလးကို ပိုနားလည္သြားေအာင္ ေလ့လာၾကည့္လိုက္ၾကပါအံုးဗ်ာ။ using System; using System.Diagnostics; namespace BogoSort { class Program { static void Main(string[] args) { int[] data = { -1, 25, -58, 85, -11, 25, 6 }; Stopwatch sw = new Stopwatch(); sw.Start(); Console.WriteLine("UnSorted Array"); printArray(data); Console.WriteLine("\n\nSorted Array"); BogoSort(ref data); printArray(data); Console.WriteLine("\n\nProcessing Time: \n\t" + sw.Elapsed.ToString("c")); sw.Stop(); Console.ReadKey(); } static void printArray(int[] arr) { int len = arr.Length; for (int i = 0; i < len; i++) { Console.Write(arr[i] + ", "); } } public static void BogoSort(ref int[] data) { while (!IsSorted(ref data)) { Shuffle(ref data); } } private static bool IsSorted(ref int[] data) { int count = data.Length; while (--count >= 1) { if (data[count] < data[count - 1]) { return false; } } return true; } private static void Shuffle(ref int[] data) { int temp, rnd; Random rand = new Random(); for (int i = 0; i < data.Length; ++i) { rnd = rand.Next(data.Length); temp = data[i]; data[i] = data[rnd]; data[rnd] = temp; } } } } မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမအားလံုး ေလ့လာျခင္းျဖင့္ ေက်နပ္ႏိုင္ၾကပါေစ။