מיון סלים
מתוך ויקיפדיה, האנציקלופדיה החופשית
מיון סלים (באנגלית Bucket Sort) הוא מיון של קבוצת מספרים טבעיים, כאשר ידוע, שכל מספר בקבוצה חסום על ידי קבוע מסוים שאינו מתבסס על השוואות בין האיברים. בזכות מידע נוסף זה, סיבוכיות זמן הריצה של האלגוריתם אינה חסומה מלמטה על ידי 
(כאשר 
הוא מספר האיברים שאותם רוצים למיין) כפי שחסומים אלגוריתמים המבוססים על השוואות, אלא היא 
, כאשר 
הוא גודל החסם של קבוצת המספרים. לכן האלגוריתם עדיף על אלגוריתמים מבוססי השוואות במקרים שבהם גודל החסם קטן יחסית למספר האיברים שאותם רוצים למיין.
האלגוריתם
נניח שהקבוע K חוסם את קבוצת המספרים. ניצור מערך A של מספרים שלמים בגודל K+1 (מ0 עד K), ונאתחל את כל התאים בו לאפסים.
נעבור פעם אחת על כל איבר x בקבוצת המספרים, ונבצע: A[x] <- A[x] + 1
לאחר שעברנו כך על כל איברי הקבוצה, נעבור על המערך, מהתא שמספרו "אפס" ומעלה, ונדפיס עבור כל תא [A[i, את המספר i כמספר הפעמים התואם לערך התא [A[i.
דוגמת הרצה
נקח את קבוצת המספרים: {9, 3, 6, 0, 4, 5, 7, 6}
ניצור מערך בן 10 תאים, ולאחר מעבר על כל הקבוצה נקבל: A[0]=1 A[1]=0 A[2]=0 A[3]=1 A[4]=1 A[5]=1 A[6]=2 A[7]=1 A[8]=0 A[9]=1
כעת נדפיס את המספרים, על פי ערך כל תא: {0, 3, 4, 5, 6, 6, 7, 9}
