میانه دو آرایه مرتب شده با اندازه یکسان – به زبان ساده

در این مطلب، روش پیدا کردن میانه دو آرایه مرتب شده با اندازه یکسان بیان شده است. دو آرایه مرتب شده A و B هر دو با سایز n موجود هستند. هدف، نوشتن الگوریتمی است که میانه آرایه را پس از ادغام دو آرایه اولیه بیان شده، به دست بیاورد (در واقع، میانه را در آرایه با طول 2n پیدا کند). پیچیدگی باید از مرتبه ((O(log(n باشد.

با توجه به اینکه اندازه آرایه‌ای که قرار است میانه در آن پیدا شود زوج است (2n)، نیاز به محاسبه میانگین دو عدد وسطی و بازگرداندن جز صحیح آن است.

 راهکار اول: محاسبه تعداد هنگام ادغام

برای این کار، از روال ادغام در «مرتب‌سازی ادغامی» (Marge Sort) استفاده می‌شود. شمارش هنگام مقایسه عناصر دو آرایه انجام می‌شود. اگر حاصل شمارش برابر با n شود (برای 2n عنصر)، می‌توان به میانه رسید. میانگین عناصر در اندیس n - 1 و n در آرایه ادغام شده را باید به دست آورد.

قطعه کدهای زیر، راهکار بیان شده را پیاده‌سازی می‌کنند.

محاسبه میانه آرایه در ++C

محاسبه میانه آرایه در C

محاسبه میانه آرایه در جاوا

محاسبه میانه آرایه در پایتون ۳

محاسبه میانه آرایه در #C

محاسبه میانه آرایه در PHP

خروجی قطعه کدهای بالا به صورت زیر و پیچیدگی زمانی روش پیاده‌سازی شده در بالا از درجه (O(n است.

Median is 16

روش دوم: مقایسه میانه دو آرایه

در این روش، ابتدا میانه دو آرایه مرتب شده دریافت و سپس این میانه‌ها با یکدیگر مقایسه می‌شوند. فرض می‌شود ar1 و ar2 آرایه‌های ورودی هستند. الگوریتم زیر، برای پیدا کردن میانه آرایه حاصل از ادغام این دو آرایه مورد استفاده قرار می‌گیرد.

1. میانه m1 و m2 را برای آرایه‌های ورودی []ar1 و []ar2 محاسبه کن.
2. اگر m1 و m2 هر دو مساوی هستند، کار تمام می‌شود. m1 یا m2 را بازگردان.
3. اگر m1 بزرگ‌تر از m2 است، میانه در یکی از زیر آرایه‌های زیر خواهد بود:
   • از اولین عنصر ar1 تا m1 (به صورت [|ـar1[0...|_n/2)
   • از m2 تا آخرین عنصر ar2 (به صورت [ar2[|_n/2_|...n-1)
4. اگر m2 بزرگ‌تر از m1 باشد، میانه در یکی از زیر آرایه‌های زیر خواهد بود:
   • از m1 تا آخرین عنصر ar1 (به صورت [ar1[|_n/2_|...n-1)
   • از اولین عنصر ar2 تا m2 (به صورت [_|ar2[0...|_n/2)
5. فرایند بالا را تا هنگامی که اندازه هر دو زیرآرایه برابر با ۲ باشد ادامه بده.
6. اگر اندازه دو آرایه برابر با ۲ باشد، از فرمول زیر برای محاسبه میانه استفاده کن:

Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

مثال: 

 ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

برای دو آرایه بالا، m1 = 15 و m2 = 17 است. برای آرایه‌های []ar1 و []ar2، مقدار m1 کوچک‌تر از m2 است. بنابراین، میانه در یکی از دو زیرآرایه‌ای که در ادامه آمده‌اند، وجود خواهد داشت.

 [15, 26, 38] and [2, 13, 17]

فرایند برای دو زیرآرایه تکرار می‌شود و خروجی آن به صورت زیر است.

 m1 = 26 m2 = 13.

m1 بزرگ‌تر از m2 است. بنابراین زیرآرایه‌ها به صورت زیر خواهند بود.

 [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2 
= (15 + 17)/2
= 16

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

محاسبه میانه آرایه در ++C

محاسبه میانه آرایه در C

محاسبه میانه آرایه در جاوا

محاسبه میانه آرایه در پایتون

خروجی قطعه کدهای بالا به صورت زیر و پیچیدگی زمانی روش ارائه شده در بالا از درجه (O(logn است.

Median is 5

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

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• برنامه تشخیص اعداد اول در پایتون — به زبان ساده
• برنامه محاسبه nامین عدد فیبوناچی — به زبان ساده
• برنامه محاسبه مجموع اعداد از ۱ تا n — راهنمای کاربردی

^^