ترتيب انتقائي خوارزمية
خوارزمية
هذه الخوارزمية تعمل كما يلي
- إوجد العنصر الأقل قيمة في القائمة
- بدل هذا العنصر مع العنصر الأول في القائمة
- كرر الخطوتان السابقات ولكن هذه المرة إبدأ من العنصر التالي.
عمليا ستكون القائمة منقسمة إلى قسمين الجزء الأول في القائمة سيكون مرتبا بالفعل وهو الجزء الذي يتم بناءه أولاً بأول عن طريق إضافة العنصر الأصغر في البداية.
والجزء الآخر هو الجزء محل عملية الترتيب والذي يتضاءل حجمه مع الوقت.
وإليكم مثال على عملية الترتيب حيث نقوم بترتيب خمسة عناصر
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 el ent is also min el ent) */
for (j 0 j < n-1 j++)
/* find the min el ent in the unsorted a[j .. n-1] */
/* assume the min is the first el ent */
int iMin j
/* test against el ents after j to find the smallest */
for ( i j+1 i < n i++)
/* if this el ent is less, then it is the new minimum */
if (a[i] < a[iMin])
/* found new minimum r ber its index */
iMin i
if(iMin ! j)
swap(a[j], a[iMin])
Selection-Sort-Animation right صورة متحركة توضح عملية الترتيب الانتقائي
خوارزمية
الترتيب الانتقائي نوع من أنواع خوارزميات الترتيب وبالتحديد خوارزميات الترتيب في المكان ووهذه الخوارزمية من الرتبة O n2 وهو ما يجعلها طريقة مثلى في قوائم البيانات الطويلة وعموما هي أسوأ من قرينتها من الترتيب الإدخالي .
الترتيب الانتقائي مشهور بسهولته وكذلك أداءه مقارنة بقرنائه الأكثر تعقيدا خصوصا عند توافر ذاكرة محدودة.