מיון מנייה – הבדלי גרסאות

ב[[מדעי המחשב]], '''מיון מנייה''' הוא [[אלגוריתם]] [[מיון (מדעי המחשב)|מיון]] עבור [[מספר שלם|מספרים שלמים]] המתבסס על העובדה שהמספרים נמצאים בטווח חסום כדי לבצע את המיון בזמן מהיר יותר מזה שמסוגלים לו אלגוריתמי המיון הכלליים. בצורה אינטואיטיבית, די למיון לעבור על קבוצת האיברים שרוצים למיין ו[[מנייה|למנות]] את מספר המופעים של כל אחד מהאיברים, ומכאן שמו של האלגוריתם.

 

שדה האיברים שיש למיין כולל ערכים שהם מספרים טבעיים בטווח <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>\ C[A[i]] = C[A[i]]-1 </math>