נושא: מדעי המחשב שפת c

נשלח בתאריך: 05 May 2009 בשעה 21:35 | IP רשוּם

שאלה 1:

נתחיל ברעיון של אלגוריתם המיון merge-sort:

q     לחלק את המערך לשני תתי מערכים בערך שווים בגדלם

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

q     למזג את שני המערכים המוחזרים למערך אחד ממוין.

נחזור לשאלה, כתבו פונקציה רקורסיבית:   void mergeSort(int *source, int size, int *target)   אשר מקבלת מערך מקור לא ממוין, את גודלו ומערך יעד, וממיינת את מערך המקור, אל תוך מערך היעד, בלי לשנות את מערך המקור.

השיטה: מיון מיזוג רקורסיבי.

על מנת למיין את מערך המקור אל מערך המטרה, נגדיר שני מערכי עזר:

             -  עבור חציו השמאלי של המערך.

             - עבור חציו הימני של המערך.

נמיין באופן רקורסיבי את החצי הראשון של source לתוך  ואת חציו הימני אל תוך .

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

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