C# - Bogo Sort | WLC_Programming Knowledge

C# - Bogo Sort

Posted by ေတဇာလင္း Wednesday, 20 December 2017 0 comments

မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမမ်ား အားလံုးပဲ မဂၤလာပါဗ်ာ။ က်ေနာ္တို႔ ဒီေန႔ 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;
            }
        }        
    }
}

မိတ္ေဆြ၊ ညီအစ္ကို၊ ေမာင္ႏွမအားလံုး ေလ့လာျခင္းျဖင့္ ေက်နပ္ႏိုင္ၾကပါေစ။