ادغام دو آرایه مرتب در جاوا (Merge Two Sorted Array)

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

1. آشنایی با متد
2. آشنایی با if
3. آشنایی با while

آرایه

به مجموعه ای از داده ها (اطلاعات) با تعداد ثابت که از یک نوع جنس هستند آرایه میگویند. برای درک بهتر یک نوع جنسی از داده ها چند مثال ساده میزنیم. میتوان گفت نمره دانش آموزان یک کلاس از یک نوع جنس هستند(همگی double هستند مثلا)  یا اسامی دانشجویان یک رشته تحصیلی(همگی از جنس string هستند).

فرض کنید میخواهیم اسامی دانش آموزان یک کلاس را در برنامه خود بیاوریم یکی از راه ها این است که به تعداد دانش آموزان متغیر تعریف کنیم(بسیار خسته کننده و برای تغییرات پویا نیست). راه دیگر استفاده از آرایه است. آرایه میتواند مجموعه ای از داده هایی که از جنس(type) خاصی هستند را در خود نگه دارد.

ادغام دو آرایه مرتب در جاوا

برای ادغام دو آرایه مرتب در جاوا ما فرض میکنیم آرایه ها قبلا تعریف شده و مرتب هم هستند. با این فرضیات الگوریتم خود را شروع میکنیم. ابتدا دو اشاره گر تعریف میکنیم که  به اندیس خانه آخر هر دو آرایه اشاره دارد(در کد i و j هستند).مقدار خانه های هر دو اشاره گر را مقایسه میکنیم و خانه بزرگتر را در خانه آخر آرایه ای دیگر قرار میدهیم(منظور آرایه ادغام است) و اندیس آن آرایه را یکی به عقب میبریم.

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

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

  public static int[] merge(int A[], int B[]) {
          int i =A.length -1;
          int j = B.length -1;
          int k =A.length + B.length -1;
          int aux[] = new int[A.length + B.length];

          while (k >= 0) {
              if (j < 0 || (i >= 0 && A[i] > B[j]))
                   aux[k--] = A[i--];
              else
                   aux[k--] = B[j--];
          }
          return aux;
     }

کد ادغام دو آرایه در جاوا شامل متغییرهای زیر است:

1. I: اشاره گر به خانه آخر آرایه A
2. J: اشاره گر به خانه آخر آرایه B
3. K: اشاره گر به آرایه ادغام(آرایه aux)

همانطور که میبینید ما یک متد با ورودی دو آرایه A و B را ساختیم. سپس یک حلقه while که شرط پایان آن بررسی کل آرایه ها است را نوشتیم.

تست ادغام دو آرایه در جاوا

برای تست کدهای بالا، کد main زیر را بزنید:

    public static void main(String[] args) {
          int nums1[] = { 1, 12, 15, 26, 38,40 };
          int nums2[] = { 2, 13, 17, 30, 45 };


          int[] aux = merge(nums1, nums2);
          System.out.println(Arrays.toString(aux));

     }