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

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

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

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

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

سيعطينا التكرار النهائي قائمة مرتبة بالكامل.

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

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

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

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

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

الخطوة 2) احسب عدد أرقام العنصر الأقصى. 835 لديه 3 أرقام بالضبط.

الخطوة 3) حدد عدد التكرارات بناءً على الخطوة 2. 835 مكون من 3 أرقام، مما يعني أن عدد التكرارات سيكون 3.

الخطوة 4) تحديد قاعدة العناصر. وبما أن هذا نظام عشري، فإن الأساس سيكون 10.

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

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

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

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

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

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

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

عمل خوارزمية فرز الجذر
القائمة بعد التكرار الأول

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

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

عمل خوارزمية فرز الجذر
الفرز على أساس الأرقام في مكان العشرات

في هذا التكرار، سننظر إلى الرقم الموجود في 10th مكان لعملية الفرز.

الخطوة 1) قسّم الأعداد الصحيحة على 10. 248 مقسومًا على 10 يعطينا 24.

الخطوة 2) تعديل ناتج الخطوة 1 في 10. 24 mod 10 يعطينا 4.

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

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

عمل خوارزمية فرز الجذر
القائمة بعد التكرار الثاني

يمكنك أن ترى من الشكل الموضح أعلاه أن القائمة لم يتم فرزها بالكامل بعد، حيث أنها ليست في ترتيب تصاعدي بعد.

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

عمل خوارزمية فرز الجذر
الفرز على أساس الأرقام في مئات الأماكن

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

الخطوة 1) قسّم الأعداد الصحيحة على 100... 415 مقسومًا على 100 يعطينا 4.

الخطوة 2) قم بتعديل النتيجة من الخطوة 1 × 10. 4 mod 10 يعطينا 4 مرة أخرى.

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

عمل خوارزمية فرز الجذر
القائمة بعد التكرار الثالث

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

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

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

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 of the elements in the jthplace
   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 integers
  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

برنامج بايثون لخوارزمية فرز راديكس

#Radix Sort using 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


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

الإخراج:

[162,248,415,623,835]

معplexتحليل ity من نوع راديكس

هناك نوعان من كومplexمن المهم أن نأخذ في الاعتبار، مساحة كومplexity والوقت كومplexإيتي.

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

كوم الفضاءplexأهمية فرز الجذر

ميزتان يجب التركيز عليهما في Space complexإيتي

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

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

كوم الشاملplexوهكذا تكون O(n+b).

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

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

الوقت كومplexأهمية فرز الجذر

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

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

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

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

مقارنات نوع راديكس مع المقارنة الأخرى algorithms

كما رأينا، كوم من نوع راديكسplexتعتمد ity على حجم الكلمة أو الرقم. سيكون له نفس complexمناسبة للحالات المتوسطة والأفضل. وهذا هو O(د*(ن+ب)). كما أنها تختلف وفقًا لتقنية الفرز التي تستخدمها في المنتصف. على سبيل المثال، يمكنك استخدام الفرز العدي أو الفرز السريع لخوارزمية الفرز المتوسطة داخل الفرز الجذري.

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

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

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