מיון בסיס (Radix Sort)

Radix Sort - מיון בסיס, הוא האלגוריתם ששימש את ממיינות הכרטיסים, מכונות שניתן לראותן כיום רק במוזיאונים למחשבים. הכרטיסים מחולקים ל 80 עמודות, ובכל אחת מהן ניתן לנקב חור באחד מ 12 מקומות. עבור ספרות עשרוניות יש צורך ב 10 מקומות בלבד בכל עמודה (שני המקומות הנוספים משמשים לקידוד תווים שאינם ספרות). מספר בן d ספרות יתפוס שדה בן d עמודות. ומכיוון שהממיינת יכולה לבחון בכל פעם רק עמודה אחת, הרי שלפתרון בעיית מיונם של n כרטיסים, שמקודדים בהם מספרים בני d ספרות, נדרש אלגוריתם מיון.

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

מיון בסיס (Radix Sort) פותר את בעיית מיון הכרטיסים באופן הנוגד את האינטואיציה שהזכרנו למעלה. תחילה הוא ממיין על פי הספרה האחרונה (הכי פחות משמעותית). אז הוא מצרף את הכרטיסים לחבילה אחת, אשר בה הכרטיסים מתא 0 מונחים מעל לכרטיסים מתא 1, שמונחים מעל לכרטיסים מתא 2, וכך הלאה. לאחר מכן הוא ממיין שוב את החבילה כולה על פי הספרה שלפני האחרונה, ומצרף את הכרטיסים כמו קודם. תהליך זה נמשך עד שהוא גומר למיין את הכרטיסים על פי כל d הספרות. באופן מפתיע, בשלב זה הכרטיסים כולם ממוינים על פי המספר בן d הספרות. תהליך מיון זה סורק את חבילת הכרטיסים d פעמים.

שימו לב, באלגוריתם זה המיונים על פי הספרות השונות חייבים להיות יציבים.

Radix Sort Algorithm

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

 

הקוד של האלגוריתם ב פסאודו קוד

RADIX-SORT(A, d)
for i <- 1 to d
    use a stable sort to sort array A on digit i

הקוד עבור מיון בסיס הוא פשוט ומיידי, הפונ’ למעלה מניחה שכל איבר במערך A שגודלו n הוא בן d ספרות, כאשר הספרה שמספרה הסידורי 1 היא הספרה הכי פחות משמעותית והספרה שמספרה הסידורי d היא המשמעותית ביותר.

 

הסבר מופשט:
תנאי הכרחי לא

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

  • כמו שציינתי בעבר, במדעי המח

    1. נקבל מערך: { 30, 10, 9, 6, 5, 4, 3, 1 }. A זהו מצביע למערך, p זה מצביע לתחילת המערך (תא מס’ 0), r מצביע לסוף המערך (תא מס’ 7), ו x זהו הערך שאנחנו מחפשים, בואו ניקח לדוגמה את 10.
    2. שורה 2: אם r < p אז.., מכיוון

סיבוכיות זמן ריצה: ((O(n*d בהינתן n מספרים בני d ספרות.

סיבוכיות מקום: תלויה במיון היציב בו אנו משתמשים.