خوارزمية الترتيب بالإختيار من الخوارزميات الأساسية التي يجب معرفتها لجميع دارسي علم الخوارزميات، و ربما ستندهش من حقيقة أنك قد إبتكرت هذه الخوارزمية بنفسك و استخدمتها في حياتك كثيراً دون أن تسميها بإسمها “خوارزمية الترتيب بالإختيار”، و ستلاحظ أن طريقة عمل الخوارزمية من السهولة بمكان، فلا يغرنك الإسم
سُميت هذه الخوارزمية بهذا الإسم لأنها تعتمد على مبدأ إختيار أصغر عنصر بالمصفوفة في كل مرة و وضعه في مكانه الصحيح، و لنعرف الطريقة تفصيلاً نُجزئها إلى خطوات
طريقة عمل خوارزمية الترتيب بالإختيار
ابحث عن أصغر عنصر بالمصفوفة و بادله بأول عنصر بالمصفوفة، و المبادلة تعني أن تضع كل عنصر مكان الآخر، و إذا وجدت أن أصغر عنصر بالمصفوفة في أول خانة منها فلا داعي لإجراء تغيير، فهو في مكانه الصحيح
ابحث عن أصغر عنصر في المصفوفة ناقصاً الجزء المُرتب
لتوضيح معنى الجزء المرتب، عندما وضعت في الخطوة الأولى أصغر عنصر في الخانة الأولى فأنت تعلم أن هذا العنصر قد أخذ مكانه الصحيح و هنا نسمي الخانة الأولى بالجزء المرتب، و لإيجاد ثاني أصغر عنصر بالمصفوفة ستبحث في عناصر عددها = طول المصفوفة -1، في الخطوة الثانية يكون لديك عنصران مرتبان، الخانة الأولى و الخانة الثانية و هذان هما الجزء المرتب، و بالتالي ستبحث في عناصر عددها = طول المصفوفة -2 لوضع العنصر الثالث في مكانه
تُعيد الخطوة الثانية حتى تصل لنهاية المصفوفة، بتعبير آخر، يصبح طول الجزء المرتب من المصفوفة مساوياً لطول المصفوفة
مثال لخوارزمية الترتيب بالإختيار
الخطوة 0
تُعبرة عن حال المصفوفة قبل الترتيب
يجب أن تضع مؤشر البحث في أول 2 رقم مُعتبراً أنه أصغر رقم
تنتقل إلى الخانات التالية 6،4،5،3،1 واحدة تلو الأخرى
إذا وجدت رقماً أصغر من الذي يوجد عليه المؤشر 2 تضع عليه المؤشر و تواصل البحث حتى تصل لنهاية المصفوفة
عندما تصل لنهاية المصفوفة تستبدل الرقم حيث المؤشر 1 مع الرقم الأول 2
الخطوة 1
تبدأ عملية البحث من الخانة الثانية حيث الرقم 6 و تعتبره أصغر رقم بوضع المؤشر عليه
تقارن بينه و بين الرقم التالي 4، و لأن 4 < 6 تضع عليها المؤشر كأصغر رقم
تنتقل للرقم التالي 5، لن تُجري عملية لأن 5>4
تنتقل للرقم 3، تضع المؤشر على الرقم 3 لأن 3<4
تنتقل للرقم 2 و تضع المؤشر على الرقم 2 لأن 2<3
بإنتهاء المصفوفة تبديل الرقم حيث المؤشر 3 مع أول خانة في الجزء غير المرتب 6
الخطوة 2: تبديل أصغر رقم 3 مع أول خانة 4
الخطوة 3: تبديل أصغر رقم 4 مع أول خانة 5
الخطوة 4: الرقم 5 هو أصغر رقم، لا يوجد إجراء مطلوب
الخطوة 5: الرقم 6 هو أصغر رقم، لا يوجد إجراء مطلوب
الخطوة 6: المصفوفة مرتبة
والان الى الكود التقريبي
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)
