מיון מנייה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Luckas-bot (שיחה | תרומות) מ r2.7.1) (בוט מוסיף: sk:Counting sort |
|||
שורה 4:
שדה האיברים שיש למיין כולל ערכים שהם מספרים טבעיים בטווח <math>\ 1 , \dots , k</math>. מערך המקור, אותו יש למיין, ייקרא <math>\ A</math>, ומערך המטרה, לתוכו תישמר תוצאת המיון, ייקרא <math>\ B</math>.
יוצרים מערך <math>\ C</math> בעל <math>\ k</math> תאים מאופסים. עוברים על מערך <math>\ A</math> ומונים את מספר המופעים של כל איבר בו. כלומר, כאשר מגיעים לאיבר <math>\ A[i]=j</math>, אזי מבצעים את הפעולה <math>\ C[j]=C[j]+1</math>.
לאחר שהסתיים המעבר על מערך המקור, התא <math>\ C[i]</math> מכיל את מספר ההופעות של איבר <math>\ i</math> במערך <math>\ A</math>. לאחר מכן, סוכמים את מספר המופעים - מוסיפים לכל <math>\ C[i]</math> את קודמו - <math>\ C[i]=C[i]+C[i-1]</math>. באופן זה, בתא <math>\ C[i]</math> שמור מספר האיברים אשר קטנים או שווים ל-<math>\ i</math> במערך <math>\ A</math>. בשלב הבא עוברים על מערך <math>\ A</math> מהסוף להתחלה, ועל כל איבר <math>\ A[i]</math> מבצעים: #<math>\ B[C[A[i]]] = A[i] </math>
#<math>\ C[A[i]] = C[A[i]]-1</math>
| |||