מיון סלים

$\, \bigg\Downarrow$

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

האלגוריתם

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

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