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