מיון חיצוני
מתוך ויקיפדיה, האנציקלופדיה החופשית
מיון חיצוני הוא שם כולל לקבוצה של אלגוריתמי מיון המסוגלים להתמודד עם כמויות גדולות של מידע. מיון חיצוני נדרש כאשר המידע שצריך למיין לא נכנס לזיכרון הראשי של המחשב (לרוב ה-RAM) ומשתמשים בהתקן זיכרון איטי יותר (לרוב דיסק קשיח).
דוגמה נפוצה למיון חיצוני הוא מיון מיזוג חיצוני. נניח שיש לנו 900MB של מידע המאוחסנים בדיסק הקשיח שצריך למיין בשימוש של 100MB של RAM בלבד.
- קרא 100MB לזיכרון הראשי ומיין בשיטה רגילה (לרוב מיון מהיר)
- כתוב את המידע הממוין
- חזור על צעדים 1 ו-2 עד שכל המידע נמצא במנות ממוינות בגושים של 100MB. צריך עכשיו למיין אותם לקובץ אחד.
- קרא את 10MB הראשונים של כל מנה ממוינת (נקרא להם חוצצי קלט) לזכרון הראשי (90MB) והקצא את 10MB הנותרים לחוצץ הפלט.
- בצע מיזוג של 9 המנות ואתחל לאחסן את התוצאה בחוצץ הפלט. אם חוצץ הפלט מלא כותבים את תוכנו לקובץ הממוין הסופי. אם חוצץ קלט מתרוקן, קוראים אליו 10MB הבאים מהמנה הממוינת המתאימה לו.
האלגוריתם הנ"ל ניתן להכללה בצורה הבאה: נניח שהמידע למיון גדולה מכמות הזכרון הראשי בפקטור של K. אז ניצור K מנות ממוינות שצריך למזג. אם X הוא כמות הזיכרון הראשי הפנוי, אז יהיו K חוצצי קלט וחוצץ פלט אחד.כל חוצץ יהיה בגודל של (X/(K+1.
