مرتب سازی ادغامی در جاوا (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 boolean 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++) {
            System.out.println(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);

     }

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

1
2
3
4
5
6
7