في هذه المقالة، سنناقش خوارزمية فرز العد. فرز العد هو أسلوب فرز يعتمد على المفاتيح الموجودة بين نطاقات محددة. في المقابلات التقنية أو الترميزية لمهندسي البرمجيات، يتم طرح خوارزميات الفرز على نطاق واسع. لذلك، من المهم مناقشة الموضوع.
لا تقوم تقنية الفرز هذه بالفرز عن طريق مقارنة العناصر. يقوم بإجراء الفرز عن طريق حساب الكائنات التي لها قيم أساسية مميزة مثل التجزئة. بعد ذلك، يقوم بإجراء بعض العمليات الحسابية لحساب موضع مؤشر كل كائن في تسلسل الإخراج. لا يتم استخدام فرز العد كخوارزمية فرز للأغراض العامة.
يكون فرز العد فعالاً عندما لا يكون النطاق أكبر من عدد الكائنات المطلوب فرزها. يمكن استخدامه لفرز قيم الإدخال السلبية.
الآن، دعونا نرى خوارزمية فرز العد.
خوارزمية
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
عمل خوارزمية الفرز
الآن، دعونا نرى عمل خوارزمية فرز العد.
لفهم عمل خوارزمية فرز العد، دعونا نأخذ مصفوفة غير مصنفة. سيكون من الأسهل فهم فرز العد عبر مثال.
دع عناصر المصفوفة هي -
1. ابحث عن الحد الأقصى للعنصر من المصفوفة المحددة. يترك الأعلى يكون العنصر الأقصى.
2. الآن، قم بتهيئة مجموعة من الطول الحد الأقصى + 1 وجود جميع العناصر 0. سيتم استخدام هذه المصفوفة لتخزين عدد العناصر في المصفوفة المحددة.
3. الآن، علينا تخزين عدد كل عنصر من عناصر المصفوفة في الفهرس المقابل له في مصفوفة العد.
سيتم تخزين عدد العنصر كـ - لنفترض أن عنصر المصفوفة '4' ظهر مرتين، وبالتالي فإن عدد العنصر 4 هو 2. وبالتالي، يتم تخزين 2 في 4ذموضع مصفوفة العد. إذا كان أي عنصر غير موجود في المصفوفة، ضع 0، أي لنفترض أن العنصر '3' غير موجود في المصفوفة، لذلك سيتم تخزين 0 في 3بحث وتطويرموضع.
يساوي الطريقة في جافا
الآن، قم بتخزين المبلغ التراكمي لـ عدد عناصر المصفوفة. سيساعد ذلك على وضع العناصر في الفهرس الصحيح للمصفوفة التي تم فرزها.
وبالمثل، فإن العدد التراكمي لمصفوفة العد هو -
4. الآن، ابحث عن فهرس كل عنصر من عناصر المصفوفة الأصلية
بعد وضع العنصر في مكانه، قلل عدده بمقدار واحد. قبل وضع العنصر 2، كان عدده 2، ولكن بعد وضعه في موضعه الصحيح، أصبح العدد الجديد للعنصر 2 هو 1.
وبالمثل، بعد الفرز، تكون عناصر المصفوفة -
الآن، تم فرز المصفوفة بالكامل.
حساب تعقيد الفرز
الآن، دعونا نرى التعقيد الزمني لفرز العد في أفضل الأحوال، ومتوسط الحالة، وفي أسوأ الحالات. سنرى أيضًا مدى التعقيد المكاني لفرز العد.
1. تعقيد الوقت
| قضية | وقت | تعقيد |
|---|---|---|
| أفضل حالة | يا (ن + ك) | |
| متوسط الحالة | يا (ن + ك) | |
| الحالة الأسوأ | يا (ن + ك) |
في جميع الحالات المذكورة أعلاه، يكون التعقيد الزمني لفرز العد هو نفسه. وذلك لأن الخوارزمية تمر ن + ك مرات، بغض النظر عن كيفية وضع العناصر في المصفوفة.
يعد فرز العد أفضل من تقنيات الفرز القائمة على المقارنة لأنه لا توجد مقارنة بين العناصر في فرز العد. ولكن، عندما تكون الأعداد الصحيحة كبيرة جدًا، يكون فرز العد سيئًا لأنه يجب إنشاء صفائف بهذا الحجم.
2. تعقيد الفضاء
| تعقيد الفضاء | يا (كحد أقصى) |
| مستقر | نعم |
- التعقيد المكاني لفرز العد هو O(max). كلما زاد نطاق العناصر، زاد تعقيد الفضاء.
تنفيذ فرز العد
الآن، دعونا نرى برامج الفرز في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ الفرز العدي بلغة 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; 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/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; 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/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); 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/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting 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. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> انتاج |
المصفوفات في جافا
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.
لم تقتصر هذه المقالة على الخوارزمية فقط. لقد ناقشنا أيضًا حساب تعقيد الفرز والعمل والتنفيذ بلغات برمجة مختلفة.