في هذه المقالة، سنناقش خوارزمية الفرز الجذري. الفرز الجذري هو خوارزمية الفرز الخطي المستخدمة للأعداد الصحيحة. في فرز الجذر، يتم إجراء فرز رقم برقم يبدأ من الرقم الأقل أهمية إلى الرقم الأكثر أهمية.
تعمل عملية الفرز الجذري بشكل مشابه لفرز أسماء الطلاب حسب الترتيب الأبجدي. في هذه الحالة، هناك 26 جذرًا تم تشكيلها بسبب 26 أبجدية في اللغة الإنجليزية. في التمريرة الأولى يتم تجميع أسماء الطلاب حسب الترتيب التصاعدي للحرف الأول من أسمائهم. وبعد ذلك، في الممر الثاني، يتم تجميع أسمائهم حسب الترتيب التصاعدي للحرف الثاني من أسمائهم. وتستمر العملية حتى نجد القائمة التي تم فرزها.
تحقق bash من تعيين متغير البيئة
الآن، دعونا نرى خوارزمية فرز راديكس.
خوارزمية
radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -> 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place
العمل على خوارزمية فرز راديكس
الآن، دعونا نرى عمل خوارزمية فرز راديكس.
يتم سرد الخطوات المستخدمة في فرز فرز الجذر على النحو التالي -
- أولا، علينا أن نجد العنصر الأكبر (لنفترض الأعلى ) من المصفوفة المحددة. يفترض 'س' يكون عدد الأرقام في الأعلى . ال 'س' يتم حسابه لأننا نحتاج إلى المرور عبر الأماكن المهمة لجميع العناصر.
- بعد ذلك، انتقل إلى كل مكان مهم واحدا تلو الآخر. هنا، يتعين علينا استخدام أي خوارزمية فرز مستقرة لفرز أرقام كل مكان مهم.
الآن دعونا نرى طريقة عمل فرز الجذر بالتفصيل باستخدام مثال. لفهم ذلك بشكل أكثر وضوحًا، لنأخذ مصفوفة غير مصنفة ونحاول فرزها باستخدام فرز الجذر. سيجعل الشرح أوضح وأسهل.
في المصفوفة المحددة، أكبر عنصر هو 736 التي لديها 3 أرقام فيه. لذلك، سيتم تشغيل الحلقة حتى ثلاث مرات (أي إلى مكان مئات ). وهذا يعني أن هناك حاجة إلى ثلاث تمريرات لفرز المصفوفة.
الآن، قم أولاً بفرز العناصر على أساس أرقام مكان الوحدة (أي، س = 0 ). نحن هنا نستخدم خوارزمية فرز العد لفرز العناصر.
تمرير 1:
في التمريرة الأولى، يتم فرز القائمة على أساس الأرقام الموجودة في مكان الصفر.
بعد المرور الأول، تكون عناصر المصفوفة -
تمرير 2:
في هذا المسار، يتم فرز القائمة على أساس الأرقام المهمة التالية (أي الأرقام عند 10)ذمكان).
بعد المرور الثاني، عناصر المصفوفة هي -
مثال على سلسلة فرعية في جافا
تمرير 3:
في هذا المسار، يتم فرز القائمة على أساس الأرقام المهمة التالية (أي الأرقام عند 100)ذمكان).
بعد المرور الثالث، عناصر المصفوفة هي -
الآن، تم ترتيب المصفوفة تصاعديًا.
تعقيد فرز الجذر
الآن، دعونا نرى التعقيد الزمني لفرز Radix في أفضل الأحوال، ومتوسط الحالة، وأسوأ الحالات. سنرى أيضًا مدى التعقيد المكاني لنوع Radix.
1. تعقيد الوقت
| قضية | تعقيد الوقت |
|---|---|
| أفضل حالة | Ω(ن+ك) |
| متوسط الحالة | θ(نك) |
| الحالة الأسوأ | يا (نك) |
الفرز الأساسي هو خوارزمية فرز غير مقارنة أفضل من خوارزميات الفرز المقارن. لديها تعقيد زمني خطي أفضل من الخوارزميات المقارنة ذات التعقيد O(n logn).
2. تعقيد الفضاء
| تعقيد الفضاء | يا (ن + ك) |
| مستقر | نعم |
- التعقيد المكاني لفرز Radix هو O(n + k).
تنفيذ نوع راديكس
الآن، دعونا نرى برامج راديكس مرتبة في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ فرز Radix بلغة C.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarray(a,n); radixsort(a, n); cout<<'
after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); console.write('
after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are -
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('
after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>