שאלה | מיזוג 3 מערכים

[maimon_y]

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

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

נ.ב אני כותב בC#

[Gil28]

לא כתבת באיזו שפה מדובר.

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

[Ash Binary]

או שתמזג 2 ואז את ה 3. תלוי איך בדיוק דברים שם בנויים יכול להיות שתקבל סיבוכיות נמוכה יותר אפילו

[Gil28]

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

[שניצל]

מבחינת סיבוכיות אין הבדל בין לרוץ על המערכים במקביל לבין לאחד שניים ואז את התוצאה עם השלישי.

מבחינת יעילות יכול להיות שלעבור על שלושתם במקביל יהיה טיפה יותר יעיל.

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

[maimon_y]

אני כותב ב C# שכחתי לציין.

ומה שאני עושה זה מיזוג של שתי מערכים כמו שאמר gil אני משווה 3כתובות בודק מי מבינהם הכי קטן ולא נמצא כבר בלולאה ומכניס אותו לממזג ומעלה את המונה של הלולאה שהערך שלה נמצא הכי קטן וכך עד שאחת מהם נגמרת זה החלק הראשון.

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

והחלק השני הוא אחרי שאחת מהם תיגמר אני צריך לרשום שוב את כל האפשרויות של כל אחת נגמרת ראשונה.

ולאחר מכן לבצע הכנסה של 2 לולאות לממזג בהתאם לתנאי שלמעלה.

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

[Ash Binary]

גיל : צודק. לא הבאתי בחשבון שכשאתה מוסיף את המערך ה 3 אתה חייב לעבור שוב על המערך שמורכב מ 1+2

[needacomp]

אם לא איכפת מכמות קוד, מה רע ב:

arr1.Concat(arr2).Concat(arr3).Sort()

[Ash Binary]

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