سورس کد الگوریتم مرتب سازی ادغامی و انتخابی در سی شارپ

فرشاد مراحم

آموزش پیاده سازی الگوریتم های مرتب سازی در دات نت 

در این مقاله قصد داریم تا دو الگوریتم پرکاربرد و مهم در امر مرتب سازی را مورد بررسی قرار بدهیم و دو الگوریتم ادغامی (Merge-Sort) و الگوریتم انتخابی (Selection-Sort) را به همراه سورس کد مربوطه تشریح کنیم.

مفهوم الگوریتم مرتب سازی چیست ؟

 منظور از مرتب سازی داده ها چیدمان عناصر در یک قالب خاصی می باشد و هدف مرتب سازی داده ها با ترتیبی خاص در کنار هم جهت بهینه سازی الگوریتم های دیگر و افزایش راندمان می باشد. در این مقاله قصد داریم تا شما را با الگوریتم های مرتب سازی ادغامی یا mergesorting و مرتب سازی انتخابی selection sorting آشنا کنیم

مرتب سازی ادغامی

الگوریتم مرتب سازی با sort کردن ادغامی یک الگوریتم پرکاربرد که از روش تقسیم و غلبه برای حل مسئله مرتب سازی استفاده میکند و در حالت کلی تقسیم آرایه به زیر آرایه را تا زمانی که تعداد عناصر به ۱ نرسیده، ادامه می دهد. زمانی که به ۱ رسید، فرآیند ادغام کردن بلوک های مختلف شروع می شود و تا ادغام کل آرایه ادامه می یابد.

سورس کد زیر مرتب سازی ادغامی را به صورت کاملا حرفه ای در محیط Console App با نام پروژه MergeSorting انجام میدهد.

namespace MergeSorting
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Please insert number 1");
            string x = Console.ReadLine();
            int n = Convert.ToInt32(x);

            Console.WriteLine("Please insert number 2");
            string x1 = Console.ReadLine();
            int n1 = Convert.ToInt32(x1);

            Console.WriteLine("Please insert number 3");
            string x2 = Console.ReadLine();
            int n2 = Convert.ToInt32(x2);

            Console.WriteLine("Please insert number 4");
            string x3 = Console.ReadLine();
            int n3 = Convert.ToInt32(x3);

            Console.WriteLine("Please insert number 5");
            string x4 = Console.ReadLine();
            int n4 = Convert.ToInt32(x4);



            int[] numbers = { n1, n2, n3, n4, n5 };
            int len = 9;
            Console.WriteLine("MergeSort :");
            sortmethod(numbers, 0, len - 1);
            for (int i = 0; i < 5; i++)
                Console.WriteLine(numbers[i]);
            Console.Read();
        }
        static public void sortmethod(int[] numbers, int left, int right)
        {
            int mid;
            if (right > left)
            {
                mid = (right + left) / 2;
                sortmethod(numbers, left, mid);
                sortmethod(numbers, (mid + 1), right);
                mergemethod(numbers, left, (mid + 1), right);

            }
        }
        static public void mergemethod(int[] numbers, int left, int mid, int right)
        {
            int[] temp = new int[25];
            int i, left_end, num_elements, tmp_pos;
            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);
            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left] <= numbers[mid])
                    temp[tmp_pos++] = numbers[left++];
                else
                    temp[tmp_pos++] = numbers[mid++];
            }
            while (left <= left_end)
                temp[tmp_pos++] = numbers[left++];
            while (mid <= right)
                temp[tmp_pos++] = numbers[mid++];
            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }

        }
    }
}

توضیحات سورس کد : همانگونه که مشاهده میکنید در مرحله اول 5 عدد از کاربر گرفته میشود سپس تمامی اعداد در آرایه ای به نام Numbers ذخیره میشوند.در برنامه دو متد با نام های Sort-Method , Merge Method داریم که در Sort-Method بحث استفاده از روش تقسیم و غلبه پیاده سازی میشود سپس خروجی آن به تابع  Merge Method ارسال شده و بجث ادغام صورت میگیرد و طبق تعریف مرتب سازی ادغامی که آرایه ها به زیر آرایه تبدیل میشوند در سورس کد کاملا مشاهده میشود. میتوان گفت الگوریتم مرتب سازی ادغامی با مرتب سازی سریع همخوانی دارد و در برخی قسمت ها شبیه هم هستند که در مقالات بعدی مورد بررسی قرار خواهیم داد

مرتب سازی انتخابی : 

این الگوریتم مرتب سازی را بر اساس مقایسه عناصر با یکدیگر انجام میدهد و طی چند مرحله عناصر را به صورت صعودی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین عنصر را پیدا کرده و به انتهای لیست منتقل می‌کند.

سورس کد زیر پیاده سازی الگوریتم Selection Sort را نمایش میدهد :

namespace Selection_sort
{
    class Program
    {
        
            static void Main(string[] args)
            {
            Console.WriteLine("Please insert number1");
            string x = Console.ReadLine();
            int n = Convert.ToInt32(x);

            Console.WriteLine("Please insert number2");
            string x1 = Console.ReadLine();
            int n1 = Convert.ToInt32(x1);


            Console.WriteLine("Please insert number3");
            string x2 = Console.ReadLine();
            int n2 = Convert.ToInt32(x2);


            Console.WriteLine("Please insert number4");
            string x3 = Console.ReadLine();
            int n3 = Convert.ToInt32(x3);
            
            Console.WriteLine("Please insert number5");
            string x4 = Console.ReadLine();
            int n4 = Convert.ToInt32(x4);

            Console.WriteLine("Please insert number6");
            string x5 = Console.ReadLine();
            int n5 = Convert.ToInt32(x5);


                int array_size = 6;
                int[] array = new int[6] {n,n1,n2,n3,n4,n5 };
                Console.WriteLine("The Array Before Selection Sort is: ");
                for (int i = 0; i < array_size; i++)
                {
                    Console.WriteLine(array[i]);
                }
                int tmp, min_key;

                for (int j = 0; j < array_size - 1; j++)
                {
                    min_key = j;

                    for (int k = j + 1; k < array_size; k++)
                    {
                        if (array[k] < array[min_key])
                        {
                            min_key = k;
                        }
                    }

                    tmp = array[min_key];
                    array[min_key] = array[j];
                    array[j] = tmp;
                }

                Console.WriteLine("The Array After Selection Sort is: ");
                for (int i = 0; i < 6; i++)
                {
                    Console.WriteLine(array[i]);
                }
                Console.ReadLine();
            }
        }
    }
    

در سورس کد مربوطه 5 عدد از کاربر گرفته میشود و در آرایه ای به نام array ذخیره میشود سپس مرتب سازی در چند مرحله صورت میگیرد برای مثال اعداد 23,45,8,4,2 را در نظر بگیرید در مرحله اول مقایسه انجام شده و بزرگترین عدد به انتهای لیست میرود 23,8,4,2,45 سپس 8,4,2,23,45 تا آخر ادامه پیدا کرده و نهایتا لیست مرتب شده برابر میشود با 2,4,8,23,45

مقایسه دو الگوریتم با یکدیگر :

در بین الگوریتم‌های هم مرتبه، مرتب‌سازی انتخابی عموماً سریع تر از مرتب‌سازی حبابی عمل می‌کند. اما در مقایسه با مرتب‌سازی درجی کندتر است. در عمل این الگوریتم برای مرتب‌سازی یک لیست کوچک، الگوریتمی نسبتا کارا به‌شمار می‌رود.

در بدترین حالت تعداد مقایسه‌های مرتب‌سازی ادغام حدود ۰/۳۹ کمتر از مرتب‌سازی سریع در حالت متوسط می‌باشد. مرتب‌سازی ادغام همیشه تعداد مقایسه‌های کمتری را نسبت به مرتب‌ساز سریع احتیاج دارد، به جز در حالتی که تمام عناصر ورودی برابر باشند جایی که بدترین حالت مرتب‌سازی ادغام همراه با بهترین حالت مرتب‌سازی سریع پیدا می‌شود. پیچیدگی مرتب‌سازی ادغام در بدترین حالت از (O(nlgn می‌باشد که با بهترین حالت مرتب‌سازی سریع برابر می‌باشد اما در بهترین حالت تعداد مقایسه‌ها نصف تعداد مقایسه‌ها در بدترین حالت می‌باشد.