تمارين

الإجابة

1. الجولتان الأوليان هما:

   الجولة	المصفوفة	الشرح
   1	[1, 2, 5, 4, 3]	أصغر عنصر، وهو 1، يُبدَّل مع العنصر الأول
   2	[1, 2, 5, 4, 3]	القيمة 2 موجودة بالفعل عند الفهرس 1، فلا حاجة إلى تبديل

   أصبح الموضعان الأولان ثابتين الآن. وتحتاج الجولات اللاحقة إلى إيجاد أصغر عنصر داخل [5, 4, 3] فقط.

2. قارن العناصر المتجاورة بالترتيب: بدّل 4 و2؛ لا تبدّل 4 و5؛ بدّل 5 و1؛ ثم بدّل 5 و3. وتكون النتيجة [2, 4, 1, 3, 5] بعد 3 عمليات تبديل. وقد انتقل أكبر عنصر، وهو 5، إلى نهاية المصفوفة، فأصبح الموضع الأخير ثابتاً.

الإجابة

1. في جولته الأولى، يختار ترتيب الاختيار أصغر عنصر، وهو 1، ويبدّله مع العنصر الأول $2_a$، فتنتج المصفوفة $[1, 2_b, 2_a]$. وقد تغيّر الترتيب النسبي لأن $2_a$ انتقل إلى ما بعد $2_b$.

2. يقارن ترتيب الفقاعات أولاً $2_a$ و$2_b$. ولأنهما متساويان فلا يبدّلهما. ثم يقارن $2_b$ و1 فيبدّلهما، فتنتج المصفوفة $[2_a, 1, 2_b]$ بعد الجولة الأولى. وما يزال $2_a$ قبل $2_b$، لذا لم يتغيّر ترتيبهما النسبي.

3. في هذا المثال، يغيّر ترتيب الاختيار الترتيب الأصلي للعناصر المتساوية. أما ترتيب الفقاعات فلا يبدّل العنصرين المتجاورين إلا عندما يكون العنصر الأيسر أكبر من الأيمن. ولا تُبدَّل العناصر المتساوية، فيبقى ترتيبها النسبي الأصلي محفوظاً.

الإجابة

1. رقم الهوية مكوّن من 8 خانات، لذا نحتاج إلى 8 جولات من الخانة الأقل دلالة إلى الخانة الأكثر دلالة. وتجمّع كل جولة القيم حسب 0–9 فقط.

2. سيستلزم العدّ المباشر مدخلاً لكل قيمة ممكنة من القيم ذات الخانات الثماني، لكن جزءاً صغيراً فقط من تلك القيم يُخصَّص فعلاً للطلاب. وستبقى معظم مدخلات مصفوفة العدّ مساوية للقيمة 0.

3. الترتيب الجذري هو الخيار الأفضل. فهو يستفيد من كون الطول ثابتاً وكون كل خانة لا تحتمل سوى 10 قيم ممكنة، فلا يتطلب إلا 8 جولات من التجميع المستقر. أما الترتيب العدّي، إذا استخدم رقم الهوية بكامله ذا الخانات الثماني كفهرس صحيح، فسيحتاج إلى مدخلات في مصفوفة العدّ لقيم كثيرة لا تظهر أبداً.