עבור לתוכן

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

Featured Replies

פורסם

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

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

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

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

פורסם

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

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

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

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

נערך על-ידי שכיר חרב

פורסם

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

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

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

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

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

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

אחלה פתרון =]

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים