RADIX SORT

RADIX SORT

שלום

אני מנסה להבין פתרון של השאלה הבאה:
צריך למיין n מספרים שלמים שכולם מהטווח שבין 0 עד n^2-1.
בזמן O(n).

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

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

ראיתי דוגמת הרצה של radix sort, שבה ממיינים רשימת מספרים באופן הבא:
ממיינים אותם לפי הספרה הפחות משמעותית (במקרה של בסיס עשרוני זו ספרת האחדות). את הרשימה שממויינת לפי ספרת האחדות, ממיינים בשלב הבא לפי ספרת העשרות, וכו'.
אני מבין למה זה עובד. אני מבין למה חשוב שמיוני הביניים יבוצעו ע"י אלגוריתם מיון יציב, אני מבין למה אם הולכים הפוך (כלומר מהספרה המשמעותית, לפחות משמעותית) זה לא יעבוד (אפשר בקלות לתת דוג' נגדיות רבות).
מה שלא ברור לי זה למה הכוונה בלעשות radix sort על בסיס n בשאלה הזו. אגב, בעברית זה נקרא מיון בסיס. לא מבין מה המשמעות של בסיסים כאן ואיך זה רלוונטי לאופן פעולת האלגוריתם..יתכן שאני בכל זאת לא מבין משהו באלגוריתם.


דבר שלישי, כתוב שכל מספר בטווח מ0 עד n^2-1 ניתן להביע
כמספר בעל 2 ספרות בבסיס n.
כלומר כל ספרה היא איזשהו ערך בטווח 0 עד n-1.
לא ברור לי למה כל ספרה אפשר להביע כמספר בעל 2 ספרות בבסיס n..לא רואה את זה..וגם לא ברור לי למה עושים את זה.
: /
מישהו יכול לעזור עם זה?
 
תשובה

בבסיס 10 למשל, הספרות של כל מספר הן בין 0 ל-9.
ספרת האחדות היא המקדם של 10 בחזקת 0.
ספרת העשרות היא המקדם של 10 בחזקת 1.
ספרת המאות היא המקדם של 10 בריבוע.
אז המספר התלת ספרתי הכי קטן בבסיס 10 הוא:
zz 0*10^0 + 0 * 10^1 + 0 * 10^2 zz
כלומר 000?

עבור בסיס n כללי:
zz 0*n^0 + 0 *n^1 +0 *n^2 zz
כלומר שוב 000?

או שאני מתבלבל?..וגם אני לא מתבלבל, עדיין לא מרגיש שאני יודע לענות על השאלות שלי :<
 

aaa123

Member
לפי ההגדרה שלהם דוקא כן בדיוק כמו שהוא מספר דו ספרתי

לפי ההגדרה שלהם.

ציטוט שלו:
"דבר שלישי, כתוב שכל מספר בטווח מ0 עד n^2-1 ניתן להביע
כמספר בעל 2 ספרות בבסיס n."

במלים אחרות לפי ההגדרה שלהם 0 ניתן להביע כמספר בעל 2 ספרות(למרות שלטעמי הוא מספר בעל ספרה אחת).

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

aaa123

Member
כוונת השאלה היתה מה המספר הכי קטן שצריך 3 ספרות כדי לייצגו

0 אפשר לייצג על ידי ספרה אחת בלבד כך שלא חייבים 3 ספרות כדי לייצגו.
 
למעלה