מיון מנייה

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] תיאור האלגוריתם

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

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

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

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

[עריכה] סיבוכיות ותכונות

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

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

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

מקור: http://he.wikipedia.org../../../%D7%9E/%D7%99/%D7%95/%D7%9E%D7%99%D7%95%D7%9F_%D7%9E%D7%A0%D7%99%D7%99%D7%94.html

קטגוריה: אלגוריתמי מיון

מיון מנייה

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

[עריכה] תיאור האלגוריתם

[עריכה] סיבוכיות ותכונות

Views

ניווט

קהילה

חיפוש

שפות אחרות