מיון מחסניות

[uvdude]

מיון מחסניות

אני עובר פה על מבחנים לקראת מבחן מחר במבוא למדעי המחשב וג'אווה בפתוחה נתקעתי באיזהשהי שאלה. איך ממיינים מחסנית, בעזרת הפעולות הבסיסיות בלבד (Push, pop, וכד'...), ובעזרת שתי מחסניות עזר בלבד? אין צורך למצוא אלגוריתם בסיבוכיות O(NlogN) רעיונות?

 

[shirbi]

אולי באמצעות Merge Sort?

 

[מתכNET]

אולי ככה?

1.קח את האיבר הבא ממחסנית S 2.אם הוא קטן מהאיבר ה TOP של מחסנית S1 אז דחוף אותו ל S1 אחרת עשה את זה 2.1 הוצא את כל האיברים קטנים ממנו והכנס אותם ל S2 2.2 דחוף את האיבר ל S1 2.3 העבר את כל האיברים מ S2 ל S1

 

[מתכNET]

למעשה מדובר ב INSERTION SORT כמדומנ

י

 

[מיקי256]

יפה מאוד, אך אפשר לשפר

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

 

[מתכNET]

כן חשבתי על זה אבל...

כתוב שצריך למיין בעזרת 2 מחסניות נוספות..עשיתי מה שביקשו בדיוק מ

 

[עדין ר]

זה לא O(n^2) zz ?

 

[danby]

מזכיר לי קצת את "מגדלי הנוי"

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

 

[tamarhp]

הרקורסיה של הנוי זה

2f(x) + 1 אם אני זוכרת נכון..

 

[עדין ר]

אולי משהו כמו merge sort

כדי למיין n איברים שנמצאים ב-S בעזרת S1 ו-S2 בכיוון מסויים: 1. אם n>1 1.1. הוצא מ-S איבר ודחוף אותו ל-S1, עשה זאת n/2 פעמים (מעוגל כלפי מעלה) 1.2. מיין (באופן רקורסיבי) n/2 (מעוגל כלפי מעלה) איברים ב-S1 בעזרת S ו-S2 בכיוון ההפוך 1.3. הוצא מ-S איבר ודחוף אותו ל-S2, עשה זאת n/2 פעמים (מעוגל כלפי מטה) 1.4. מיין (באופן רקורסיבי) n/2 (מעוגל כלפי מטה) איברים ב-S2 בעזרת S ו-S1 בכיוון ההפוך 1.5. מזג את שתי המחסניות הממוינות בסדר הפוך S1 ו-S2 לתוך S