C# - Gnome Sort | WLC_Programming Knowledge

C# - Gnome Sort

Posted by ေတဇာလင္း Monday, 25 December 2017 0 comments

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

Gnome 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 အလုပ္ လုပ္သြားပံုကို က်ေနာ္တို႔ ဥပမာေလးနဲ႔ ေလ့လာၾကည့္ပါ့မယ္။

နားလည္ႏိုင္ၾကလိမ့္မယ္လို႔ ထင္ပါတယ္ဗ်ာ။

Time Complexity :

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; }
                }
            }
        }       
    }
}