C# - Shaker Sort Algorithm | WLC_Programming Knowledge

C# - Shaker Sort Algorithm

Posted by ေတဇာလင္း Monday 8 January 2018 0 comments

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

အလုပ္လုပ္သြားတဲ့ လုပ္ငန္းစဥ္ကိုေတာ့ အထက္ပါပံုကို ၾကည့္လိုက္တာနဲ႔ နားလည္ႏိုင္ၾကမွာပါ။ ပိုၿပီးနားလည္သြားေအာင္ က်ေနာ္ အနည္းငရ္ ရွင္းျပပါ့မရ္။ Shaker Sort Algorithm ရဲ႕ Step တစ္ခုမွာ အဆင့္(2)ဆင့္ခြဲၿပီး အလုပ္လုပ္ပါတရ္(အတြင္း loop ႏွစ္ခုကို ဆိုလိုတာပါ)။

ပထမအဆင့္မွာေတာ့ Unsorted Array ရဲ႕ ပထမ Index ကစၿပီး ေနာက္ဆံုး index အထိ loop ပါတ္ကာ Increase ျဖစ္သြားေသာ ကပ္လွ်က္ index ေတြနဲ႔ ႏႈိင္းယွဥ္ပါတယ္။ ႏိႈင္းယွဥ္တဲ့ေနရာမွာ ႏႈိင္းယွဥ္ခံ element က ငယ္ေနရင္ေတာ့ ေနရာခ်င္း ခ်ိန္းယူပါတယ္။ loop ဆံုးသြားတဲ့အခ်ိန္မွာေတာ့ Array/List ရဲ႕ ေနာက္ဆံုး index မွာ အႀကီးဆံုးကိန္း ေရာက္ေနပါလိမ့္မယ္။ ၿပီးရင္ေတာ့ ဒုတိယ loop ကိုဆက္သြားပါၿပီ။

ဒုတိယအဆင့္ကေတာ့ ပထမအဆင့္နဲ႔ ေျပာင္းျပန္ပါ။ Sort ျဖစ္ၿပီးသား ေနာက္ဆံုး index ကို ခ်န္ခဲ့ပါတယ္။ sort မျဖစ္ေသးေသာ last index ကစၿပီး Decrease ျဖစ္သြားကာ first index ျပန္ေရာက္သည္အထိ loop ပါတ္ကာ ကပ္လွ်က္ index ေတြနဲ႔ ႏႈိင္းယွဥ္ပါတယ္။ ႏိႈင္းယွဥ္တဲ့ေနရာမွာ ႏႈိင္းယွဥ္ခံ element က ႀကီးေနရင္ေတာ့ ေနရာခ်င္း ခ်ိန္းယူပါတယ္။ loop ဆံုးသြားတဲ့အခ်ိန္မွာေတာ့ Array/List ထဲက အငယ္ဆံုး ကိန္းဟာ first index ဆီေရာက္ေနပါလိမ့္မယ္ဗ်။

မွတ္ခ်က္။ Step တစ္ႀကိမ္ၿပီးတိုင္း Array/List ရဲ႕ အျမင့္ဆံုး Index နဲ႔ အနိမ့္ဆံုး index တို႔ဟာ Sorting စီၿပီး ျဖစ္ေနပါလိမ့္မယ္။

ဒီနည္းလမ္းအတိုင္း Step အားလံုး ဆံုးသည္အထိ အလုပ္ လုပ္ေစၿပီး Array/List ကို Sorting စီယူမွာျဖစ္ပါတယ္ဗ်။ အေပၚက ရွင္းလင္းခ်က္ မူၾကမ္းပံုကို ၾကည့္လုိက္ရင္ေတာ့ မိတ္ေဆြတို႔အေနနဲ႔ က်ေနာ့္ ဆိုလိုရင္းကို နားလည္ပါလိမ့္မယ္ဗ်။ ပိုၿပီး နားလည္သြားေအာင္ ေအာက္က C# Code အျပည့္အစံုေလးကို ေလ့လာၾကည့္လိုက္ၾကပါအံုးဗ်ာ။

using System;
using System.Diagnostics;

namespace SortingMethods
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 2, 1, 12, 10, -3 };
            Stopwatch sw = new Stopwatch();
            sw.Start();
            Console.WriteLine("Shaker Sort Algorithm\n=======================\n");
            Console.WriteLine("UnSorted Array");
            printArray(data);

            Console.WriteLine("\n\nSorted Array");
            ShakerSort(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 ShakerSort(ref int[] data)
        {
            int key, tmp;
            int len = data.Length;
            
            for (key = 1; key <= len/2; key++) {
                //Increase Index for Highest Value
                for (int i = key-1; i < len-key; i++) {
                    if (data[i] > data[i + 1]) {
                        tmp = data[i];
                        data[i] = data[i + 1];
                        data[i + 1] = tmp;
                    }
                }

                //Decrease Index for Lower Value
                for (int j = len-key-1; j >= key; j--) {
                    if (data[j] < data[j - 1]) {
                        tmp = data[j];
                        data[j] = data[j - 1];
                        data[j - 1] = tmp;
                    }                    
                }
            }
        }
    }
}

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