מיון סלים

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

מיון סלים הוא מיון יציב, כלומר הוא שומר על הסדר היחסי של איברים זהים.

משרטטים מספר תאים או "סלים" שמחלקים את הטווח של הערכים. בדרך כלל בוחרים כמות סלים שקשורה לגודל הקלט, למשל Θ(n). כל מספר מועבר לסל המתאים לפי חלוקת הערך בגודל הסל והחלק השלם (floor) של התוצאה קובע את הסל.

בהנחת אחידות, בכל סל יהיו בממוצע מספר קבוע של איברים (Θ(1)). כל סל ממויין בנפרד בעזרת אלגוריתם משני, כמו מיון הכנסה (Insertion Sort) או מיון מהיר (Quick Sort). מאחר שהסלים קטנים, המיון הפנימי מהיר.

החלוקה לסלים עולה Θ(n) זמן, כי מעבירים כל איבר לסל בפעולה יחידה. במקרה הגרוע, אם ההפצה אינה אחידה, יתכן שסל אחד יקבל כמעט את כל האיברים, ואז מיון הסל יעלה Θ(n log n), והסיבוכיות הכוללת תהיה Θ(n log n + m).

אם אכן יש אחידות ובוחרים m במקביל ל-n (m = Θ(n)), אז בכל סל יש Θ(n/m) איברים ומתקבל זמן כולל של Θ(n). לכן האלגוריתם מתאים במיוחד כאשר ההתפלגות אחידה וקיימת אפשרות להשתמש במיון קל לסלים קטנים.

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

מכירים את הרעיון של לשים פריטים בקופסאות לפי טווח? כך עובדת השיטה. מחלקים את הטווח של המספרים לכמה סלים.

כל מספר נכנס לסל לפי החלק השלמ (floor) של החלוקה. אחרי שמכניסים הכל, ממיינים כל סל בנפרד. מכיוון שהסלים קטנים, זה קל ומהיר.

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

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