خوارزمية الترتيب الانتقائي نوع من أنواع خوارزميات الترتيب وبالتحديد خوارزميات

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

ومن ناحية أخرى، الترتيب الانتقائي مشهور بسهولته وكذلك أدائه مقارنة بقرنائه الأكثر تعقيدا خصوصا عند توافر ذاكرة محدودة.

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

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 */

خوارزمية

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

والجزء الآخر هو الجزء محل عملية الترتيب والذي يتضاءل حجمه مع الوقت.
وإليكم مثال على عملية الترتيب حيث نقوم بترتيب خمسة عناصر:
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64

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

if (a[i] < a[iMin]) {

/* found new minimum; remember its index */
iMin = i;
}
}
if(iMin != j) {
swap(a[j], a[iMin]);
}
}

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 */

مثال بـلغة C

/* a[0] to a[n-1] is the array to sort */

فرز انتقائي