מיון מנייה

מיון מנייה (counting sort) הוא אלגוריתם למיון מספרים טבעיים בטווח חסום. הרעיון פשוט: לסרוק את כל האיברים ולמנות את מספר ההופעות של כל ערך.

הכנס את הקלט למערך A והכן מערך תוצאה B. בונים מערך עזר C בגודל k, מאופס. עולים על A ומוסיפים ל-C את מספר ההופעות של כל ערך. לאחר הספירה, C[i] מכיל כמה פעמים הופיע הערך i.
לאחר מכן מחשבים סכום מצטבר על C, כך שכל C[i] ישמור כמה איברים קטנים או שווים ל-i. לבסוף עוברים על A מהסוף להתחלה. לכל A[i] מניחים את הערך במקום המתאים ב-B לפי C ואז מפחיתים את C[A[i]]. המעבר מהסוף שומר על הסדר היחסי של איברים שווים, ולכן המיון יציב (יציב = אינו משנה את הסדר בין איברים זהים).

זמן הריצה תלוי גם במספר הפריטים n וגם בטווח k. במילים פשוטות, זמן העבודה הוא בערך O(n+k). אם k הוא בגודל שווה לגודל הקלט או קטן ממנו, כלומר k=O(n), זמן הריצה יהיה O(n). זו תוצאה טובה יותר ממיונים המבוססים על השוואות, שהמינימום האסימפטוטי שלהם הוא O(n log n).
ניתן להתמודד עם טווחים גדולים על ידי שימוש במיון בסיס (radix sort). למשל, עבור טווח של n^2 אפשר להמיר את המספרים לבסיס n כך שמספר הספרות קטן, ואז להשתמש במיון מנייה על הספרות.
המיון עובד גם על קבוצות אחרות שיש להן יחס סדר מלא, אם ממצים התאמה חד-חד ערכית לערכים של המערך C.

קיימות גרסאות מקבילות של מיון מנייה. בגרסאות כאלה משתמשים במערך עזר גדול יותר ובמספר מעבדים בהתאם, וניתן להשיג זמני ריצה לוגריתמיים בתנאים מתאימים.

מיון מנייה הוא שיטה למיין מספרים על ידי ספירה. קודם בונים רשימה בשם C, שמתחילה מאפסים. עוברים על כל המספרים וסופרים כמה פעמים כל מספר מופיע. אחר כך עושים סכום מצטבר ב-C כדי לדעת היכן לשים כל מספר.

בשלב האחרון שמים את המספרים ברשימה B לפי המיקומים ש-C קבע. שמים מהסוף להתחלה כדי לשמור על סדר בין פריטים שווים. זה אומר שהמיון "יציב", הוא שומר על הסדר של פריטים זהים.

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

יש גם גרסאות שמריצים את הספירה וההצבה בזמנים מקבילים, כדי לעזור כשהרשימה מאוד גדולה.