#c, سی شارپ, مرتب سازی در #c

مرتب سازی ادغامی در سی شارپ (Merge Sort)

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

در این جلسه، تیم کدگیت را با آموزش مرتب سازی ادغامی در سی شارپ همراهی کنید. پیش نیاز این جلسه آشنایی با روش بازگشتی، آرایه و متد است.

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

مرتب‌سازی ادغامی یک الگوریتم مرتب‌سازی تطبیقی با زمان اجرای nlogn می‌باشد. در اکثر پیاده‌سازی‌ها این الگوریتم پایدار می‌باشد. بدین معنی که این الگوریتم ترتیب ورودی‌های مساوی را در خروجی مرتب شده حفظ می‌کند. این یک مثال از الگوریتم تقسیم و تسخیر می‌باشد. این الگوریتم در سال ۱۹۴۵ توسط جان فون نویمان اختراع شده‌است.

از نظر مفهومی یک الگوریتم مرتب‌سازی ادغام بدین صورت کار می‌کند:

  1. اگر طول لسیت ۰ یا ۱ باشد آن پیش از این مرتب شده‌است در غیر این صورت
  2. لیست نامرتب را به دو زیرلیست که اندازه آن‌ها در حدود نصف سایز لیست اولیه‌است تقسیم می‌کند.
  3. هر زیرلیست را به طور بازگشتی با صدا کردن merge sort مرتب می‌کند.
  4. دو تا دوتا زیر لیست‌ها را از آخر ادغام می‌کند تا به یک لیست برسد

مرتب‌سازی ادغام ۲ تا ایده اصلی را با هم ترکیب می‌کند تا زمان اجرایش تقویت شود

  1. یک لیست کوچک از گام‌های کم‌تری برای مرتب‌کردن نسبت به یک لیست بزرگ استفاده می‌کند.
  2. یرای مرتب کردن دو لیست مرتب‌شده نسبت به دو لیست نامرتب گام‌های کمتری نیاز می‌باشد به عنوان مثال اگر این لیست‌ها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبارپیمایش کنید(ویکیپدیا)

پیاده سازی مرتب سازی ادغامی در سی شارپ

در توضیحات بالا درباره نحوه  کاره مرتب سازی ادغامی صحبت شد. قبل از پیاده سازی در مورد نحوه merge کردن دو آرایه مرتب صحبت میکنیم سپس به پیاده سازی آن خواهیم پرداخت.

ما وقتی دو آرایه مرتب داریم و میخواهیم آنها را با هم ادغام(merge) کنیم باید دو اندیس به ابتدای هر دو آرایه اشاره کند. ما این اندیس ها را i و  j مینامیم. سپس کوچکترین مقداری که در اندیس های i و j قرار دارد را برمیداریم و اندیس مورد نظر را یکی به جلو حرکت میدهیم. با این کار ما بین دو آرایه کوچکترین مقدار را برمیداریم و در آرایه کمکی میریزیم.

حال نوبت به پیاده سازی رسیده است. ما برای پیاده سازی متدی به نام sort مینویسیم که یک آرایه ورودی بگیرد و آن را به روش ادغامی مرتب کند.ما در تمامی کد از آرایه ای به نام aux استفاده کردیم که آن را آرایه کمکی مینامند.

        private static void merge(int[] a, int[] aux, int lo,
            int mid, int hi) {


            for (int k = lo; k <= hi; k++) {
                aux[k] = a[k];
            }


            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                if (i > mid)
                    a[k] = aux[j++];
                else if (j > hi)
                    a[k] = aux[i++];
                else if (less(aux[j], aux[i]))
                    a[k] = aux[j++];
                else
                    a[k] = aux[i++];
            }


        }


        private static void sort(int[] a, int[] aux, int lo, int hi) {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            sort(a, aux, lo, mid);
            sort(a, aux, mid + 1, hi);
            merge(a, aux, lo, mid, hi);
        }


        public static void sort(int[] a) {
            int[] aux = new int[a.Length];
            sort(a, aux, 0, a.Length - 1);

        }


        private static bool less(int v, int w) {
            return (v < w);
        }

        private static void exch(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }


        private static void show(int[] a) {
            for (int i = 0; i < a.Length; i++) {
                Console.WriteLine(a[i]);
            }
        }

کد مرتب سازی ادغامی در سی شارپ شامل متد های زیر است:

  1. Show : این متد یک آرایه را ورودی میگیرد و آن را چاپ میکند.
  2. Exch: دو خانه از آرایه ورودی را جابجا میکند. اندیس خانه هایی که باید جابجا شوند در ورودی است(ما ورودی آرایه این متد را از جنس object گذاشتیم ولی میتوان آن را به int نیز عوض کرد توجه کنید در صورت جابجایی متغیر swap درون متد نیز باید int شود).
  3. Less: این متد دو ورودی v و w را میگیرد و به ما میگوید که آیا v کوچکتر از w است یا خیر.
  4. Merge: این متد دو آرایه را ادغام میکند. دو آرایه ما یکی از اندیس low تا mid آرایه اصلی هستند و دیگری از mid تا high آرایه اصلی هستند(متغیر low و mid و high ورودی های ما هستند) سپس نتیجه را در آرایه کمکی به نام aux میریزد.
  5. Sort: کد بالا دو متد sort دارد یکی فقط آرایه میگیرد و کل آن را مرتب میکند و دیگری آرایه و اندیس های ابتدا و انتهایی را ورودی میگیرد تا فقط بین این اندیس ها آرایه را مرتب کند. متد که یک ورودی دارد کار با آن راحت تر است.

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

برای تست کد مرتب سازی ادغامی در سی شارپ کافیست کد main زیر را بزنید.

        public static void Main (string[] args)
        {
            int[] a = {2,1,7,4,5,3,6};
            sort(a);
            show(a);

            Console.ReadKey ();
        }

خروجی مرتب سازی ادغامی در سی شارپ به صورت زیر است:

1
2
3
4
5
6
7

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *