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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
صورة متحركة توضح عملية الترتيب الانتقائي

خوارزمية الترتيب الانتقائي نوع من أنواع خوارزميات الترتيب وبالتحديد خوارزميات الترتيب في المكان ووهذه الخوارزمية من الرتبة 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

مراجع[عدل]

وصلات خارجية[عدل]

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

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