خوارزمية الترتيب بالإختيار: الشرح السهل مع التنفيذ

خوارزمية الترتيب بالإختيار من الخوارزميات الأساسية التي يجب معرفتها لجميع دارسي علم الخوارزميات، و ربما ستندهش من حقيقة أنك قد إبتكرت هذه الخوارزمية بنفسك و استخدمتها في حياتك كثيراً دون أن تسميها بإسمها “خوارزمية الترتيب بالإختيار”، و ستلاحظ أن طريقة عمل الخوارزمية من السهولة بمكان، فلا يغرنك الإسم 🙂 .

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

طريقة عمل خوارزمية الترتيب بالإختيار

1. ابحث عن أصغر عنصر بالمصفوفة و بادله بأول عنصر بالمصفوفة، و المبادلة تعني أن تضع كل عنصر مكان الآخر، و إذا وجدت أن أصغر عنصر بالمصفوفة في أول خانة منها فلا داعي لإجراء تغيير، فهو في مكانه الصحيح.
2. ابحث عن أصغر عنصر في المصفوفة ناقصاً الجزء المُرتب.
3. لتوضيح معنى الجزء المرتب، عندما وضعت في الخطوة الأولى أصغر عنصر في الخانة الأولى فأنت تعلم أن هذا العنصر قد أخذ مكانه الصحيح و هنا نسمي الخانة الأولى بالجزء المرتب، و لإيجاد ثاني أصغر عنصر بالمصفوفة ستبحث في عناصر عددها = طول المصفوفة -1، في الخطوة الثانية يكون لديك عنصران مرتبان، الخانة الأولى و الخانة الثانية و هذان هما الجزء المرتب، و بالتالي ستبحث في عناصر عددها = طول المصفوفة -2 لوضع العنصر الثالث في مكانه.
4. تعيد الخطوة الثانية حتى تصل لنهاية المصفوفة، بتعبير آخر، يصبح طول الجزء المرتب من المصفوفة مساوياً لطول المصفوفة.

مثال لخوارزمية الترتيب بالإختيار

[tie_list type=”checklist”]

• الخطوة 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: المصفوفة مرتبة.[/tie_list]
  

  الكود التقريبي لخوارزمية الترتيب بالإختيار

  SELECTION-SORT(A)
          for j ← 1 to n-1
  	         smallest ← j
           	 for i ← j + 1 to n
  	                  if A[ i ] < A[ smallest ]
                            smallest ← i
           	  Exchange A[ j ] ↔ A[ smallest ]

  خوارزمية الترتيب بالإختيار بلغة الجافا

  public static void SelectionSort ( int [ ] num )
  {
       int i, j, first, temp;  
       for ( i = num.length - 1; i > 0; i - - )  
       {
            first = 0;   //initialize to subscript of first element
            for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
            {
                 if( num[ j ] < num[ first ] )         
                   first = j;
            }
            temp = num[ first ];   //swap smallest found with element in position i.
            num[ first ] = num[ i ];
            num[ i ] = temp; 
        }           
  }

  بهذا نصل لختام تناولنا لخوارزمية الترتيب بالإختيار، لطفاً إذا ما وجدت أن هذه التدوينة مفيدة لا تتردد في مشاركتها مع أصدقائك و زملائك و الاطلاع علي هذه التدوينات.

  خوارزمية الترتيب الفقاعي | Bubble Sort Algorithm

  شرح خوارزمية الترتيب بالإدخال [سطر سطر]

  خوارزمية البحث الخطي Linear Search Algorithm