إيجاد الوسيط لمصفوفتين مرتبتين ذات نفس الحجم

من موسوعة حسوب

المطلوب في هذه الخوارزمية هو إيجاد الوسيط 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[]‎.

  1. نحسب الوسيطين m1 و m2 للمصفوفتين ar1[]‎ و ar2[]‎ على التوالي.
  2. إن كان الوسيطان متساويين ينتهي عمل الخوارزمية وتعيد الوسيط المحسوب (إما m1 أو m2).
  3. إن كانت قيمة الوسيط m1 أكبر من m2 فإنّ الوسيط سيكون موجودًا في إحدى المصفوفتين الفرعيتين التاليتين:
    1. من العنصر الأول في ar1 إلى m1 أي ضمن النطاق ‎(ar1[0...|_n/2_|])‎.
    2. من m2 إلى العنصر الأخير في المصفوفة الثانية، أي ضمن النطاق ‎(ar2[|_n/2_|...n-1])‎.
  4. إن كانت قيمة الوسيط m2 أكبر من m1 فإنّ الوسيط سيكون موجودًا في إحدى المصفوفتين الفرعيتين التاليتين:
    1. من m1 إلى العنصر الأخير في المصفوفة ar1 أي ضمن النطاق ‎(ar1[|_n/2_|...n-1])‎.
    2. من العنصر الأول في المصفوفة ar2 إلى m2 أي ضمن النطاق ‎(ar2[0...|_n/2_|])‎.
  5. تعاد الخطوات السابقة إلى يصل عدد العناصر في كلتا المصفوفتين الفرعيتين إلى 2.
  6. إن وصل عدد عناصر كلت المصفوفتين إلى 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)‎.

مصادر

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/median_two_equal_sorted_arrays&oldid=29566»