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

خوارزمية الاختيار هي طريقة بحث فعالة حيث يتم اعطاء الخوارزمية عدد,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

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

• بوابة خوارزميات
• بوابة علم الحاسوب