الترتيب بالاختيار

يرتب الترتيب بالاختيار القائمة كما يرتب كثيرون أوراق اللعب في أيديهم: ابحث عن الأصغر وضعه أولًا، ثم ابحث عن الأصغر بين البقية. يجري مقارنات كثيرة لكن تبديلات قليلة جدًا، ولا يكاد وقت تشغيله يتأثر بترتيب القائمة.

أعمدة بارتفاعات مختلفة قيد الترتيب، والجزء المرتب في بداية القائمة، وأصغر عمود متبقٍ مميز، وسهم يُظهر انتقاله بالتبديل إلى مكانه
أعمدة بارتفاعات مختلفة قيد الترتيب، والجزء المرتب في بداية القائمة، وأصغر عمود متبقٍ مميز، وسهم يُظهر انتقاله بالتبديل إلى مكانه

الفكرة

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

مثال

خذ 5, 1, 4, 2, 8. تمسح الجولة الأولى القيم الخمس كلها، فتجد أن 1 هي الأصغر، وتبدّلها مع 5: 1, 5, 4, 2, 8. تمسح الجولة الثانية 5, 4, 2, 8، فتجد 2 وتبدّلها مع 5: 1, 2, 4, 5, 8. تجد الجولة الثالثة أن 4 في مكانها أصلًا، والرابعة أن 5 في مكانها أصلًا، فلا يتحرك شيء. هذه 4 + 3 + 2 + 1 = 10 مقارنات وتبديلان فقط. أما الترتيب الفقاعي فيحتاج إلى 4 تبديلات على القائمة نفسها.

عدد المقارنات ثابت دائمًا

للتأكد من أصغر قيمة، يجب أن ينظر المسح في كل قيمة متبقية. تجري الجولة 1 عدد n − 1 مقارنة، والجولة 2 عدد n − 2، وهكذا حتى 1، والمجموع n(n − 1)/2. لا يعتمد هذا العدد على القائمة: القائمة المرتبة تكلّف عدد المقارنات نفسه تمامًا الذي تكلّفه القائمة المعكوسة. ليس للترتيب بالاختيار توقف مبكر، لأن المسح الذي يجد أصغر قيمة في المقدمة أصلًا لم يعرف شيئًا عن البقية.

تبديلات قليلة

تجري كل جولة تبديلًا واحدًا على الأكثر، لذا لا يتجاوز الترتيب بالاختيار n − 1 تبديل، ويتخطى التبديل إذا كانت أصغر قيمة في مكانها أصلًا. أما الترتيب الفقاعي والترتيب بالإدراج فيجريان تبديلات بعدد الأزواج غير المرتبة، وقد يبلغ ذلك نحو n²/2. وحين تكون كتابة قيمة أعلى كلفة بكثير من قراءة قيمتين، كما في الذاكرة التي تبلى مع كل كتابة، تصبح قلة التبديلات ميزة.

غير مستقر

يكون الترتيب مستقرًا إذا حافظت القيم المتساوية على ترتيبها الأصلي. والترتيب بالاختيار ليس كذلك، لأن التبديل لمسافة بعيدة قد ينقل قيمة متجاوزًا قيمة مساوية لها. في 2, 2, 1 تبدّل الجولة الأولى الـ 2 الأولى مع 1، فتنتج 1, 2, 2 وقد انعكس ترتيب الرقمين 2. أما النسخة التي تزيح القيم الواقعة بينهما بدلًا من التبديل فهي مستقرة، لكنها تنقل قيمًا أكثر بكثير.

جرّبه بنفسك

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

الأسئلة المتداولة

ما التعقيد الزمني للترتيب بالاختيار؟

O(n²) في كل الحالات: n(n − 1)/2 مقارنة بالضبط لـ n قيمة، مهما كان ترتيبها. يجري n − 1 تبديل على الأكثر ولا يحتاج إلا إلى ذاكرة إضافية O(1).

ما الفرق بين الترتيب بالاختيار والترتيب الفقاعي؟

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

هل الترتيب بالاختيار مستقر؟

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

ما علاقة الترتيب بالكومة بالترتيب بالاختيار؟

الترتيب بالكومة هو ترتيب بالاختيار بطريقة أسرع لإيجاد القيمة التالية: يحفظ الجزء غير المرتب في كومة، فيستغرق كل اختيار نحو log n خطوة بدلًا من مسح كامل. وهذا يخفض الإجمالي إلى O(n log n).

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب الترتيب بالاختيار