7.4 מיון-סלים (bin sort)

מבנה נתונים ואלגוריתמים

הניחו כי:

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

2. יש רק פריט אחד לכל ערך של מפתח.

אזי ניתן למיין בהתאם להליך הבא:

1. הגדרת מערך של "סלים" - אחד עבור כל ערך של מפתח.

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

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

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

אילוצי מיון-הסלים

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

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

שלב זה דורש m פעולות. לכן זמן האלגוריתם יהפוך להיות:

T(n) = c₁n + c₂m

כלומר - O(n+m). אם m<=n, מדובר כמובן ב- O(n). אולם אם m>>n, אז מדובר ב- O(m).

לדוגמא, אם אנו מעונינים למיין 10⁴ ערכים שלמים בני 32 סיביות, אזיm = 2³² ואנו זקוקים ל- 2³² פעולות (וכן לכמות זיכרון גדולה מאוד!).

עבור n = 10^4:

nlogn ~ 10⁴ x 13 ~ 2¹³ x 2⁴ ~ 2¹⁷

לכן ניתן לראות בבירור כי במקרה זה מיון-מהיר או מיון-ערמה עדיפים.

יישום אפשרי למיון-סלים ייראה כך:

 #define EMPTY -1 /* Some convenient flag */
 void bin_sort( int *a, int *bin, int n ) {
  int i;
  /* Pre-condition: for 0<=i<n : 0 <= a[i] < M */
  /* Mark all the bins empty */
  for(i=0;i<M;i++) bin[i] = EMPTY;
  for(i=0;i<n;i++)
  bin[ a[i] ] = a[i];
  }
 
 main() {
  int a[N], bin[M]; /* for all i: 0 <= a[i] < M */
  .... /* Place data in a */
   bin_sort( a, bin, N );
 

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

3. קשר בין כל הרשימות המקושרות לרשימה מקושרת אחת.

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

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

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

בהתחשב באילוץ זה, ישנה גרסה של מיון-סלים המאפשרת מיון ללא שימוש בזיכרון נוסף:

 #define EMPTY -1 /* Some convenient flag */
 void bin_sort( int *a, int n ) {
  int i;
  /* Pre-condition: for 0<=i<n : 0 <= a[i] < n */
  for(i=0;i<n;i++)
  if ( a[i] != i )
  SWAP( a[i], a[a[i]] );
  }

הדבר מבוסס על ההנחה כי ישנם n מפתחות נבדלים בטווח n-1...0. בנוסף למגבלה זו, פעולת

ה-SWAP הינה יקרה באופן יחסי, כך שגרסה זו מחליפה מקום בזמן.

אסטרטגיית מיון-הסלים עשויה להיראות מעט מוגבלת, אך היא יכולה להיות מוכללת לאסטרטגיית מיון הנקראת

מיון בסיס (radix sort).

המשך ל: מיון-בסיס (radix sort) חזור ל: תוכן עניינים