Motivation
الدرس 2 من 9 في دورة Counting Sort - سلسلة DSA على Coddy.
لا يقوم فرز العد (Counting Sort) بمقارنة عنصرين أبداً. بل يستخدم قيمهما مباشرة كفهارس في مصفوفة count، وهو ما يسمح له بالعمل في زمن خطي.
لماذا نتعلم فرز العد (Counting Sort)؟
- زمن خطي: يعمل في زمن قدره O(n + k)، حيث n هو عدد العناصر و k هو نطاق القيم. عندما تكون k صغيرة، فإن ذلك يتفوق على O(n log n).
- مستقر (عند تنفيذه بعناية): يمثل أساساً لفرز الأساس (Radix Sort)، الذي يربط عدة مراحل من فرز العد.
- فكرة مختلفة: الفرز عن طريق إحصاء القيم بدلاً من مقارنتها.
المقايضة: يتطلب ذاكرة قدرها O(k) لمصفوفة العد (count array)، لذا فهو غير مناسب عندما يكون نطاق القيم ضخماً (على سبيل المثال، فرز مجموعة صغيرة من الأرقام تصل قيمتها إلى مليار).
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
