شرح خوارزمية الفرز الجذري (Radix Sort)

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

يعتبر الفرز الجذري قويًا عند فرز الأعداد الصحيحة ذات عدد محدود من الأرقام. يرتبط ارتباطًا وثيقًا بخوارزمية فرز العد (Counting Sort) لأنها تستخدم عادةً كروتين فرعي مستقر لفرز الأرقام حسب كل خانة.

مقدمة

تقوم معظم خوارزميات الفرز بمقارنة القيم مع بعضها البعض. يقوم فرز الفقاعة (Bubble Sort) بمقارنة الجيران، وفرز التحديد (Selection Sort) يجد أصغر عنصر، وفرز الإدراج (Insertion Sort) يدرج القيم في الموضع الصحيح، وفرز السريع (Quicksort) يقسم القيم حول محور.

يستخدم الفرز الجذري استراتيجية مختلفة. لا يقارن الأرقام الكاملة مباشرة. بدلاً من ذلك، ينظر إلى الأرقام الفردية ويقوم بفرز الأرقام موضعًا رقميًا واحدًا في كل مرة.

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

ما هو الفرز الجذري (Radix Sort)؟

الفرز الجذري هو خوارزمية فرز تقوم بفرز الأرقام عن طريق معالجة خاناتها. تشير كلمة “radix” إلى أساس نظام الأرقام. في النظام العشري، الأساس هو 10 لأن الأرقام تتراوح من 0 إلى 9.

على سبيل المثال، الرقم 472 له ثلاثة مواضع رقمية:

  • خانة الآحاد: 2

  • خانة العشرات: 7

  • خانة المئات: 4

يمكن لـ Radix Sort فرز قائمة من الأرقام عن طريق الفرز أولاً وفقًا لخانة الآحاد، ثم خانة العشرات، ثم خانة المئات، وهكذا.

الفكرة الرئيسية بسيطة:

  • إيجاد أكبر عدد لمعرفة عدد المواضع الرقمية المطلوبة.

  • فرز المصفوفة حسب خانة الآحاد.

  • فرز المصفوفة حسب خانة العشرات.

  • فرز المصفوفة حسب خانة المئات.

  • المتابعة حتى تتم معالجة جميع المواضع الرقمية.

بعد معالجة جميع المواضع الرقمية باستخدام طريقة فرز مستقرة، تصبح المصفوفة مفروزة بالكامل.

لماذا يحتاج الفرز الجذري (Radix Sort) إلى فرز مستقر

يعتمد الفرز الجذري على الاستقرار. تحتفظ خوارزمية الفرز المستقرة بالترتيب النسبي للعناصر ذات المفاتيح المتساوية.

هذا مهم لأن الفرز الجذري يفرز رقمًا واحدًا في كل مرة. عند الفرز حسب رقم لاحق، يجب عدم تدمير الترتيب الذي تم إنشاؤه بواسطة فرز الأرقام السابقة.

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

لهذا السبب، تستخدم خوارزمية فرز العد (Counting Sort) بشكل شائع داخل الفرز الجذري. يمكن لـ Counting Sort المستقر فرز القيم حسب رقم معين مع الحفاظ على ترتيب الأرقام التي لها نفس الرقم.

الفرز الجذري LSD و MSD (Least Significant Digit و Most Significant Digit)

هناك مقاربتان شائعتان للفرز الجذري: الفرز الجذري للأرقام الأقل أهمية (LSD Radix Sort) والفرز الجذري للأرقام الأكثر أهمية (MSD Radix Sort).

LSD Radix Sort تعني الفرز الجذري للخانة الأقل أهمية. يبدأ من الرقم الأيمن، مثل خانة الآحاد، ثم ينتقل إلى اليسار إلى العشرات، المئات، الآلاف، والمواضع الأعلى.

MSD Radix Sort تعني الفرز الجذري للخانة الأكثر أهمية. يبدأ من الرقم الأيسر وينتقل نحو اليمين.

تركز هذه المقالة على LSD Radix Sort لأنه أسهل في الفهم ويُدرّس عادةً عند شرح الفرز الجذري باستخدام فرز العد.

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

تعالج LSD Radix Sort الأرقام من الرقم الأقل أهمية إلى الرقم الأكثر أهمية. في الأرقام العشرية، هذا يعني البدء بخانة الآحاد، ثم خانة العشرات، ثم خانة المئات، وهكذا.

تعمل الخوارزمية كالتالي:

  1. إيجاد القيمة القصوى في المصفوفة.

  2. البدء بموضع الرقم 1، الذي يمثل خانة الآحاد.

  3. فرز جميع الأرقام حسب الرقم الحالي باستخدام خوارزمية فرز مستقرة.

  4. الانتقال إلى موضع الرقم التالي بضرب قيمة الموضع في 10.

  5. التكرار حتى لا يتبقى للرقم الأقصى المزيد من الأرقام للمعالجة.

النقطة الأساسية هي أن كل خطوة فرز على مستوى الرقم يجب أن تكون مستقرة.

مثال تشغيل يدوي

دعنا نفرز المصفوفة التالية يدويًا باستخدام LSD Radix Sort:

[170, 45, 75, 90, 802, 24, 2, 66]

القيمة القصوى هي:

802

بما أن 802 يحتوي على ثلاثة أرقام، فإن Radix Sort سيعالج ثلاثة مواضع رقمية:

  • خانة الآحاد

  • خانة العشرات

  • خانة المئات

المرحلة 1: الفرز حسب خانة الآحاد

أولاً، نقوم بفرز الأرقام حسب خانة الآحاد.

Number: 170  Ones digit: 0
Number: 45   Ones digit: 5
Number: 75   Ones digit: 5
Number: 90   Ones digit: 0
Number: 802  Ones digit: 2
Number: 24   Ones digit: 4
Number: 2    Ones digit: 2
Number: 66   Ones digit: 6

الآن نقوم بتجميع الأرقام حسب خانة الآحاد مع الحفاظ على ترتيبها النسبي:

Digit 0: 170, 90
Digit 1:
Digit 2: 802, 2
Digit 3:
Digit 4: 24
Digit 5: 45, 75
Digit 6: 66
Digit 7:
Digit 8:
Digit 9:

بعد الفرز حسب خانة الآحاد، تصبح المصفوفة:

[170, 90, 802, 2, 24, 45, 75, 66]

هذه المصفوفة ليست مفروزة بالكامل بعد. تم فرزها فقط وفقًا لخانة الآحاد.

المرحلة 2: الفرز حسب خانة العشرات

الآن نفرز المصفوفة الحالية حسب خانة العشرات.

Current array:
[170, 90, 802, 2, 24, 45, 75, 66]

خانة العشرات هي:

Number: 170  Tens digit: 7
Number: 90   Tens digit: 9
Number: 802  Tens digit: 0
Number: 2    Tens digit: 0
Number: 24   Tens digit: 2
Number: 45   Tens digit: 4
Number: 75   Tens digit: 7
Number: 66   Tens digit: 6

الآن نقوم بتجميع الأرقام حسب خانة العشرات مع الحفاظ على الترتيب:

Digit 0: 802, 2
Digit 1:
Digit 2: 24
Digit 3:
Digit 4: 45
Digit 5:
Digit 6: 66
Digit 7: 170, 75
Digit 8:
Digit 9: 90

بعد الفرز حسب خانة العشرات، تصبح المصفوفة:

[802, 2, 24, 45, 66, 170, 75, 90]

المصفوفة ليست مفروزة بالكامل بعد، لكنها الآن تحترم ترتيب خانتي الآحاد والعشرات معًا لأن الفرز المستقر حافظ على المرحلة السابقة.

المرحلة 3: الفرز حسب خانة المئات

الآن نفرز المصفوفة الحالية حسب خانة المئات.

Current array:
[802, 2, 24, 45, 66, 170, 75, 90]

خانة المئات هي:

Number: 802  Hundreds digit: 8
Number: 2    Hundreds digit: 0
Number: 24   Hundreds digit: 0
Number: 45   Hundreds digit: 0
Number: 66   Hundreds digit: 0
Number: 170  Hundreds digit: 1
Number: 75   Hundreds digit: 0
Number: 90   Hundreds digit: 0

الآن نقوم بتجميع الأرقام حسب خانة المئات مع الحفاظ على الترتيب:

Digit 0: 2, 24, 45, 66, 75, 90
Digit 1: 170
Digit 2:
Digit 3:
Digit 4:
Digit 5:
Digit 6:
Digit 7:
Digit 8: 802
Digit 9:

بعد الفرز حسب خانة المئات، تصبح المصفوفة:

[2, 24, 45, 66, 75, 90, 170, 802]

المصفوفة المفروزة النهائية

[2, 24, 45, 66, 75, 90, 170, 802]

يوضح هذا التشغيل اليدوي كيف يقوم Radix Sort ببناء الترتيب النهائي تدريجياً. يقوم كل مرور بالفرز حسب موضع رقمي واحد، ويضمن الاستقرار بقاء ترتيب الأرقام السابق صحيحًا.

كيفية استخراج رقم

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

لاستخراج رقم في موضع قيمة معين:

digit = Math.floor(number / place) % 10

على سبيل المثال، للرقم 170:

  • خانة الآحاد: Math.floor(170 / 1) % 10 = 0

  • خانة العشرات: Math.floor(170 / 10) % 10 = 7

  • خانة المئات: Math.floor(170 / 100) % 10 = 1

في PHP، يمكن كتابة نفس الفكرة كالتالي:

$digit = intdiv($number, $place) % 10;

تبدأ قيمة الموضع من 1 وتُضرب في 10 بعد كل مرحلة.

خطوات خوارزمية الفرز الجذري

يمكن وصف خوارزمية LSD Radix Sort باستخدام هذه الخطوات:

  1. إيجاد القيمة القصوى في مصفوفة الإدخال.

  2. تعيين قيمة الموضع الأولية إلى 1.

  3. استخدام خوارزمية فرز مستقرة لفرز المصفوفة حسب الرقم في موضع القيمة الحالي.

  4. ضرب قيمة الموضع في 10.

  5. التكرار طالما أن القيمة القصوى مقسومة على قيمة الموضع أكبر من 0.

  6. إرجاع المصفوفة المفروزة.

عادة ما تُستخدم خوارزمية فرز العد (Counting Sort) كخوارزمية فرز أرقام مستقرة لأن كل رقم يتراوح بين 0 و 9.

شبه الكود (Pseudocode)

radixSort(array):
    max = find maximum value in array
    place = 1

    while max / place > 0:
        countingSortByDigit(array, place)
        place = place * 10

    return array

تقوم الدالة المساعدة بفرز المصفوفة وفقًا لموضع رقمي واحد:

countingSortByDigit(array, place):
    count = array of size 10 filled with 0
    output = array of same size as input

    for each number in array:
        digit = (number / place) % 10
        count[digit] = count[digit] + 1

    for i from 1 to 9:
        count[i] = count[i] + count[i - 1]

    for i from length(array) - 1 down to 0:
        digit = (array[i] / place) % 10
        position = count[digit] - 1
        output[position] = array[i]
        count[digit] = count[digit] - 1

    copy output back to array

الدالة المساعدة هي Counting Sort مستقرة مطبقة على موضع رقمي واحد.

مثال على Radix Sort في PHP

إليك تطبيق PHP نظيف لخوارزمية Radix Sort للأعداد الصحيحة غير السالبة:

<?php

function radixSort(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $max = max($numbers);

    for ($place = 1; intdiv($max, $place) > 0; $place *= 10) {
        $numbers = countingSortByDigit($numbers, $place);
    }

    return $numbers;
}

function countingSortByDigit(array $numbers, int $place): array
{
    $length = count($numbers);
    $output = array_fill(0, $length, 0);
    $count = array_fill(0, 10, 0);

    foreach ($numbers as $number) {
        $digit = intdiv($number, $place) % 10;
        $count[$digit]++;
    }

    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    for ($i = $length - 1; $i >= 0; $i--) {
        $digit = intdiv($numbers[$i], $place) % 10;
        $position = $count[$digit] - 1;

        $output[$position] = $numbers[$i];
        $count[$digit]--;
    }

    return $output;
}

$numbers = [170, 45, 75, 90, 802, 24, 2, 66];

print_r(radixSort($numbers));

الناتج سيكون:

Array
(
    [0] => 2
    [1] => 24
    [2] => 45
    [3] => 66
    [4] => 75
    [5] => 90
    [6] => 170
    [7] => 802
)

يستخدم هذا التطبيق Counting Sort المستقر لكل موضع رقمي. تحتوي مصفوفة العد على 10 مواضع فقط لأن الأرقام العشرية تتراوح من 0 إلى 9.

مثال على Radix Sort في JavaScript

إليك نفس الخوارزمية مطبقة في JavaScript:

function radixSort(numbers) {
    if (numbers.length === 0) {
        return [];
    }

    const max = Math.max(...numbers);

    for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
        numbers = countingSortByDigit(numbers, place);
    }

    return numbers;
}

function countingSortByDigit(numbers, place) {
    const output = new Array(numbers.length);
    const count = new Array(10).fill(0);

    for (const number of numbers) {
        const digit = Math.floor(number / place) % 10;
        count[digit]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = numbers.length - 1; i >= 0; i--) {
        const digit = Math.floor(numbers[i] / place) % 10;
        const position = count[digit] - 1;

        output[position] = numbers[i];
        count[digit]--;
    }

    return output;
}

const numbers = [170, 45, 75, 90, 802, 24, 2, 66];

console.log(radixSort(numbers));

الناتج سيكون:

[2, 24, 45, 66, 75, 90, 170, 802]

يتبع إصدار JavaScript نفس المنطق المستخدم في إصدار PHP. يقوم بالفرز المتكرر حسب موضع الرقم باستخدام دالة مساعدة لـ Counting Sort مستقرة.

لماذا تُستخدم Counting Sort داخل Radix Sort

تعد Counting Sort مساعدة جيدة لـ Radix Sort لأن كل رقم له نطاق ثابت وصغير. في الأعداد العشرية، يمكن أن يتراوح كل رقم فقط بين 0 و 9.

هذا يعني أن مصفوفة العد (count array) دائمًا ما تكون بحجم 10 لكل مرحلة فرز رقمي:

Digit values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

نظرًا لأن نطاق الأرقام صغير، تصبح Counting Sort فعالة جدًا داخل Radix Sort.

توفر Counting Sort أيضًا الاستقرار عند تطبيقها مع التعدادات التراكمية. هذا الاستقرار ضروري لـ Radix Sort لإنتاج الترتيب النهائي الصحيح.

التعقيد الزمني لخوارزمية Radix Sort

يصف التعقيد الزمني كيف يزداد وقت تشغيل الخوارزمية مع زيادة حجم الإدخال. يعتمد Radix Sort على عدد العناصر، وعدد المواضع الرقمية، والأساس أو النطاق المستخدم لكل رقم.

التعقيد الزمني القياسي لـ Radix Sort هو:

O(d × (n + k))

حيث:

  • n هو عدد العناصر.

  • d هو عدد المواضع الرقمية.

  • k هو نطاق قيم الأرقام الممكنة.

في LSD Radix Sort العشري، k عادة ما تكون 10 لأن الأرقام تتراوح من 0 إلى 9.

لذا بالنسبة للأعداد العشرية، غالبًا ما يُكتب هذا كالتالي:

O(d × n)

يستخدم هذا الشكل المبسط عندما يتم التعامل مع k كثابت.

لماذا Radix Sort هو O(d × (n + k))

لكل موضع رقمي، يقوم Radix Sort بإجراء Counting Sort مستقر.

تستغرق Counting Sort حسب الرقم:

O(n + k)

إذا كان أكبر رقم يحتوي على d خانات، فإن الخوارزمية تكرر هذه العملية d مرات.

لذلك، يصبح التعقيد الزمني الكلي:

O(d × (n + k))

إذا كان k ثابتًا عند 10، تصبح الصيغة قريبة من:

O(d × n)

إذا كان d صغيرًا ومحدودًا أيضًا، يمكن لـ Radix Sort أن يتصرف بالقرب من الوقت الخطي.

أفضل حالة للتعقيد الزمني

أفضل حالة للتعقيد الزمني لـ Radix Sort هي:

O(d × (n + k))

لا يزال Radix Sort يحتاج إلى معالجة كل موضع رقمي حتى لو كانت مصفوفة الإدخال مفروزة بالفعل. على عكس Insertion Sort، فإنه لا يصبح O(n) فقط لأن البيانات مرتبة بالفعل.

متوسط حالة التعقيد الزمني

متوسط حالة التعقيد الزمني هو أيضًا:

O(d × (n + k))

تتبع الخوارزمية نفس عملية الفرز رقمًا رقمًا بغض النظر عن الترتيب الأصلي للمدخلات.

أسوأ حالة للتعقيد الزمني

أسوأ حالة للتعقيد الزمني هي:

O(d × (n + k))

هذا لأن Radix Sort لا يعتمد على محاور سيئة أو مصفوفات معكوسة. يعتمد أداؤها بشكل أساسي على عدد الأرقام ونطاق الأرقام.

ومع ذلك، إذا كانت الأرقام تحتوي على العديد من الخانات، يصبح d كبيرًا. في هذه الحالة، قد يصبح Radix Sort أقل عملية.

التعقيد المكاني لخوارزمية Radix Sort

يتطلب Radix Sort عادةً ذاكرة إضافية لأن Counting Sort المستقر يستخدم مصفوفة إخراج ومصفوفة عد.

التعقيد المكاني هو:

O(n + k)

حيث n هو عدد العناصر و k هو نطاق الأرقام.

بالنسبة للأرقام العشرية، k هي 10، لذا فإن الذاكرة الإضافية الرئيسية تأتي من مصفوفة الإخراج بحجم n.

بسبب هذا، لا يعتبر Radix Sort عمومًا خوارزمية فرز في المكان (in-place) في تطبيقها المستقر الشائع.

هل Radix Sort مستقر؟

يعتبر Radix Sort مستقرًا إذا كانت خوارزمية فرز الأرقام الداخلية مستقرة.

عندما يستخدم LSD Radix Sort خوارزمية Counting Sort المستقرة، تصبح الخوارزمية بأكملها مستقرة. هذا يعني أن القيم المتساوية تحافظ على ترتيبها النسبي.

إذا لم تكن خطوة الفرز الداخلية مستقرة، فقد يفشل Radix Sort لأن عمليات تمرير الأرقام اللاحقة يمكن أن تدمر الترتيب الذي تم إنشاؤه بواسطة عمليات تمرير الأرقام السابقة.

إذن الإجابة الصحيحة هي:

  • Radix Sort مع Counting Sort المستقر: مستقر.

  • Radix Sort مع فرز رقمي غير مستقر: ليس مضمونًا أن يكون مستقرًا.

هل Radix Sort خوارزمية قائمة على المقارنة؟

Radix Sort ليست خوارزمية فرز قائمة على المقارنة. فهي لا تقوم بالفرز عن طريق مقارنة العناصر ببعضها البعض بشكل متكرر.

بدلاً من ذلك، تستخدم استخراج الأرقام والتوزيع المستقر. لهذا السبب يمكن لـ Radix Sort أن تعمل أحيانًا بشكل أسرع من الخوارزميات القائمة على المقارنة في الظروف المناسبة.

تحتوي خوارزميات الفرز القائمة على المقارنة على حد أدنى قدره O(n log n) للفرز العام. يتجنب Radix Sort هذا القيد باستخدام افتراضات حول البيانات، مثل بنية الأرقام الرقمية ونطاق الأرقام المحدود.

Radix Sort مقابل Counting Sort

ترتبط Counting Sort و Radix Sort ارتباطًا وثيقًا، لكنهما ليسا متطابقين.

تقوم Counting Sort بعد القيم الكاملة مباشرة. تعمل بشكل جيد عندما يكون نطاق القيم الكلي صغيرًا. على سبيل المثال، فرز درجات الامتحانات من 0 إلى 100 هو حالة استخدام جيدة لـ Counting Sort.

يقوم Radix Sort بفرز القيم رقمًا رقمًا. إنه مفيد عندما يكون نطاق القيم الكلي كبيرًا، ولكن كل رقم له نطاق صغير.

  • تستخدم Counting Sort القيمة بأكملها كمؤشر.

  • تستخدم Radix Sort رقمًا واحدًا في كل مرة.

  • تعقيد Counting Sort الزمني هو O(n + k).

  • تعقيد Radix Sort الزمني هو O(d × (n + k)).

  • Counting Sort أبسط.

  • يمكن لـ Radix Sort التعامل مع الأرقام الأكبر بكفاءة أكبر من Counting Sort المباشر عندما يكون النطاق ضخمًا.

من الناحية العملية، غالبًا ما يستخدم Radix Sort خوارزمية Counting Sort داخليًا.

Radix Sort مقابل Quicksort

Quicksort هي خوارزمية فرز قائمة على المقارنة. تعمل عن طريق اختيار محور وتقسيم المصفوفة حول هذا المحور.

Radix Sort هي خوارزمية لا تعتمد على المقارنة. تقوم بفرز القيم حسب المواضع الرقمية.

  • متوسط التعقيد الزمني لـ Quicksort هو O(n log n).

  • التعقيد الزمني لـ Radix Sort هو O(d × (n + k)).

  • يعمل Quicksort للعديد من أنواع البيانات القابلة للمقارنة.

  • يعمل Radix Sort بشكل أفضل للأعداد الصحيحة أو المفاتيح ذات الطول الثابت.

  • يمكن أن يكون Quicksort في مكانه (in-place).

  • يحتاج Radix Sort عادةً إلى ذاكرة إضافية.

Quicksort أكثر عمومية. Radix Sort أكثر تخصصًا، لكنها يمكن أن تكون سريعة جدًا عندما تتطابق البيانات مع افتراضاتها.

Radix Sort مقابل Merge Sort

Merge Sort هي خوارزمية فرز مستقرة قائمة على المقارنة مع تعقيد زمني مضمون O(n log n). Radix Sort لا تعتمد على المقارنة ويمكن أن تكون أسرع لبيانات الأعداد الصحيحة المناسبة.

الاختلافات الرئيسية هي:

  • يقارن Merge Sort العناصر.

  • يعالج Radix Sort الأرقام.

  • يعمل Merge Sort للقيم العامة القابلة للمقارنة.

  • يعمل Radix Sort بشكل أفضل للأعداد الصحيحة أو المفاتيح ذات الحجم الثابت.

  • التعقيد الزمني لـ Merge Sort هو O(n log n).

  • التعقيد الزمني لـ Radix Sort هو O(d × (n + k)).

  • كلاهما يتطلب عادةً ذاكرة إضافية.

Merge Sort أكثر عمومية وقابلية للتنبؤ. Radix Sort أكثر تخصصًا للبيانات ويمكن أن تكون أسرع عندما يكون عدد الأرقام محدودًا.

التعامل مع الأرقام ذات الأطوال المختلفة

يمكن لـ Radix Sort التعامل مع الأرقام ذات الأطوال المختلفة. تُعامل الأرقام الأقصر كما لو كانت تحتوي على أصفار بادئة.

على سبيل المثال:

2 can be treated as 002
24 can be treated as 024
802 stays as 802

لهذا السبب، خلال مرحلة فرز خانة المئات، فإن الأرقام مثل 2 و 24 و 45 و 90 لها خانة مئات تساوي 0.

لا تحتاج الخوارزمية إلى إضافة الأصفار فعليًا. تستعيد عملية استخراج الرقم بشكل طبيعي القيمة 0 عندما تكون قيمة الموضع أكبر من الرقم.

التعامل مع الأرقام السالبة

يعمل تطبيق Radix Sort الأساسي عادةً مع الأعداد الصحيحة غير السالبة. تتطلب الأعداد السالبة معالجة إضافية لأن استخراج الأرقام وترتيبها يصبحان أكثر تعقيدًا.

نهج شائع هو:

  1. فصل الأعداد السالبة عن الأعداد غير السالبة.

  2. تحويل الأعداد السالبة إلى قيم موجبة مؤقتًا.

  3. فرز كلتا المجموعتين بشكل منفصل.

  4. عكس ترتيب المجموعة السالبة المفروزة.

  5. إعادة تحويل القيم السالبة.

  6. دمج الأعداد السالبة أولاً، ثم الأعداد غير السالبة.

على سبيل المثال:

Input: [-10, 5, -3, 2]

Negatives as positive: [10, 3]
Sorted positives from negatives: [3, 10]
Reverse and restore signs: [-10, -3]

Non-negatives sorted: [2, 5]

Final result: [-10, -3, 2, 5]

هذا المنطق الإضافي ضروري لأن الفرز العادي رقمًا رقمًا يفترض قيمًا غير سالبة.

مثال عملي: فرز أرقام تعريف الطلاب

يعتبر Radix Sort مفيدًا عند فرز أرقام التعريف الرقمية التي تحتوي على عدد محدود من الخانات.

Student IDs:
[1203, 1045, 1002, 1320, 1111]

جميع أرقام التعريف تحتوي على أربعة أرقام. يمكن لـ Radix Sort فرزها رقمًا رقمًا:

Sorted IDs:
[1002, 1045, 1111, 1203, 1320]

هذا النوع من البيانات مناسب تمامًا لأن كل رقم له بنية رقمية يمكن التنبؤ بها.

مثال عملي: فرز رموز المنتجات

إذا كانت رموز المنتجات رقمية، يمكن استخدام Radix Sort لفرزها بكفاءة.

Product codes:
[501, 120, 305, 220, 110]

بعد Radix Sort:

[110, 120, 220, 305, 501]

ومع ذلك، إذا كانت رموز المنتجات تحتوي على أحرف أو رموز أو تنسيقات مختلطة، تحتاج الخوارزمية إلى تعيين (mapping) أو نهج مختلف.

متى يجب على المطورين استخدام Radix Sort؟

يجب على المطورين النظر في استخدام Radix Sort عندما تتناسب البيانات مع افتراضات الخوارزمية.

Radix Sort مفيدة عندما:

  • القيم هي أعداد صحيحة غير سالبة.

  • عدد الأرقام محدود.

  • نطاق الأرقام صغير.

  • الفرز المستقر مفيد.

  • حجم الإدخال كبير بما يكفي للاستفادة من السلوك الشبيه بالخطي.

  • تستخدم البيانات مفاتيح رقمية ثابتة الطول مثل أرقام التعريف أو الرموز.

عندما تكون هذه الشروط صحيحة، يمكن أن يكون Radix Sort فعالاً للغاية.

متى لا يجب استخدام Radix Sort

ليس Radix Sort هو الخيار الأفضل دائمًا.

يجب على المطورين تجنب Radix Sort عندما:

  • البيانات ليست رقمية أو لا يمكن ربطها بوضوح بالأرقام.

  • الأرقام تحتوي على عدد كبير جدًا من الخانات.

  • يجب أن يكون استخدام الذاكرة منخفضًا جدًا.

  • مجموعة البيانات صغيرة والفرز المدمج أبسط.

  • يصبح التنفيذ أكثر تعقيدًا مما تتطلبه المشكلة.

  • مفتاح الفرز هو مقارنة كائن معقد.

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

أخطاء شائعة عند تطبيق Radix Sort

يحتوي Radix Sort على أجزاء متحركة أكثر من الخوارزميات البسيطة، لذا غالبًا ما يرتكب المبتدئون أخطاء في استخراج الأرقام، أو شروط الحلقات، أو الاستقرار.

الأخطاء الشائعة تشمل:

  • استخدام طريقة فرز غير مستقرة لكل مرحلة رقمية.

  • نسيان معالجة جميع المواضع الرقمية.

  • استخراج الرقم الخاطئ.

  • استخدام شرط حلقة خاطئ للقيمة القصوى.

  • تجاهل الأرقام ذات الأطوال المختلفة.

  • محاولة فرز الأعداد السالبة بدون معالجة إضافية.

  • الخلط بين Radix Sort و Counting Sort.

  • نسيان أن مصفوفة العد (count array) للأرقام العشرية يجب أن تحتوي على 10 مواضع.

الخطأ الأكثر أهمية هو تجاهل الاستقرار. بدون فرز رقمي مستقر، قد ينتج LSD Radix Sort نتائج غير صحيحة.

قائمة تحقق عملية لفهم Radix Sort

قبل الانتقال إلى خوارزميات فرز أكثر تقدمًا، يجب أن يكون المطورون قادرين على الإجابة عن هذه الأسئلة:

  • ماذا تعني كلمة "radix"؟

  • ما هو الفرق بين LSD و MSD Radix Sort؟

  • لماذا تبدأ LSD Radix Sort من خانة الآحاد؟

  • لماذا يحتاج Radix Sort إلى فرز مستقر؟

  • كيف تساعد Counting Sort في Radix Sort؟

  • كيف نستخرج رقمًا من عدد؟

  • لماذا التعقيد الزمني هو O(d × (n + k))؟

  • لماذا لا يكون Radix Sort عادةً في المكان (in-place)؟

  • متى يكون Radix Sort أفضل من الفرز القائم على المقارنة؟

إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم المنطق الحقيقي وراء Radix Sort بدلاً من مجرد حفظ الكود.

مزايا Radix Sort

يتمتع Radix Sort بالعديد من المزايا عند استخدامه مع البيانات المناسبة.

  • يمكن أن يكون أسرع من الخوارزميات القائمة على المقارنة ذات التعقيد O(n log n) في الحالات المناسبة.

  • لا يعتمد على مقارنات العناصر المباشرة.

  • يعمل بشكل جيد للأعداد الصحيحة ذات طول رقمي محدود.

  • يمكن أن يكون مستقرًا عند تطبيقه باستخدام Counting Sort مستقر.

  • مفيد لفرز أرقام التعريف والرموز والمفاتيح الرقمية ذات الطول الثابت.

  • يعلم أفكارًا مهمة مثل معالجة الأرقام والفرز الفرعي المستقر.

هذه المزايا تجعل Radix Sort خوارزمية مهمة في تعليم هياكل البيانات والخوارزميات.

عيوب Radix Sort

يحتوي Radix Sort أيضًا على قيود مهمة.

  • ليست خوارزمية فرز للأغراض العامة لجميع أنواع البيانات.

  • تتطلب عادةً ذاكرة إضافية.

  • أكثر تعقيدًا من خوارزميات الفرز البسيطة.

  • تتطلب معالجة خاصة للأرقام السالبة.

  • قد لا تكون فعالة عندما تحتوي الأرقام على العديد من الخانات.

  • تعتمد على خوارزمية فرز داخلية مستقرة.

Radix Sort قوية، ولكن فقط عندما تكون بنية البيانات وتنسيق القيمة مناسبين.

الخلاصة

الفرز الجذري (Radix Sort) هو خوارزمية فرز لا تعتمد على المقارنة، تقوم بفرز الأرقام رقمًا رقمًا. في LSD Radix Sort، تبدأ الخوارزمية من الرقم الأقل أهمية وتنتقل نحو الرقم الأكثر أهمية.

تستخدم الخوارزمية عادةً Counting Sort المستقر كدالة مساعدة لكل موضع رقمي. الاستقرار ضروري لأن كل مرحلة يجب أن تحافظ على الترتيب الذي تم إنشاؤه بواسطة مراحل الأرقام السابقة.

التعقيد الزمني لـ Radix Sort هو O(d × (n + k))، حيث n هو عدد العناصر، و d هو عدد المواضع الرقمية، و k هو نطاق الأرقام. بالنسبة للأعداد العشرية، k عادة ما تكون 10، مما يجعل Radix Sort فعالاً عندما يكون عدد الأرقام محدودًا.

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

بالنسبة للمطورين الذين يتعلمون الخوارزميات، يعتبر Radix Sort ذا قيمة لأنه يقدم طريقة مختلفة للتفكير في الفرز. بدلاً من مقارنة القيم الكاملة، فإنه يستخدم الأرقام، والفرز المستقر، والمرات المتكررة لإنتاج نتيجة مفروزة بالكامل. كما يعزز فهم Radix Sort فهم المطور لـ Counting Sort، والاستقرار، والخوارزميات غير القائمة على المقارنة.