מיון סלים

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

Bucket sort 1.png

Bucket sort 2.png

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

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

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

ניתוח סיבוכיות זמן ריצה[עריכת קוד מקור | עריכה]

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

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

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

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

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

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.