في هذه المقالة، سنناقش خوارزمية فرز الجرافة. يتم توزيع عناصر البيانات الموجودة في فرز المجموعة على شكل مجموعات. في المقابلات التقنية أو الترميزية لمهندسي البرمجيات، يتم طرح خوارزميات الفرز على نطاق واسع. لذلك، من المهم مناقشة الموضوع.
فرز الجرافة هو خوارزمية فرز تفصل العناصر إلى مجموعات متعددة يُقال إنها دلاء. يتم أولاً تقسيم العناصر في فرز الجرافة بشكل موحد إلى مجموعات تسمى الدلاء، ثم يتم فرزها بواسطة أي خوارزمية فرز أخرى. بعد ذلك، يتم جمع العناصر بطريقة مرتبة.
يتم إعطاء الإجراء الأساسي لتنفيذ فرز الجرافة على النحو التالي -
- أولاً، قم بتقسيم النطاق إلى عدد ثابت من المجموعات.
- ثم قم برمي كل عنصر في الدلو المناسب له.
- بعد ذلك، قم بفرز كل مجموعة على حدة من خلال تطبيق خوارزمية الفرز.
- وأخيرًا، قم بتسلسل جميع الدلاء التي تم فرزها.
مزايا فرز الجرافة هي -
- نوع الجرافة يقلل من الرقم. من المقارنات.
- إنه سريع مقارب بسبب التوزيع الموحد للعناصر.
قيود نوع الجرافة هي -
- قد تكون أو لا تكون خوارزمية فرز مستقرة.
- ليس من المفيد أن يكون لدينا مجموعة كبيرة لأنها تزيد من التكلفة.
- إنها ليست خوارزمية فرز في المكان، لأن هناك حاجة إلى بعض المساحة الإضافية لفرز المجموعات.
أفضل ومتوسط تعقيد نوع الجرافة هو يا (ن + ك) ، والتعقيد الأسوأ لفرز الجرافة هو على2) ، أين ن هو عدد العناصر.
يتم استخدام نوع الجرافة بشكل شائع -
- مع قيم الفاصلة العائمة.
- عندما يتم توزيع المدخلات بشكل موحد على نطاق.
يتم إعطاء الفكرة الأساسية لتنفيذ فرز الجرافة على النحو التالي -
bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort
الآن دعونا نرى خوارزمية فرز الجرافة.
خوارزمية
Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End
نهج مبعثر وجمع
يمكننا أن نفهم خوارزمية فرز الجرافة من خلال نهج التجميع المبعثر. هنا، يتم أولاً توزيع العناصر المحددة في دلاء. بعد التشتت، يتم فرز العناصر في كل مجموعة باستخدام خوارزمية فرز مستقرة. أخيرًا، سيتم جمع العناصر التي تم فرزها بالترتيب.
لنأخذ مصفوفة غير مصنفة لفهم عملية فرز الجرافة. سيكون من الأسهل فهم نوع الجرافة من خلال مثال.
دع عناصر المصفوفة هي -
الآن، قم بإنشاء مجموعات بنطاق من 0 إلى 25. نطاق المجموعات هو 0-5، 5-10، 10-15، 15-20، 20-25. يتم إدراج العناصر في الدلاء وفقًا لنطاق الدلو. لنفترض أن قيمة عنصر ما هي 16، لذلك سيتم إدراجه في المجموعة ذات النطاق 15-20. وبالمثل، سيتم إدراج كل عنصر في المصفوفة وفقًا لذلك.
ومن المعروف أن هذه المرحلة هي تشتت عناصر المصفوفة .
الآن، نوع كل دلو على حدة. يمكن فرز عناصر كل مجموعة باستخدام أي من خوارزميات الفرز المستقرة.
أخيرا، يجتمع العناصر مرتبة من كل دلو بالترتيب
الآن، تم فرز المصفوفة بالكامل.
تعقيد فرز الجرافة
الآن، دعونا نرى التعقيد الزمني لفرز الجرافة في أفضل الأحوال، وفي الحالة المتوسطة، وفي أسوأ الحالات. سنرى أيضًا مدى تعقيد مساحة نوع الجرافة.
1. تعقيد الوقت
| قضية | وقت | تعقيد |
|---|---|---|
| أفضل حالة | يا (ن + ك) | |
| متوسط الحالة | يا (ن + ك) | |
| الحالة الأسوأ | على2) |
إذا استخدمنا فرز الإدراج لفرز عناصر الدلو، فسيكون التعقيد الإجمالي خطيًا، أي O(n + k)، حيث O(n) مخصص لصنع الدلاء، وO(k) مخصص لفرز عناصر الدلو باستخدام خوارزميات ذات تعقيد زمني خطي في أفضل الأحوال.
أفضل تعقيد زمني لنوع الجرافة هو يا (ن + ك) .
سوف يزداد التعقيد سوءًا عندما تكون العناصر بالترتيب العكسي.
أسوأ تعقيد زمني لنوع الجرافة هو على2) .
2. تعقيد الفضاء
| تعقيد الفضاء | يا (ن * ك) |
| مستقر | نعم |
- التعقيد المكاني لفرز الجرافة هو O(n*k).
تنفيذ فرز دلو
الآن، دعونا نرى برامج الفرز في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ فرز الجرافة بلغة C.
#include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are -
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are -
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are -
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are -
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>