JAVA - סוג של מיון בועות (קוד בפנים)

[שניצל]

(אבל אני מודה שהפתרון אכן בעייתי אם דורשים O(1) מקום.)

nop. אפשר לעשות הכל in place.

[שכיר חרב]

nop. אפשר לעשות הכל in place.

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

[שניצל]

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

[שכיר חרב]

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

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

איך אתה עשית את זה?

[Gil28]

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

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

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

[שכיר חרב]

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

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

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

אחלה פתרון =]