الترتيب بالعد

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

أعمدة قائمة، وشريط من العدّادات يبيّن كم مرة تظهر كل قيمة، وصف مخزن مؤقت لكل قيمة فيه مقطعها الخاص
أعمدة قائمة، وشريط من العدّادات يبيّن كم مرة تظهر كل قيمة، وصف مخزن مؤقت لكل قيمة فيه مقطعها الخاص

العدّ

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

الجمع

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

الوضع

اقرأ القائمة مرة ثانية وانقل كل قيمة إلى الموضع الفارغ التالي في مقطعها. ولأن القيم تُنقل بترتيب ظهورها، تحافظ القيم المتساوية على ترتيبها الأصلي: الترتيب بالعد مستقر. انسخ المخزن المؤقت إلى القائمة، فتصبح مرتبة. ويُظهر التطبيق كل عدّاد وهو يتناقص مع وضع قيمه.

مثال

خذ 4, 1, 3, 4, 2, 1, 4. تنتهي العدّادات من 1 إلى 4 عند 2 و1 و1 و3. وبالجمع تتحدد المقاطع: القيمتان 1 في الموضعين 1 و2، والقيمة 2 في الموضع 3، والقيمة 3 في الموضع 4، والقيم 4 في المواضع من 5 إلى 7. ووضع القيم بترتيب القائمة يعطي 1, 1, 2, 3, 4, 4, 4: عُدّت 7 قيم، و14 نقلة، و4 عدّادات، ولا مقارنات.

متى تستخدمه

يزداد العمل الكلي مع n + k. فعندما تكون k صغيرة مقارنةً بـ n، مثل ألف درجة امتحان من 0 إلى 100، يكون الترتيب بالعد أسرع من أي ترتيب يعتمد على المقارنة، إذ يحتاج ذلك إلى نحو n log₂ n مقارنة. وعندما يكون النطاق واسعًا يصبح مهدرًا: بضع قيم تمتد حتى مليون تحتاج إلى مليون عدّاد. ويحل الترتيب بالأساس هذه المشكلة بتشغيل الترتيب بالعد مرة لكل خانة، فلا تحتاج كل جولة إلا إلى عشرة عدّادات. وقد وصف Harold Seward الترتيب بالعد، مع الترتيب بالأساس، عام 1954.

استكشفه

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

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

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

O(n + k) لـ n قيمة وk قيمة ممكنة، مع ذاكرة إضافية O(n + k) للعدّادات والمخزن المؤقت.

لماذا لا يكون الترتيب بالعد الأسرع دائمًا؟

لأن تكلفته تعتمد على نطاق القيم، لا على عددها فقط. فإذا كان النطاق أكبر بكثير من القائمة، بقيت معظم العدّادات عند الصفر وضاع الوقت والذاكرة.

هل يتعامل الترتيب بالعد مع الأعداد السالبة؟

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

هل الترتيب بالعد مستقر؟

نعم، ما دامت القيم تُنقل بترتيب القائمة إلى الموضع الفارغ التالي في مقطعها. والترتيب بالأساس يعتمد على ذلك.

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

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

جرّب الترتيب بالعد