מיון מנייה

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

תיאור האלגוריתם

שדה האיברים שיש למיין כולל ערכים שהם מספרים טבעיים בטווח $\ 1,\dots ,k$. מערך המקור, אותו יש למיין, ייקרא $\ A$, ומערך המטרה, לתוכו תישמר תוצאת המיון, ייקרא $\ B$.

יוצרים מערך $\ C$ בעל $\ k$ תאים מאופסים. עוברים על מערך $\ A$ ומונים את מספר המופעים של כל איבר בו. כלומר, כאשר מגיעים לאיבר $\ A[i]=j$, אזי מבצעים את הפעולה $\ C[j]=C[j]+1$. לאחר שהסתיים המעבר על מערך המקור, התא $\ C[i]$ מכיל את מספר ההופעות של איבר $\ i$ במערך $\ A$.

לאחר מכן, סוכמים את מספר המופעים - מוסיפים לכל $\ C[i]$ את קודמו - $\ C[i]=C[i]+C[i-1]$. באופן זה, בתא $\ C[i]$ שמור מספר האיברים אשר קטנים או שווים ל-$\ i$ במערך $\ A$.

בשלב הבא עוברים על מערך $\ A$ מהסוף להתחלה, ועל כל איבר $\ A[i]$ מבצעים:

1. $\ B[C[A[i]]]=A[i]$
2. $\ C[A[i]]=C[A[i]]-1$

המערך $\ B$ יהיה ממוין, והסדר בין איברים שווים נשמר, מה שגורם לכך שמיון זה יהיה מיון יציב. זאת משום שבתא $\ C[i]$ נשמר המופע האחרון המיועד של האיבר $\ i$ במערך $\ B$, ומשום שהמעבר על מערך $\ A$ היה מהסוף להתחלה.

סיבוכיות ותכונות

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

אפשר ליישם את האלגוריתם בסיבוכיות $\ O(n)$ גם כאשר טווח הערכים הוא $\ 1,\dots ,n^{2}$, כלומר לא לינארי לגודל הקלט. למשל, עבור קלט בגודל $\ n$ ותחום של $\ n^{2}$, ממירים את המספרים לבסיס $\ n$, כך שמספר הספרות המקסימלי הוא 2, ומספר התאים במערך $\ C$ הוא בסך הכל $\ n$, ולכן $\ k$ אינו $\ n^{2}$ אלא $\ n$, ואז מיישמים מיון בסיס.

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

הרחבה של האלגוריתם

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

מיון מנייה הוא חלק אינטגרלי ממיון בסיס, שמאפשר למיין גם מספרים שהטווח שלהם גדול מדי בשביל מיון מנייה רגיל.

מימוש מקבילי

ניתן לממש מיון מניה בעזרת אלגוריתם מקבילי. האלגוריתם משתמש במערך מנייה בגודל $n*d$, כאשר $n$ הוא מספר הערכים שיש למיין ו-$d$ הוא רוחבו של טווח הערכים במערך.

קיימת גרסה שמשתמשת במערך מניה בגודל n*n, ו-n^2 מעבדים (כאשר n הוא מספר הערכים שיש למיין). זמן הריצה הוא log(n).

קישורים חיצוניים

• הדגמה של מיון מנייה
• מיון מניה בQueue