خوارزمية الاختيار

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أغسطس 2017)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

خَوَارِزمِيَّةُ الاِختِيَارِ (بالإنجليزية: selection algorithm)‏ هي خوارزمية لإيجاد مكان عدد بالترتيب حسب التصنيف، وتعد هذه الخوارزمية من أشهر الخوارزميات لأنه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion

خوارزمية الاختيار هي طريقة بحث فعّـالة حيث تُعطَى الخوارزمية عدد i, والهدف هو إيجاد العدد ال-i في القائمة بعد التصنيف -SORTING- هناك عدة طرق لإيجاد هذا الهدف وقد تم التوصل إلى خوارزمية فعالة بزمن خطي - linear time algorithm-

عندما يكون i=1 عندها على الخوارزمية إيجاد العدد الأول من حيث الترتيب أي اصغر قيمة في القائمة وهذه المهمة بسيطة جدا وإيجاد هذه القيمة يتم عن طريق بحث خطي مع متغيِّر إضافيّ وها هي طريقة لفعل هذا:

int FindMin(int[] A)
{
int min=A[0];
for(int j=1;j<=A.length;j++)
{ 
  if(A[j]<A[0])
  {
    min=A[j];
  }
}
return min;
}

وحالة أخرى هي i=n وعندها يجب ايجاد القيمة الكبرى وبطريقة مشابهة لايجاد القيمة الصغرى.

نبدأ أولا بالطريقة السهلة وهي تتم عن طريق تحويل الاختيار إلى تصنيف ثم التوجه للعدد المطلوب أي:

int select(int[] A,int i)
{
return (A.sort())[i]
}

هذه الطريقة صحيحة ولكن الوقت الذي تحتاجه هو: ((O(nlog(n ونريد ان نصل لخوارزمية فعالة بوقت خطي بالنسبة للمدخل!

هذه الخوارزمية تستخدم طريقة الاستدعاء الذاتي (العودية) وهي كالتالي: اسم هذه الخوارزمية سيكون: اختيار

• إذا n=1 نرجع القيمة الوحيدة الموجودة وهو بمثابة العدد ال -i
• إذا n>1 حينها:

1. - قسم ال-n أعداد في القائمة ل- ${\displaystyle \lfloor n/5\rfloor }$ حيث كل قائمة تحوي 5 أعداد وقائمة أخيرة تحوي البواقي وهي بكبر:n mod 5
2. - جِد القيمة الوسطى للقوائم (تستطيع ان تصنف ثم تجد لكل قائمة القيمة الوسطى)
3. - استدعي اختيار لايجاد القيمة الوسطى،x, ل${\displaystyle \lfloor n/5\rfloor }$ الاعداد التي وجدتها في 2
4. - قسم القائمة حول x بواسطة partition ولنقل أن الأعداد في القائمة السفلى عددها k والقائمة العليا هي n-k
5. - استدعي اختيار بشكل ذاتي لايجاد العدد ال-i في القائمة السفلى إذا: i≤k أو العدد ال- i-k الأصغر إذا i>k

• معادلة الاستدعاء الذاتي:

${\displaystyle T(n)\leq T(n/5)+T(7\cdot n/10)+O(n).}$

• وحلها كالتالي:

${\displaystyle T(n)\leq c\cdot n\cdot (1+(9/10)+(9/10)^{2}+\cdots )\in O(n).}$

• Design and Analysis of Algorithms, for a detailed explanation of the recurrence relation for the median-of-medians