إيجاد الوسيط لمصفوفتين مرتبتين ذات نفس الحجم
المطلوب في هذه الخوارزمية هو إيجاد الوسيط median للمصفوفة الناتجة عن دمج مصفوفتين مرتبتين ومتساويتين في الحجم.
يجدر ملاحظة أنّه لمّا كان عدد العناصر الناتج من دمج المصفوفتين هو عدد زوجي (2n
) فإن الوسيط يُحسب بانتخاب العددين الواقعين في وسط المصفوفة وحساب معدّلهما وإعادة الناتج بعد تقريبه.
الطريقة الأولى (العدّ أثناء الدمج)
تستخدم هذه الطريقة خطوات الدمج المستخدمة في خوارزمية الترتيب بالدمج، وتتابع العدّ أثناء المقارنة بين المصفوفتين، فإن وصلت الخوارزمية في العدّ إلى القيمة n
(لـ 2n
من العناصر) فهذا يعني وصولها إلى الوسيط. تحسب الخوارزمية معدّل العنصرين في الموقعين n
و n-1
في المصفوفة المدمجة.
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
using namespace std;
/* تعيد الدالة الوسيط من المصفوفتين المعطاتين
على فرض أنّهما مرتبتان وتحتويان على عدد العناصر عينه */
int getMedian(int ar1[],
int ar2[], int n)
{
int i = 0; /* الموقع الحالي في المصفوفة الأولى */
int j = 0; /* الموقع الحالي في المصفوفة الثانية */
int count;
int m1 = -1, m2 = -1;
/* 2n لما كانت المصفوفتان تحتويان على
من العناصر فإنّ الوسيط سيساوي معدّل العنصرين
n-1 و n
في المصفوفة الناتجة من دمج المصفوفتين المعطاتين */
for (count = 0; count <= n; count++)
{
/* معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الأولى
أصغر من أصغر (أو أول) عنصر في المصفوفة الثانية */
if (i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/* معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الثانية
أصغر من أصغر (أو أول) عنصر في المصفوفة الأولى */
else if (j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if (ar1[i] < ar2[j])
{
/* حفظ قيمة الوسيط السابقة */
m1 = m2;
m2 = ar1[i];
i++;
}
else
{
/* حفظ قيمة الوسيط السابقة */
m1 = m2;
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
// اختبار الدالة السابقة
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(ar1) / sizeof(ar1[0]);
int n2 = sizeof(ar2) / sizeof(ar2[0]);
if (n1 == n2)
cout << "Median is "
<< getMedian(ar1, ar2, n1) ;
else
cout << "Doesn't work for arrays"
<< " of unequal size" ;
getchar();
return 0;
}
- بايثون:
# تعيد الدالة الوسيط من المصفوفتين المعطاتين
# على فرض أنّهما مرتبتان وتحتويان على عدد العناصر عينه
def getMedian( ar1, ar2 , n):
i = 0 # الموقع الحالي في القائمة الأولى
j = 0 # الموقع الحالي في القائمة الثانية
m1 = -1
m2 = -1
# 2n لما كانت المصفوفتان تحتويان على
# من العناصر فإنّ الوسيط سيساوي معدّل العنصرين
# n-1 و n
# في المصفوفة الناتجة من دمج المصفوفتين المعطاتين
count = 0
while count < n + 1:
count += 1
# معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الأولى
# أصغر من أصغر (أو أول) عنصر في المصفوفة الثانية
if i == n:
m1 = m2
m2 = ar2[0]
break
# معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الثانية
# أصغر من أصغر (أو أول) عنصر في المصفوفة الأولى
elif j == n:
m1 = m2
m2 = ar1[0]
break
if ar1[i] < ar2[j]:
m1 = m2 # حفظ قيمة الوسيط السابقة
m2 = ar1[i]
i += 1
else:
m1 = m2 # حفظ قيمة الوسيط السابقة
m2 = ar2[j]
j += 1
return (m1 + m2)/2
# اختبار الدالة السابقة
ar1 = [1, 12, 15, 26, 38]
ar2 = [2, 13, 17, 30, 45]
n1 = len(ar1)
n2 = len(ar2)
if n1 == n2:
print("Median is ", getMedian(ar1, ar2, n1))
else:
print("Doesn't work for arrays of unequal size")
- جافا:
class Main
{
/* تعيد الدالة الوسيط من المصفوفتين المعطاتين
على فرض أنّهما مرتبتان وتحتويان على عدد العناصر عينه */
static int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* الموقع الحالي في المصفوفة الأولى */
int j = 0; /* الموقع الحالي في المصفوفة الثانية */
int count;
int m1 = -1, m2 = -1;
/* 2n لما كانت المصفوفتان تحتويان على
من العناصر فإنّ الوسيط سيساوي معدّل العنصرين
n-1 و n
في المصفوفة الناتجة من دمج المصفوفتين المعطاتين */
for (count = 0; count <= n; count++)
{
/* معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الأولى
أصغر من أصغر (أو أول) عنصر في المصفوفة الثانية */
if (i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/* معالجة الحالة التي تكون فيها جميع العناصر في المصفوفة الثانية
أصغر من أصغر (أو أول) عنصر في المصفوفة الأولى */
else if (j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if (ar1[i] < ar2[j])
{
/* حفظ قيمة الوسيط السابقة */
m1 = m2;
m2 = ar1[i];
i++;
}
else
{
/* حفظ قيمة الوسيط السابقة */
m1 = m2;
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* اختبار الدالة السابقة */
public static void main (String[] args)
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
int n1 = ar1.length;
int n2 = ar2.length;
if (n1 == n2)
System.out.println("Median is " +
getMedian(ar1, ar2, n1));
else
System.out.println("arrays are of unequal size");
}
}
تعطي الشيفرات السابقة المخرجات التالية:
Median is 16
الطريقة الثانية (مقارنة وسيطي المصفوفتين)
تحسب هذه الطريقة الوسيط عن طريق حساب وسيطي المصفوفتين المرتبتين ومقارنتهما بعضهما ببعض، وتتّبع هذه الطريقة أسلوب فرِّق تسد في تنفيذ الخوارزمية.
خطوات الخوارزمية
تتبع هذه الخوارزمية الخطوات التالية:
لتكن المصفوفة الأولى ar1[]
والثانية ar2[]
.
- نحسب الوسيطين
m1
وm2
للمصفوفتينar1[]
وar2[]
على التوالي. - إن كان الوسيطان متساويين ينتهي عمل الخوارزمية وتعيد الوسيط المحسوب (إما
m1
أوm2
). - إن كانت قيمة الوسيط
m1
أكبر منm2
فإنّ الوسيط سيكون موجودًا في إحدى المصفوفتين الفرعيتين التاليتين:- من العنصر الأول في
ar1
إلىm1
أي ضمن النطاق(ar1[0...|_n/2_|])
. - من
m2
إلى العنصر الأخير في المصفوفة الثانية، أي ضمن النطاق(ar2[|_n/2_|...n-1])
.
- من العنصر الأول في
- إن كانت قيمة الوسيط
m2
أكبر منm1
فإنّ الوسيط سيكون موجودًا في إحدى المصفوفتين الفرعيتين التاليتين:- من
m1
إلى العنصر الأخير في المصفوفةar1
أي ضمن النطاق(ar1[|_n/2_|...n-1])
. - من العنصر الأول في المصفوفة
ar2
إلىm2
أي ضمن النطاق(ar2[0...|_n/2_|])
.
- من
- تعاد الخطوات السابقة إلى يصل عدد العناصر في كلتا المصفوفتين الفرعيتين إلى
2
. - إن وصل عدد عناصر كلت المصفوفتين إلى
2
يُحسب الوسيط باستخدام الصيغة التالية:
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
.
يلاحظ أنّ m1 < m2
، وهذا يعني أنّ الوسيط سيكون في إحدى المصفوفتين الفرعيتين التاليتين:
[15, 26, 38] و [2, 13, 17]
قيمتا الوسيط للمصفوفتين السابقتين هما m1 = 26
, m2 = 13
.
يلاحظ أن m2 < m1
وهذا يعني أن الوسيط سيكون في إحدى المصفوفتين الفرعيتين التاليتين:
[15, 26] and [13, 17]
تحتوي كل مصفوفة الآن على عنصرين فقط؛ لذا يمكن حساب الوسيط باستخدام الصيغة التالية:
median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include<bits/stdc++.h>
using namespace std;
/* هذه الدالة مسؤولة عن جلب الوسيط للمصفوفة المرتبة المعطاة */
int median(int [], int);
/* تعيد الدالة الوسيط من المصفوفتين المعطاتين
على فرض أنّهما مرتبتان وتحتويان على عدد العناصر عينه */
int getMedian(int ar1[],
int ar2[], int n)
{
/* تعيد الدالة القيمة -1 للمدخلات غير الصالحة */
if (n <= 0)
return -1;
if (n == 1)
return (ar1[0] +
ar2[0]) / 2;
if (n == 2)
return (max(ar1[0], ar2[0]) +
min(ar1[1], ar2[1])) / 2;
/* الحصول على الوسيط للمصفوفة الأولى */
int m1 = median(ar1, n);
/* الحصول على الوسيط للمصفوفة الثانية */
int m2 = median(ar2, n);
/* إن تساوت قيمتا الوسيط تعيد الدالة أحدهما */
if (m1 == m2)
return m1;
/* إن كان الوسيط الأول أصغر من الوسيط الثاني */
if (m1 < m2)
{
if (n % 2 == 0)
return getMedian(ar1 + n / 2 - 1,
ar2, n - n / 2 + 1);
return getMedian(ar1 + n / 2,
ar2, n - n / 2);
}
/* إن كان الوسيط الثاني أصغر من الوسيط الأول */
if (n % 2 == 0)
return getMedian(ar2 + n / 2 - 1,
ar1, n - n / 2 + 1);
return getMedian(ar2 + n / 2,
ar1, n - n / 2);
}
/* تحسب الدالة الوسيط للمصفوفة المرتبة المعطاة */
int median(int arr[], int n)
{
if (n % 2 == 0)
return (arr[n / 2] +
arr[n / 2 - 1]) / 2;
else
return arr[n / 2];
}
// اختبار الدالة السابقة
int main()
{
int ar1[] = {1, 2, 3, 6};
int ar2[] = {4, 6, 8, 10};
int n1 = sizeof(ar1) /
sizeof(ar1[0]);
int n2 = sizeof(ar2) /
sizeof(ar2[0]);
if (n1 == n2)
cout << "Median is "
<< getMedian(ar1, ar2, n1);
else
cout << "Doesn't work for arrays "
<< "of unequal size";
return 0;
}
- بايثون:
# هذه الدالة مسؤولة عن جلب الوسيط للمصفوفة المرتبة المعطاة
def getMedian(arr1, arr2, n):
# في حال عدم وجود أي عنصر في أيٍّ من القائمتين
# there is no element in any array
if n == 0:
return -1
# في حال وجود عنصر واحد في كل قائمة
# فإن قيمة الوسيط ستساوي مجموع العنصرين مقسومًا على 2
elif n == 1:
return (arr1[0]+arr2[1])/2
# إن كان هناك عنصران في كل قائمة
elif n == 2:
return (max(arr1[0], arr2[0]) +
min(arr1[1], arr2[1])) / 2
else:
# حساب قيمتي الوسيط
m1 = median(arr1, n)
m2 = median(arr2, n)
# سيكون العنصران الموجودان في موقعي الوسيط
# بين الوسيط ذي القيمة الأكبر والعنصر الأول
# في المصفوفة التي ينتمي إليها ذلك الوسيط
# وبين الوسيط الثاني والعنصر الأخير
# في المصفوفة التي ينتمي إليها ذلك الوسيط
if m1 > m2:
if n % 2 == 0:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2):], int(n / 2) + 1)
else:
if n % 2 == 0:
return getMedian(arr1[int(n / 2 - 1):],
arr2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return getMedian(arr1[int(n / 2):],
arr2[0:int(n / 2) + 1], int(n / 2) + 1)
# تحسب الدال الوسيط في المصفوفة المعطاة
def median(arr, n):
if n % 2 == 0:
return (arr[int(n / 2)] +
arr[int(n / 2) - 1]) / 2
else:
return arr[int(n/2)]
# اختبار الدوال السابقة
arr1 = [1, 2, 3, 6]
arr2 = [4, 6, 8, 10]
n = len(arr1)
print(int(getMedian(arr1,arr2,n)))
- جافا:
import java.util.*;
class GfG {
/* تعيد الدالة الوسيط من المصفوفتين المعطاتين
على فرض أنّهما مرتبتان وتحتويان على عدد العناصر عينه */
static int getMedian(int ar1[], int ar2[], int n)
{
/* تعيد الدالة القيمة -1 للمدخلات غير الصالحة */
if (n <= 0)
return -1;
if (n == 1)
return (ar1[0] + ar2[0]) / 2;
if (n == 2)
return (Math.max(ar1[0], ar2[0]) + Math.min(ar1[1], ar2[1])) / 2;
/* الحصول على الوسيط للمصفوفة الأولى */
int m1 = median(ar1, n);
/* الحصول على الوسيط للمصفوفة الثانية */
int m2 = median(ar2, n);
/* إن تساوت قيمتا الوسيط تعيد الدالة أحدهما */
if (m1 == m2)
return m1;
/* إن كان الوسيط الأول أصغر من الوسيط الثاني */
if (m1 < m2)
{
if (n % 2 == 0)
return getMedian(ar1 + n / 2 - 1, ar2, n - n / 2 + 1);
return getMedian(ar1 + n / 2, ar2, n - n / 2);
}
/* إن كان الوسيط الثاني أصغر من الوسيط الأول */
if (n % 2 == 0)
return getMedian(ar2 + n / 2 - 1, ar1, n - n / 2 + 1);
return getMedian(ar2 + n / 2, ar1, n - n / 2);
}
/* تحسب الدالة الوسيط للمصفوفة المرتبة المعطاة */
static int median(int arr[], int n)
{
if (n % 2 == 0)
return (arr[n / 2] + arr[n / 2 - 1]) / 2;
else
return arr[n / 2];
}
// اختبار الدالة السابقة
public static void main(String[] args)
{
int ar1[] = {1, 2, 3, 6};
int ar2[] = {4, 6, 8, 10};
int n1 = ar1.length;
int n2 = ar2.length;
if (n1 == n2)
System.out.println("Median is " + getMedian(ar1, ar2, n1));
else
System.out.println("Doesn't work for arrays "+ "of unequal size");
}
}
تعطي الشيفرات السابقة المخرجات التالية:
Median is 5
التعقيد الزمني
يبلغ التعقيد الزمني لتنفيذ الخوارزمية بأسلوب فرِّق تسد المقدار O(logn)
.
مصادر
- صفحة Median of two sorted arrays of same size في توثيق الخوارزميات في موقع GeeksforGeeks.