خوارزمية الترتيب بالجذر Radix Sort

مفهوم خوارزمية الترتيب بالجذر:

خوارزمية الترتيب بالجذر هي إحدى خوارزميات ترتيب الأعداد الصحيحة، والتي تقوم بترتيب البيانات باستخدام مفتاح العدد الصحيح، ويتم ذلك عن طريق تجميع المفاتيح حسب المنزلة الحسابية والتي تشترك في نفس الموضع والقيمة (القيمة المكانية)، فإن خوارزمية الترتيب بالجذر تستخدم الترتيب بالعد كإجراء فرعي لفرز مصفوفة من الأرقام؛ وذلك نظرًا لإمكانية استخدام الأعداد الصحيحة لتمثيل الـ (strings)، وذلك عن طريق تجزئة الـ (strings) إلى أعداد صحيحة، تعمل خوارزمية الترتيب بالجذر على أنواع البيانات المختلفة إلى جانب الأعداد الصحيحة، نظرًا لأن هذه الخوارزمية لا تعتمد على المقارنة.

تشتمل خوارزمية الترتيب بالجذر على خوارزمية الترتيب بالعد، بحيث يمكنها ترتيب أعداد أكبر وذات منازل أرقام أكثر، دون الحاجة إلى تقليل من الكفاءة عن طريق زيادة نطاق المفاتيح التي يجب أن ترتبها الخوارزمية؛ لأن هذا قد يتسبب في إهدار الكثير من الوقت.

ما هو تعقيد الوقت لخوارزمية الترتيب بالجذر؟

افرض أن (d) هي عدد منازل الأعداد الصحيحة المدخلة، يستغرق ترتيب خوارزمية الترتيب بالجذر الوقت “O(d * (n + b))”، حيث تكون (b) هي الأساس الأرقام، على سبيل المثال، بالنسبة للنظام العشري، فإن (b) هي (10)، وإذا كانت (k) هي أقصى قيمة ممكنة، فإن (d) ستكون “O(log_b(k))”، لذا فإن التعقيد الزمني الإجمالي هو “O((n+b) * log_b(k))”، الذي يبدو أكثر من التعقيد الزمني لخوارزميات الترتيب الأخرى القائمة على المقارنة (k).

دعونا نحدد قيمة (k)، افرض أنها (k <= n^c) حيث (c) ثابت، في هذه الحالة، يصبح التعقيد “O(nLog_b(n))”، لكنها ما زالت لا تتفوق على خوارزميات الفرز القائمة على المقارنة، ماذا لو جعلنا قيمة (b) أكبر؟، ماذا يجب أن تكون قيمة (b) لجعل التعقيد الزمني خطيًا؟، إذا حددنا (b) على أنه (n)، فسنحصل على التعقيد الزمني على النحو “O(n)”، بمعنى آخر، يمكننا ترتيب مصفوفة من الأعداد الصحيحة بمدى من (1 إلى n^c)، إذا تم تمثيل الأرقام للأساس (n)، أو يأخذ كل رقم “log₂(n)” بت.

كيف تعمل خوارزمية الترتيب بالجذر؟

• تقوم الخوارزمية بالبحث عن أكبر عنصر في المصفوفة (لنقم بتسميته “max”)، لنفترض أن (X) هو عدد المنازل لـ “max”، يتم حساب (X)؛ لأنه يتعين علينا المرور عبر جميع منازل جميع العناصر، في هذه المصفوفة [121 ، 432 ، 564 ، 23 ، 1 ، 45 ، 788]، لدينا أكبر رقم (788)، ويتكون من 3 منازل، لذلك، يجب أن تصل الـ (loop) إلى منزلة المئات (أي أنها ستعمل بـ 3 تكرارات).

•  الآن، انتقل إلى كل منزلة واحدًا تلو الآخر، استخدم أي أسلوب ترتيب ثابت لترتيب المنازل، لقد استخدمنا خوارزمية الترتيب المعد لهذا الغرض، بناءً على الخوارزمية، سنقوم بترتيب المصفوفة وفقًا لمنزلة الآحاد:

0:

1: 1, 121

2: 432

3: 23

4: 564

5: 45

6:

7:

8: 788

9:

تصبح المصفوفة:

• الآن، سنقوم بالترتيب وفقًا لمنزلة العشرات:

0: 1

1:

2: 121، 23

3: 432

4: 45

5:

6: 564

7:

8: 788

9:

تصبح المصفوفة:

• أخيراً، سنقوم بالترتيب وفقًا لمنزلة المئات:

0: 45، 23، 1

1: 121

2:

3:

4: 432

5: 564

6:

7: 788

8:

9:

لتصبح المصفوفة: