מיון מנייה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

שדה האיברים שיש למיין כולל ערכים שהם מספרים טבעיים בטווח \ 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 הוא רוחבו של טווח הערכים במערך.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הדגמה של מיון מנייה