כיצד לחשב מיון מערך בסיבוכיות נמוכה ככל הניתן

[wow]

אני אמור לפתור את השאלה בצורה כמה שיותר יעילה כי אם הסיבוכיות תהיה גבוהה מזו הנדרשת (במקום או בזמן) אני לא יקבל את מירב הנק'.

מה נראה לך יהיה יעיל לעשות ?

אולי יהיה הכי יעיל לעבור על המערך 4 פעמים ובכל פעם "לשלוף" את המספרים שמתחלקים ללא שארית,אח"כ את אלו עם שארית של 1 וכו' ולדחוף אותם למערך חדש ? השאלה שלי היא האם זה יהיה יעל ולא קצת "לא יפה לעין"

[noodle]

כמו שאמרו 5n,4n,10n כולם O(n) בסופו של דבר.

וגם במקום לשחזר קוד של swap עדיף תעשה פונקציה נפרדת להחלפה.

[neogod]

אם תעביר את האיברים למערך עזר זה כבר לא יהיה מיון במקום .

[שניצל]

שום דבר לא מונע ממנו להעביר למערך זמני חדש ואז להעתיק בחזרה למערך המקורי.

[wow]

אוקיי השאלה שלי היא איך הכי טוב להעביר למערך חדש ?

האם להגדיר מערך עזר אחד או שניים ? הסיבוכיות עדיין תהיה n ?

[Gil28]

ממליץ לך לעבור על האלגוריתם של bucket sort ולראות איך אתה משתמש בו.

[עוד אחד]

שום דבר לא מונע ממנו להעביר למערך זמני חדש ואז להעתיק בחזרה למערך המקורי.

סיבוכיות מקום...

למה לעשות את זה אם לא חייבים ?

זה פתיר בסיבוכיות מקום של N ובזמן של N+K < 2N

[Gil28]

שימוש במערך נוסף (או שניים, שלושה) זה סיבוכיות מקום של (O(n

[עוד אחד]

אוקיי.

תספר לגוגל שפתרת להם את הבעיה של אינדוקס האינטרנט באו של.

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

[Gil28]

אנחנו מנסים לשפר כאן את הקבוע ולספור מיקרו שניות או לעזור לו בשיעורי בית?

[עוד אחד]

אנחנו מנסים לגרום לו להיות מתכנת טוב יותר.

מתכנת שמבזבז משאבים בצורה מיותרת כשיש פתרון טריוויאלי שלא עושה את זה הוא מתכנת לא טוב.

[wow]

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

[עוד אחד]

למיין, זו בדר"כ בעיה קשה יותר ממה שיש לך פה.

כי יש סדר בין כל האיברים.

כאן אתה רק מחלק אותם לקבוצות ע"פ תכונה מסויימת.

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

נניח שהייתי נותן לך מערך של כדורים שחורים ולבנים, והייתי רוצה שכל הלבנים יהיו בהתחלה והשחורים יהיו בסוף, איך היית עושה את זה ?

נניח שאסור לך להוציא את כל הכדורים ולהתחיל לסדר אותם, יש לך רק 2 ידיים.

משם הדרך ל3 צבעים קצרה.

[wow]

לא הבנתי את השורה האחרונה (משם הדרך ל-3 צבעים קצרה) - האם אתה מתכוון למערך עזר ?

[עוד אחד]

לא. אמרנו שלצורך העניין אסור להוציא כדורים, ושיש לך רק 2 ידיים.

תן לי אלגוריתם ל2 צבעים, ובוא נחשוב איך אפשר להרחיב אותו, אם בכלל צריך..