מיון בסיס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הגמל התימני (שיחה | תרומות) ראו גם |
SilvonenBot (שיחה | תרומות) מ בוט מוסיף: fa:مرتبسازی پایهای |
||
שורה 30: | שורה 30: | ||
[[de:Radixsort]] |
[[de:Radixsort]] |
||
[[es:Ordenamiento Radix]] |
[[es:Ordenamiento Radix]] |
||
[[fa:مرتبسازی پایهای]] |
|||
[[fi:Kantalukulajittelu]] |
[[fi:Kantalukulajittelu]] |
||
[[fr:Tri par base]] |
[[fr:Tri par base]] |
גרסה מ־08:24, 16 במאי 2009
מיון בסיס (Radix sort) הוא אלגוריתם מיון של מספרים המסתמך על כך שמספר הספרות בייצוג המספרים חסום על ידי קבוע. (למשל: מספר הספרות בייצוג המספר 1234567 הוא 7).
נניח כי כל המספרים הם בטווח בגודל k, בשל הנחה זו, מתבצע מיון בסיס בזמן ריצה של . (כאשר זמן הריצה המינימלי למיון מספרים ללא הנחות כלשהן הוא )
מהלך האלגוריתם
- מיון כל המספרים בקבוצה ל־10 קבוצות, על פי ספרת האחדות שלהם.
- מיון כל המספרים מהקבוצות שהתקבלו שוב, ל־10 קבוצות, על פי ספרת העשרות של כל מספר, תוך כדי שמירה על סדר המספרים בתוך כל קבוצה, לפי המיון של השלב הקודם.
- המשך מיון המספרים על פי הספרה החשובה יותר (מאות, ואז אלפים, ואז עשרות אלפים וכן הלאה), תוך שמירת סדר המספרים בכל קבוצה לפי המיון של השלב הקודם לשלב הנוכחי.
דוגמת הרצה
נתונה קבוצת המספרים הבאה: {0, 1 ,42, 32, 33, 67, 103 ,27, 105, 85} כמות הספרות של כל המספרים חסומה על ידי 3, לכן נמיין 3 פעמים:
- על פי ספרת האחדות: {0}, {1}, {42, 32}, {33, 103}, {}, {105, 85}, {}, {67, 27}, {}, {}
- על פי ספרת העשרות: {0, 1, 103, 105}, {}, {27}, {32, 33}, {42}, {}, {67}, {}, {85}, {}
- על פי ספרת המאות: {0, 1, 27, 32, 33, 42, 67, 85}, {103, 105}, {}, {}, {}, {}, {}, {}, {}, {}
המספרים התקבלו כשהם מסודרים בסדר עולה, על ידי 3 מעברים על כל המספרים.