במאמר זה, נדון באלגוריתם מיון הספירה. ספירת מיון היא טכניקת מיון המבוססת על המפתחות בין טווחים ספציפיים. בקידוד או ראיונות טכניים למהנדסי תוכנה, אלגוריתמי מיון נשאלים רבות. לכן, חשוב לדון בנושא.
טכניקת מיון זו אינה מבצעת מיון על ידי השוואת אלמנטים. הוא מבצע מיון על ידי ספירת אובייקטים בעלי ערכי מפתח ברורים כמו hashing. לאחר מכן, הוא מבצע כמה פעולות אריתמטיות כדי לחשב את מיקום האינדקס של כל אובייקט ברצף הפלט. מיון ספירה אינו משמש כאלגוריתם מיון למטרות כלליות.
ספירת מיון יעילה כאשר הטווח אינו גדול ממספר האובייקטים שיש למיין. ניתן להשתמש בו כדי למיין את ערכי הקלט השליליים.
עכשיו, בואו נראה את האלגוריתם של מיון ספירה.
אַלגוֹרִיתְם
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מחקר ופיתוחעמדה.
java ו-swing
כעת, אחסן את הסכום המצטבר של לספור אלמנטים של מערך. זה יעזור למקם את האלמנטים באינדקס הנכון של המערך הממוין.
באופן דומה, הספירה המצטברת של מערך הספירה היא -
4. כעת, מצא את האינדקס של כל רכיב של המערך המקורי
לאחר הנחת האלמנט במקומו, הקטן את הספירה שלו באחד. לפני הצבת רכיב 2, הספירה שלו הייתה 2, אך לאחר הצבתו במיקום הנכון, הספירה החדשה של רכיב 2 היא 1.
באופן דומה, לאחר המיון, רכיבי המערך הם -
כעת, המערך ממוין לחלוטין.
ספירת מורכבות המיון
כעת, בואו נראה את מורכבות הזמן של מיון ספירה במקרה הטוב, במקרה הממוצע, ובמקרה הגרוע ביותר. נראה גם את מורכבות החלל של מיון הספירה.
1. מורכבות זמן
| מקרה | זְמַן | מוּרכָּבוּת |
|---|---|---|
| המקרה הטוב ביותר | O(n + k) | |
| מקרה ממוצע | O(n + k) | |
| במקרה הגרוע ביותר | O(n + k) |
בכל המקרים שלעיל, מורכבות הזמן של מיון הספירה זהה. הסיבה לכך היא שהאלגוריתם עובר n+k פעמים, ללא קשר לאופן שבו האלמנטים ממוקמים במערך.
מיון ספירה עדיפה על טכניקות המיון המבוססות על השוואה מכיוון שאין השוואה בין אלמנטים במיון ספירה. אבל, כאשר המספרים השלמים גדולים מאוד, מיון הספירה גרוע מכיוון שיש ליצור מערכים בגודל זה.
2. מורכבות החלל
| מורכבות החלל | O(max) |
| יַצִיב | כן |
- מורכבות החלל של מיון ספירה היא 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;></=> תְפוּקָה
אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.
מאמר זה לא היה מוגבל רק לאלגוריתם. דנו גם בספירת מורכבות המיון, עבודה והטמעה בשפות תכנות שונות.