מיון סלים

$\,{\bigg \Downarrow }$

מיון סלים או מיון דלי (באנגלית Bucket Sort) הוא מיון של קבוצת מספרים ממשיים, או כל קבוצה אחרת, כאשר ידוע שהפיזור של האיברים אחיד, ואינו מתבסס על השוואות בין האיברים. בזכות מידע נוסף זה, סיבוכיות זמן הריצה של האלגוריתם אינה חסומה מלמטה על ידי $\ \Omega (n\log n)$ (כאשר $\ n$ הוא מספר האיברים שאותם רוצים למיין) כפי שחסומים אלגוריתמים המבוססים על השוואות, אלא היא $\ O(N)$, כאשר $\ N$ הוא גודל החסם של קבוצת המספרים. לכן האלגוריתם עדיף על אלגוריתמים מבוססי השוואות במקרים שבהם גודל החסם קטן יחסית למספר האיברים שאותם רוצים למיין. מיון סלים הוא מיון יציב, כלומר לא משנה את הסדר היחסי בין איברים זהים.

האלגוריתם

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

חישוב הסיבוכיות

עבור חלוקה של n איברים לתוך m סלים, בהנחה שהפונקציה המחלקת לוקחת $\ O(1)$ לכל איבר אזי פעולת החלוקה לוקחת $\ O(N)$ זמן, במקרה הגרוע, אם פיזור האיברים אינו אחיד, לסל אחד נכנסו $\ O(N)$ איברים ומיונם ייקח $\ O(NlogN)$ והמעבר על שאר הסלים לוקח $\ O(M)$ זמן, וסה"כ לוקח $\ O(NlogN+M)$, לעומת זאת, בהנחה שאכן הפיזור אחיד, צריך למיין m תאים שבכל אחד מהם $\ O(N/M)$ איברים שלמיין כל אחד מהם לוקח $\ O((N/M)log(N/M))$,וסה"כ אחרי שמכפילים ב m תאים ומוסיפים את הסיבוכיות של החלוקה לתאים, צריך גם לקחת בחשבון גם מקרה שm הרבה יותר גדולה בסדר גודל מ$\ N$ ולוקח יותר זמן המעבר על התאים ולכן צריך לחבר לסיבוכיות $\ M$, זה לוקח $\ O(Nlog(N/M)+M)$, במקרה האידיאלי, שבו $\ M$= $\Theta \left(N\right)$ וההתפלגות אחידה הסיבוכיות היא בתוחלת$\ O(N)$.

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

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

• סימולציה של מיון סלים
• מיון סלים בQueue

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30562295מיון סלים