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

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)
N write.svg
هذه مقالة جديدة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (أكتوبر 2012)
Commons-emblem-copyedit.svg
هذه المقالة ليس بها أي وصلات لمقالاتٍ أخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (ديسمبر 2013)

خوارزمية الاختيار او 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 اعداد في القائمة ل- حيث كل قائمة تحوي على 5 اعداد وقائمة اخيرة تحوي البواقي وهي بكبر :n mod 5
  2. - جد القيمة الوسطى للقوائم (تستطيع ان تصنف ثم تجد لكل قائمة القيمة الوسطى)
  3. - استدعي اختيار لايجاد القيمة الوسطى,x, ل الاعداد التي وجدتها في 2
  4. - قسم القائمة حول x بواسطة partition ولنقل ان الاعداد في القائمة السفلى عددها k والقائمة العليا هي n-k
  5. - استدعي اختيار بشكل ذاتي لايجاد العدد ال-i في القائمة السفلى اذا: i≤k او العدد ال- i-k الأصغر اذا i>k

تحليل زمن الخوارزمية[عدل]

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

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

وصلات خارجية[عدل]