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

ما هي خوارزمية فرز الجذر؟

فرز الجذر هو خوارزمية فرز غير مقارنة. يعمل عن طريق التجميعping يتم فرز الأرقام الفردية للعناصر المراد فرزها. ثم تُستخدم تقنية فرز مستقرة لتنظيم العناصر بناءً على أساسها. وهي خوارزمية فرز خطية.

تتضمن عملية الفرز الخصائص التالية:

• يتم إيجاد العنصر الأكبر وحساب عدد أرقامه. وهذا يحدد عدد مرات تكرار عملية الفرز.
• الحبوping الأرقام الفردية للعناصر في نفس الموضع المهم في كل تكرار.
• المجموعةping تبدأ العملية من الرقم الأقل أهمية وتنتهي عند الرقم الأكثر أهمية.
• فرز العناصر بناءً على الأرقام الموجودة في ذلك الموضع المهم.
• يحافظ فرز الجذر على الترتيب النسبي للعناصر التي لها نفس قيمة المفتاح. هذه الخاصية تجعله فرزًا مستقرًا.

تُعيد العملية النهائية قائمة مرتبة بالكامل.

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

قائمة الأعداد الصحيحة التي سيتم فرزها

لنقم بترتيب قائمة الأعداد الصحيحة في الشكل أعلاه بترتيب تصاعدي باستخدام خوارزمية الترتيب الجذري.

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

الخطوة 1) حدد العنصر الأكبر في القائمة. هنا هو 835.

الخطوة 2) احسب أرقامه. العدد 835 يتكون من 3 أرقام، لذا فإن عدد التكرارات هو 3.

الخطوة 3) حدد الأساس. بما أن هذا عدد عشري، فإن الأساس هو 10.

الخطوة 4) ابدأ التكرار الأول.

أ) التكرار الأول

الترتيب حسب الرقم الأخير

في التكرار الأول، نأخذ في الاعتبار القيمة المكانية للوحدة لكل عنصر.

الخطوة 1) قم بتقسيم العدد الصحيح على 10 للحصول على خانة الآحاد. على سبيل المثال، 623 بتردد 10 يعطي 3، و248 بتردد 10 يعطي 8.

الخطوة 2) استخدم فرز العد أو أي فرز مستقر آخر لترتيب الأعداد الصحيحة وفقًا لأقل رقم ذي دلالة. من الشكل، يقع العدد 248 في الخانة الثامنة، ويقع العدد 623 في الخانة الثالثة، وهكذا.

بعد التكرار الأول، تبدو القائمة الآن هكذا.

القائمة بعد التكرار الأول

لم يتم فرز القائمة بعد، وهي تتطلب المزيد من التكرارات.

ب) التكرار الثاني

الفرز على أساس الأرقام في مكان العشرات

في هذه العملية، نأخذ في الاعتبار الرقم الموجود في خانة العشرات لعملية الفرز.

الخطوة 1) اقسم الأعداد الصحيحة على 10. على سبيل المثال، 248 مقسومة على 10 تعطي 24.

الخطوة 2) قم بتعديل ناتج الخطوة 1 بضربه في 10. 24 mod 10 يعطي 4.

الخطوة 3) اتبع الخطوة 2 من التكرار السابق.

بعد التكرار الثاني، أصبحت القائمة تبدو كالتالي:

القائمة بعد التكرار الثاني

لم يتم فرز القائمة بالكامل بعد، حيث إنها ليست مرتبة تصاعدياً حتى الآن.

ج) التكرار الثالث

الفرز بناءً على الأرقام في خانة المئات

في التكرار الأخير، نريد الحصول على الرقم الأكثر أهمية. في هذه الحالة، هو خانة المئات لكل عدد صحيح في القائمة.

الخطوة 1) اقسم الأعداد الصحيحة على 100. على سبيل المثال، 415 مقسومة على 100 تعطي 4.

الخطوة 2) قم بتعديل الناتج من الخطوة 1 بضربه في 10. 4 mod 10 يعطي 4.

الخطوة 3) اتبع الخطوة 3 من التكرار السابق.

القائمة بعد التكرار الثالث

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

الكود الزائف لخوارزمية فرز الجذر

إليكم الشفرة الزائفة لخوارزمية فرز الجذر:

radixSortAlgo(arr as an array)
    Find the largest element in arr
    maximum = the element in arr that is the largest
    Find the number of digits in maximum
    k = the number of digits in maximum
    Create buckets of size 0-9 k times
    for j -> 0 to k
        Acquire the jth place of each element in arr. Here j = 0 represents the least significant digit.
        Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits in the jth place
    arr = sorted elements

C++ برنامج لتنفيذ فرز الجذر

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
    int maximum = arr[0];
    for (int i = 1; i < n; i++) {
        if (maximum < arr[i]) maximum = arr[i];
    }
    return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
    const int limit = 10;
    int result[size];
    int count[limit] = {0};
    // Calculating the count of each integer
    for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
    // Calculating the cumulative count
    for (int j = 1; j < limit; j++) {
        count[j] += count[j - 1];
    }
    // Sort the integers
    for (int j = size - 1; j >= 0; j--) {
        result[count[(arr[j] / position) % 10] - 1] = arr[j];
        count[(arr[j] / position) % 10]--;
    }
    for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
    // Get the largest element in the array
    int maximum = getMaximum(arr, size);
    for (int position = 1; maximum / position > 0; position *= 10)
        countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {162, 623, 835, 415, 248};
    int size = sizeof(arr) / sizeof(arr[0]);
    radixSortAlgo(arr, size);
    printResult(arr, size);
}

الإخراج:

162 248 415 623 835

Python برنامج لخوارزمية فرز الجذر

# Radix Sort in Python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10
    # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1
    # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]
    # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]

def radixSortAlgo(arr):
    # Acquiring the largest element in the array
    maximum = max(arr)
    # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

الإخراج:

[162, 248, 415, 623, 835]

تحليل تعقيد فرز الجذر

هناك نوعان من التعقيد يجب أخذهما في الاعتبار: التعقيد المكاني والتعقيد الزمني.

• تعقيد المساحة: O(n + b) حيث n هو حجم المصفوفة و b هو الأساس الذي تم اعتباره.
• التعقيد الزمني: O(d * (n + b)) حيث d هو عدد أرقام أكبر عنصر في المصفوفة.

تعقيد الفضاء للفرز الأساسي

هناك سمتان يجب التركيز عليهما فيما يتعلق بتعقيد المساحة:

• عدد العناصر في المصفوفة، n.
• الأساس المستخدم لتمثيل العناصر، b.

في بعض الأحيان، قد يكون هذا الأساس أكبر من حجم المصفوفة. وبالتالي، فإن التعقيد الإجمالي هو O(n + b).

قد تجعل الخصائص التالية للعناصر الموجودة في القائمة استخدام خوارزمية فرز الجذر غير فعال من حيث المساحة:

• العناصر التي تحتوي على عدد كبير من الأرقام.
• قاعدة العناصر كبيرة، مثل أرقام 64 بت.

تعقيد الوقت لفرز النظام الأساسي

باستخدام فرز العد كإجراء فرعي، تستغرق كل تكرارة O(n + b) وقت. في حالة وجود تكرارات d، يصبح إجمالي وقت التشغيل O(d * (n + b))هنا، يشير الحرف "O" إلى دالة التعقيد.

الخطية من نوع الجذر

تكون خوارزمية فرز الجذر خطية عندما:

• d ثابت، حيث d هو عدد أرقام العنصر الأكبر.
• b ليس أكبر بكثير من n.

مقارنة فرز الجذر مع أنواع الفرز الأخرى Algorithms

تعتمد تعقيدات خوارزمية فرز الجذر على حجم العدد. يبلغ تعقيد كل من أفضل الحالات والحالة المتوسطة O(d * (n + b)). يختلف الأداء باختلاف الفرز الداخلي - يُعد فرز العد هو المعيار، ولكن أي فرز مستقر يُؤدي الغرض.

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

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

• يمكن استخدام خوارزمية فرز الجذر كخوارزمية لتحديد الموقع عندما يتعلق الأمر بنطاقات كبيرة من القيم.
• يتم استخدامه لإنشاء مصفوفة لاحقة في خوارزمية DC3.
• يتم استخدامه في الآلات ذات الوصول العشوائي التسلسلي حيث يتم فهرسة السجلات بواسطة معرفات ذات عرض ثابت.

الأسئلة الشائعة