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

ترتيب انتقائي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Arwikify.svg
هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (مايو 2016)
N write.svg
هذه مقالة جديدة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (أغسطس 2011)
صورة متحركة توضح عملية الترتيب الانتقائي

خوارزمية الترتيب الانتقائي نوع من أنواع خوارزميات الترتيب وبالتحديد خوارزميات الترتيب في المكان ووهذه الخوارزمية من الرتبة O n2 وهو ما يجعلها طريقة مثلى في قوائم البيانات الطويلة وعموما هي أسوأ من قرينتها من الترتيب الإدخالي. الترتيب الانتقائي مشهور بسهولته وكذلك أداءه مقارنة بقرنائه الأكثر تعقيدا خصوصا عند توافر ذاكرة محدودة.

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

هذه الخوارزمية تعمل كما يلي:

  1. إوجد العنصر الأقل قيمة في القائمة
  2. بدل هذا العنصر مع العنصر الأول في القائمة
  3. كرر الخطوتان السابقات ولكن هذه المرة إبدأ من العنصر التالي.

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

وإليكم مثال على عملية الترتيب حيث نقوم بترتيب خمسة عناصر:

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64   

(نلاحظ عدم وجود تغيير لإن أول رقمين هم بالفعل أصغر رقمين)

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

64 25 12 22 11

11 64 25 12 22

11 12 64 25 22

11 12 22 64 25

11 12 22 25 64

مثال بلغة C[عدل]

/* a[0] to a[n-1] is the array to sort */
int i,j;

/* advance the position through the entire array */
/*   (could do j < n-1 because single element is also min element) */
for (j = 0; j < n-1; j++) {
    /* find the min element in the unsorted a[j .. n-1] */

    /* assume the min is the first element */
    int iMin = j;
    /* test against elements after j to find the smallest */
    for ( i = j+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }

    if(iMin != j) {
        swap(a[j], a[iMin]);
    }
}

مراجع[عدل]

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

بالفقاعات · بالإختيار · بالإدراج · سريع · انتقائي · دمجي