סטודנטלמתמטיקה
New member
RADIX SORT
שלום
אני מנסה להבין פתרון של השאלה הבאה:
צריך למיין n מספרים שלמים שכולם מהטווח שבין 0 עד n^2-1.
בזמן O.
דבר ראשון עוד בלי קשר לשאלה הזו, לא ברור לי מה הניסוח המדוייק של ההנחה ש-radix sort מניח על הקלט.
הוא מניח שטווח הערכים במערך הקלט חסום? תמיד הטווח של הערכים במערך סופי הוא חסום. כנראה שזו לא ההנחה.
חשוב לי לדעת את זה כדי להבין למה בכלל צריך ומותר לחשוב פה בכיוון של radix sort.
דבר שני, בפתרון כתוב "נבצע radix sort על בסיס n".
לא ברור לי למה עושים את זה ומה הכוונה.
ראיתי דוגמת הרצה של radix sort, שבה ממיינים רשימת מספרים באופן הבא:
ממיינים אותם לפי הספרה הפחות משמעותית (במקרה של בסיס עשרוני זו ספרת האחדות). את הרשימה שממויינת לפי ספרת האחדות, ממיינים בשלב הבא לפי ספרת העשרות, וכו'.
אני מבין למה זה עובד. אני מבין למה חשוב שמיוני הביניים יבוצעו ע"י אלגוריתם מיון יציב, אני מבין למה אם הולכים הפוך (כלומר מהספרה המשמעותית, לפחות משמעותית) זה לא יעבוד (אפשר בקלות לתת דוג' נגדיות רבות).
מה שלא ברור לי זה למה הכוונה בלעשות radix sort על בסיס n בשאלה הזו. אגב, בעברית זה נקרא מיון בסיס. לא מבין מה המשמעות של בסיסים כאן ואיך זה רלוונטי לאופן פעולת האלגוריתם..יתכן שאני בכל זאת לא מבין משהו באלגוריתם.
דבר שלישי, כתוב שכל מספר בטווח מ0 עד n^2-1 ניתן להביע
כמספר בעל 2 ספרות בבסיס n.
כלומר כל ספרה היא איזשהו ערך בטווח 0 עד n-1.
לא ברור לי למה כל ספרה אפשר להביע כמספר בעל 2 ספרות בבסיס n..לא רואה את זה..וגם לא ברור לי למה עושים את זה.
: /
מישהו יכול לעזור עם זה?
שלום
אני מנסה להבין פתרון של השאלה הבאה:
צריך למיין n מספרים שלמים שכולם מהטווח שבין 0 עד n^2-1.
בזמן O.
דבר ראשון עוד בלי קשר לשאלה הזו, לא ברור לי מה הניסוח המדוייק של ההנחה ש-radix sort מניח על הקלט.
הוא מניח שטווח הערכים במערך הקלט חסום? תמיד הטווח של הערכים במערך סופי הוא חסום. כנראה שזו לא ההנחה.
חשוב לי לדעת את זה כדי להבין למה בכלל צריך ומותר לחשוב פה בכיוון של radix sort.
דבר שני, בפתרון כתוב "נבצע radix sort על בסיס n".
לא ברור לי למה עושים את זה ומה הכוונה.
ראיתי דוגמת הרצה של radix sort, שבה ממיינים רשימת מספרים באופן הבא:
ממיינים אותם לפי הספרה הפחות משמעותית (במקרה של בסיס עשרוני זו ספרת האחדות). את הרשימה שממויינת לפי ספרת האחדות, ממיינים בשלב הבא לפי ספרת העשרות, וכו'.
אני מבין למה זה עובד. אני מבין למה חשוב שמיוני הביניים יבוצעו ע"י אלגוריתם מיון יציב, אני מבין למה אם הולכים הפוך (כלומר מהספרה המשמעותית, לפחות משמעותית) זה לא יעבוד (אפשר בקלות לתת דוג' נגדיות רבות).
מה שלא ברור לי זה למה הכוונה בלעשות radix sort על בסיס n בשאלה הזו. אגב, בעברית זה נקרא מיון בסיס. לא מבין מה המשמעות של בסיסים כאן ואיך זה רלוונטי לאופן פעולת האלגוריתם..יתכן שאני בכל זאת לא מבין משהו באלגוריתם.
דבר שלישי, כתוב שכל מספר בטווח מ0 עד n^2-1 ניתן להביע
כמספר בעל 2 ספרות בבסיס n.
כלומר כל ספרה היא איזשהו ערך בטווח 0 עד n-1.
לא ברור לי למה כל ספרה אפשר להביע כמספר בעל 2 ספרות בבסיס n..לא רואה את זה..וגם לא ברור לי למה עושים את זה.
: /
מישהו יכול לעזור עם זה?