מיון בסיס – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־10:47, 16 באפריל 2015

מיון בסיס (Radix sort) הוא אלגוריתם מיון של מספרים המסתמך על כך שמספר הספרות בייצוג המספרים חסום על ידי קבוע. (למשל: מספר הספרות בייצוג המספר 1234567 הוא 7).

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

מיון הבסיס מתבצע בדרך כלל בזמן ריצה של $\ O(n*k)$ , כאשר n הוא גודל הקלט ו-k הוא מספר הספרות המקסימלי בכל מספר.

מהלך האלגוריתם

(הדוגמה הבאה מתייחסת למספרים המיוצגים בבסיס 10, כך שכל ספרה קטנה מ-10. ניתן להכליל זאת בקלות לבסיס 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 מעברים על כל המספרים.

זמן ריצה

עקרונית, זמן הריצה של האלגוריתם הוא $\ O(k*(n+d))$ , כאשר n הוא כמות המספרים בקלט, k הוא מספר הספרות המקסימלית בכל מספר ו-d הוא הבסיס בו המספרים נתונים. עם זאת, לרוב המספרים נתונים בבסיס ידוע, כך שלכל בסיס שהוא מתקיים $\ d=O(1)$ ולכן זמן הריצה יהיה $\ O(n*k)$ .

אם גודל הקלט, כלומר מספר המספרים שיש למיין, הוא מאותו סדר גודל של מספר הספרות, כלומר $\ k=O(n)$ , זמן הריצה יהיה $\ O(n)$ ^{[דרושה הבהרה]}, כאשר זמן הריצה המינימלי למיון $\ n$ מספרים ללא הנחות כלשהן הוא $\ O(nlog(n))$ .

חשוב לשים לב שלא בכל המקרים $\ O(n*k)<O(n*log(n))$ , והדבר תלוי ביחס שבין גודל הקלט למספר הספרות בכל מספר (לדוגמה, שני מספרים בעלי 10 ספרות עשרוניות ימוינו מהר יותר במיון מיזוג מאשר במיון בסיס).

קישורים חיצוניים

ראו גם

@@ שורה 27: / שורה 27: @@
 עם זאת, לרוב המספרים נתונים בבסיס ידוע, כך שלכל בסיס שהוא מתקיים <math>\ d=O(1)</math> ולכן זמן הריצה יהיה <math>\ O(n*k)</math>.
-אם גודל הקלט, כלומר מספר המספרים שיש למיין, הוא מאותו סדר גודל של מספר הספרות, כלומר <math>\ k=O(n)</math>, זמן הריצה יהיה <math>\ O(n)</math>{{הבהרה}}, כאשר זמן הריצה המינימלי למיון <math>\ n</math> מספרים ללא הנחות כלשהן הוא <math>\ O(nlog(n))</math>.
+אם גודל הקלט, כלומר מספר המספרים שיש למיין, הוא מאותו סדר גודל של מספר הספרות, כלומר <math>\ k=O(n)</math>, זמן הריצה יהיה <math>\ O(n)</math>{{הבהרה}}<!-- דרוש תיקון -->, כאשר זמן הריצה המינימלי למיון <math>\ n</math> מספרים ללא הנחות כלשהן הוא <math>\ O(nlog(n))</math>.
 חשוב לשים לב שלא בכל המקרים <math>\ O(n*k)<O(n*log(n))</math>, והדבר תלוי ביחס שבין גודל הקלט למספר הספרות בכל מספר (לדוגמה, שני מספרים בעלי 10 ספרות עשרוניות ימוינו מהר יותר ב[[מיון מיזוג]] מאשר במיון בסיס).