מיון לינארי במקום

[גל אדום]

מיון לינארי במקום

נניח יש לי M רשומות ויש בהם שדה של 0 או 1, זה שדה בינארי. הדרישה היא לבצע מיון לינארי במקום (כלומר סיבוכיות O של n). רק שאני כנראה לא מבין את השאלה. הרי מיון לינארי כמו מיון מניה או מיון בסיס עושים שימוש בעוד מקום, ככה שזה לא הפתרון. מה למעשה רוצים כאן? זה הרי די טריוואלי לשמור 2 פוינטרים. לסרוק את המערך ולחפש נניח רק "1" ולבצע החלפות. המיון לא יהיה יציב אך עדיין נקבל את כל קבוצת ה"1" בהתחלה ואחריה קבוצת ה"0".

 

[DadleFish]

גם אני לא כל כך מבין -

מה הבעיה עם הפתרון בשני פוינטרים?

 

[גל אדום]

זאת שאלה מתוך בחינה

או שזה קל מדי או שאני לא הבנתי מה רוצים. אני גם לא בטוח שאני מבין מה זה מיון לינארי בדיוק. אולי פה טמון הכלב.

 

[IP yuval]

זה קל, לא צריך להסתבך.

 

[גל אדום]

ראו שאלה אחרת:

נתונות n נקודות במישור

(x1,y1) , (x2,y2) , ... , (xn,yn)​

נקודה xi,yi נקראת נקודת קיצור אם לא קיימת נקודה אחרת הקטנה ממנה בשתי הקורדינטות. רשום אלגוריתם המדפיס את כל נקודות הקיצון. אם אני מבין את השאלה, הרי יכולה להיות רק נקודת קיצון אחת. הנושא הוא מיונים ומיון כלשהו יתן לי נקודת קיצון אחת. לא הבנתי למה מדובר בכמה נקודות ולא בנקודה אחת בלבד.

 

[vinney]

למה רק אחת?

שים לב, לא קיימת נקודה אחרת הקטנה בשתי הקואורדינטות. יכולה להיות קטנה באחת הקואורדינטות, אבל לא בשתיים. למשל בקבוצה (0,1), (1,1) - שתי הנקודות הן נקודות קיצון, כי אף אחת לא קטנה מהשניה בשתי הקואורדינטות.

 

[גל אדום]

תודה. הבנתי בערך

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

 

[vinney]

כי זה N בריבוע מה שאמרת

ואפשר לעשות את זה בפחות עם שני מיונים של N*LOG N וN*LOG N חיפושים - סה"כ סיבוכיות NLOG N, בניגוד לN בריבוע שלך.

 

[גל אדום]

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

בניית הערימה היא O של n. נבנה את הערימה נניח לפי yi של הקורדינטה. כעת נריץ חיפוש ל-xj שהוא יותר קטן מ-xi הנוכחי כדי לדעת האם xi,yi זו נקודת קיצון. החיפוש עצמו בערימה זה nlogn. בעצם, זה לא משנה לפי מה נעשה מיון ראשוני. xi או yi. הסריקה השניה תהיה רק לחפש לפי זה שלא מוין.

 

[vinney]

זה ממש לא משנה

אם תעשה את זה עם ערימות או מיונים אחרים, בסופו של דבר תגיע לNLOG N או כי זה מה שצריך למיון (ואז החיפוש הוא LOG N לכל אחת מN הנקודות) או כי זה מה שצריך לחיפוש (והמיון הוא כמו שאמרת בO של N). בפחות מNLOG N לא תוכל לעשות את זה, וביותר - לא תקבל את כל הנקודות.

 

[גל אדום]

צודק בהחלט

תודה. אפשר גם מיון מיזוג וזה עדיין אותה סיבוכיות.