מיון (מדעי המחשב)

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

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

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

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

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

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

ישנם אלגוריתמי מיון רבים, הנבדלים זה מזה בסיבוכיות הזמן שלהם ובפשטות מימושם. כל אלגוריתמי המיון המבוססים על פעולת השוואה דורשים לפחות $\ \Omega (Nlog(N))$ פעולות השוואה על-מנת לבצעם.

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

מאחר שקיימות לכל $\ n$ איברים $\ n!$ דרכים לסדרם, הרי שמספר העלים בעץ יהיה $\ n!$ , ולפי משפט מתורת הגרפים גובה העץ (מספר ההשוואות שהאלגוריתם יאלץ לעשות לפני שיגיע לעלה) יהיה $\ lg(n!)$ . ניתן להוכיח ש- $\ lg(n!)=\Theta (nlog(n))$ (באמצעות נוסחת סטירלינג) ומכאן נובע החסם.

[עריכה] רשימת אלגוריתמי מיון

מיון בחירה (selection sort בלעז) הוא אלגוריתם השוואתי פשוט אך לא יעיל, שבו נמצא בכל צעד האיבר בעל הערך הקטן ביותר, והוא מועבר למקומו. סיבוכיות הזמן של האלגוריתם היא $\Omega\left(n^2\right)$ . מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש $\Omega\left(1\right)$ .
מיון בועות, הידוע גם בכינוי מיון החלפה הוא מיון פשוט, שבו מושווים שני איברים סמוכים במערך המתמיין. מיון זה הפועל בסיבוכיות של $\ \Theta (n^{2})$ . המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך.
מיון הכנסה (insertion sort בלעז) הוא אלגוריתם מיון השוואתי פשוט. הוא יעיל עבור מערכים קטנים ועבור מערכים ממויינים כמעט ממויינים. סיבוכיות הזמן של האלגוריתם היא $\Omega\left(n^2\right)$ .
מיון מהיר (quicksort בלעז) הוא אלגוריתם מיון השוואתי אקראי מהיר במיוחד. זהו אלגוריתם רקורסיבי הפועל בשיטת הפרד ומשול.סיבוכיות הזמן הממוצע של האלגוריתם הוא $O\left(n\log n\right)$ פעולות (כמו, למשל, מיון מיזוג (mergesort)), אך במקרה הגרוע עלול לדרוש $\Omega\left(n^2\right)$ פעולות.
מיון מיזוג הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים.
מיון מנייה הוא אלגוריתם למיון מספרים שלמים המתבסס על העובדה שהמספרים נמצאים בטווח חסום כדי לבצע את המיון בזמן מהיר יותר מזה שמסוגלים לו אלגוריתמי המיון הכלליים. בצורה אינטואיטיבית, די למיון לעבור על קבוצת האיברים שרוצים למיין ולמנות את מספר המופעים של כל אחד מהאיברים, ומכאן שמו של האלגוריתם.
מיון סלים (Bucket Sort) הוא מיון של קבוצת מספרים טבעיים, כאשר ידוע, שכל מספר בקבוצה חסום על ידי קבוע מסוים. בזכות מידע נוסף זה, סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון כללי כלשהו, אל $O\left(n\right)$ במקום $O\left(n\log n\right)$ .
מיון בסיס (Radix sort) הוא אלגוריתם למיון מספרים, המסתמך על מידע נוסף שאומר שכמות הספרות שבאמצעותן מיוצג כל מספר חסומה על ידי קבוע. (למשל: כמות הספרות של המספר 1234567 היא 7). בעזרת מידע נוסף זה, סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון כללי כלשהו, אל $O\left(n\right)$ במקום $O\left(n\log n\right)$ .
מיון חיצוני הוא שם כולל לקבוצה של אלגוריתמי מיון המסוגלים להתמודד עם כמויות גדולות של מידע. מיון חיצוני נדרש כאשר המידע שצריך למיין לא נכנס לזיכרון הראשי של המחשב (לרוב ה-RAM) ומשתמשים בהתקן זיכרון איטי יותר (לרוב דיסק קשיח).