اقرأ في هذا المقال
- ما هي خوارزمية الترتيب بالعد؟
- كيف تعمل خوارزمية الترتيب بالعد؟
- تعقيد الوقت لخوارزمية الترتيب بالعد
- تطبيقات خوارزمية الترتيب بالعد
- مزايا وعيوب خوارزمية الترتيب بالعد
ما هي خوارزمية الترتيب بالعد؟
خوارزمية الترتيب بالعدّ هي إحدى خوارزميات الترتيب الفعّالة للغاية والمستقرة في التعقيد الزمني، يمكن استخدامها لترتيب العناصر ضمن نطاق معين، تعتمد تقنية الترتيب هذه على تكرارات، حيث تقوم بترتيب عناصر المصفوفة عن طريق حساب عدد تكرارات كل عنصر فريد في المصفوفة (بدلاً من مقارنة العناصر)، ثم يتم تخزين العدّ في “مصفوفة مساعدة”، ويتم الترتيب عن طريق تعيين العد كمؤشر للمصفوفة المساعدة
كيف تعمل خوارزمية الترتيب بالعد؟
1- تقوم الخوارزمية أولاً، بإيجاد أكبر عنصر (لنقم بتسميته “max”) من المصفوفة المُعطاة.
2- تنشئ الخوارزمية مصفوفة بطول (max + 1)، ثم تسند لجميع عناصرها قيم ابتدائية (0)، حيث تُستخدم هذه المصفوفة لتخزين عدد التكرارات لكل عنصر في المصفوفة المُعطاه.
3- ثم تقوم بتخزين عدد تكرارات كل عنصر في المكان الخاص به في مصفوفة العدّ، على سبيل المثال، إذا كان عدد تكرارات العنصر (3) في المصفوفة هو (2)، فسيتم تخزين (2)في الموضع الثالث من مصفوفة العدّ، إذا لم يكن العنصر (5) موجودًا في المصفوفة، فسيتم تخزين (0) في الموضع الخامس من مصفوفة العدّ.
4- تُخزن الخوارزمية المجموع التراكمي لتكرارات العناصر في مصفوفة العدّ، يساعد هذا في وضع العناصر في المكان الصحيح للمصفوفة المرتبة.
5- وأخيراً، تقوم الخوارزمية بإيجاد مكان (index) كل عنصر في عناصر المصفوفة الأصلية باستخدام مصفوفة العدّ، هذا يُعطي العد التراكمي، فتضع العنصر في المكان المحسوب كما هو موضح في الشكل أدناه.
6- بعد وضع كل عنصر في موضعه الصحيح، قلل عدده بمقدار واحد.
تعقيد الوقت لخوارزمية الترتيب بالعد:
تأخذ خوارزمية الترتيب بالعدّ وقتاً للتنفيذ مقداره “O(n + k)”، حيث أن (n) هو عدد العناصر التي ستقوم الخوارزمية بترتيبها، و (k) هو أكبر قيمة ممكنة الإدخال.
تطبيقات خوارزمية الترتيب بالعد:
يتم استخدام خوارزمية الترتيب بالعدّ عندما:
- يكون هناك أعداد صحيحة صغيرة، بتكرارات متعددة.
- تكون هناك حاجة إلى تعقيد زمني خطي (Linear).
مزايا وعيوب خوارزمية الترتيب بالعد:
مزايا خوارزمية الترتيب بالعد:
- أن الخوارزمية سريعة جدًا.
- أن الخوارزمية مستقرة.
عيوب خوارزمية الترتيب بالعد:
- أن الخوارزمية غير مناسبة لترتيب مجموعات الكبيرة من البيانات.
- أن الخوارزمية غير مناسبة لترتيب قيم الـ (string).
