שאלה על מיון.

[mob2]

שאלה על מיון.

נתון לי מערך שהוא k sorted כלומר כל איבר בו נמצא מקסימום במרחק של קיי מקומות מן המקום שמתאים לו לו המערך היה ממוין (לצורך העניין בסדר עולה). השאלה אומרת: Show that a k-sorted array of length n can be sorted in O(n lg k) time. רמז: שימוש בmerge sort . אם מישהו יכול למצוא דרך אלגנטית זה יהיה נהדר תודה,

 

[mob2]

מישהו??

תעזרו בבקשה אנשים

 

[immortalus]

המ.. תחשוב על הבעיה ומה אתה יודע...

נסתכל על קטע המערך 0-2k. אנחנו יודעים בוודאות כי k האיברים הראשונים נמצאים בהכרח בקטע הזה. אם תמיין את הקטע 0-2k בלבד, בסיבוכיות של O(k*log(k)) d [למעשה יש שם עוד פקטור של 2 אבל הניתוח הוא אסימפטוטי ולכן........... עכשיו לאחר שמיינו את החלק הזה, אנחנו יודעים בוודאות שהסגמנט [החלק] 0 עד k יהיה ממוין! עכשיו נסתכן על הסגמנט k-3k, משיקולים דומים, האיברים k-2k חייבים להמצא בסגמנט הזה! נמיין אותו ב- O(k*log(k)) d עכשיו לאחר שמיינו את החלק הזה, אנחנו יודעים בוודאות שהסגמנט [החלק] k עד 2k יהיה ממוין! נמשיך ככה עד הסוף בעצם... קיבלנו שעשינו מספר פעמים k*log(k) dd פעולות. כמה פעמים עשינו זאת? כמספר הסגמנטים בגודל k שקיימים במערך - n/k פעמים. (שים לב שאנחנו מסתכלים בכל פעם על 2k איברים אבל בכל פעם ממינים רק k מהם למקומות הנכונים). בסה"כ קיבלנו:

O((n/k)*k*log(k)) = O(n*log(k)) מש"ל​

 

[mob2]

אני חושב שיש בעיה במה שאתה מציע

משום שאם אנו רצים וממיינים את המערך במקטעים של קיי איברים, יתכן מצב ובו איבר שהיה אמור להיות במקום ה k+1 והוסט שמאלה נניח בשני מקומות (בהנחה שקיי גדול מ2), לעולם לא יגיע למקום הטבעי שלו. לכן אני מציע את הדבר הבא: נרוץ על המערך במקטעים של 2K אבל מספר הפעמים שנבצע את הריצה יהיה N/K כך תיווצר חפיפה של קיי איברים בין כל סגמנט שאנו ממיינים ובכך מובטח מיון נכון. בכל ריצה נמיין את המערך עם מיון מיזוג ולכן זמן הריצה הוא n/k * 2klog(2k) => n(2log(k)+2) וזה בהכרח קטן מזמן ריצה של kn

 

[immortalus]

תעבור על מה שרשמתי שוב

שים לב שהסברתי שבכל איטרציה הסגמט התחתון, זה של k האיברים התחתונים ימויין נכון. המקרה שהצעת לא יתכן תחת ההנכון של מערך k ממוין. נסה לבנות את הדוגמא שלך על מערך של 15 איברים 5 ממויינים ותראה שהמקרה שאתה חושב עליו לא קורה... בכל מקרה, להריץ את האלגוריתם פעמיים לא ישנה את הסיבוכיות האסימפטוטית...

 

[mob2]

הסתכלתי שוב ו..

עכשיו אני רואה שכתבנו את אותם דברים בדיוק, אך במילים שונות. טעות שלי, מצטער (לא ראיתי ששהצעת למיין את המערך במקטעים של 2k ). אחלה, תודה.

 

[immortalus]

בבקשה