אני צריכה עזרה...

[sindy_]

אני צריכה עזרה... ../images/Emo70.gif

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

אני צריכה לכתוב תוכנית בפסקל שמקבלת מהמשתמש קובץ טקסט (כגון: c:/a.txt) וצריכה לבצע בו מיון על פי הגדרות שהמשתמש (מדובר במספר מיונים פנימיים ואחד חיצוני גדול) ולבסוף להדפיס את הקובץ לקובץ טקסט חדש שאת שמו גם המשתמש נותן. כמו-כן יש לבצע את המיון לא בעזרת פרוצדורות אלא בעזרת אלוגריתמים.

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

 

[באפט]

תגובה

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

 

[sindy_]

תגובה לתגובה

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

 

[שאקל]

Merge Sort מיון מיזוג

זה אלגוריתם הפועל בשיטת הפרד ומשול. מה שהוא עושה: 1. מחלק את סדרת X האיברים שיש למיין לשתי סדרות. כל אחת בת X/2 איברים. 2. ממיין את שתי הסדרות באופן רקורסיבי. 3. ממזג את שתי הסדרות הממוינות לסדרה ממוינת אחת. נניח ויש לנו מערך עם המספרים 1,3,2,6 נחלק את המערך לשתי קבוצות. קבוצה 1: 1,3 קבוצה 2: 2,6 כעת מבצעים מיזוג של שתי הסדרות ממוין. מקוה שעזרתי קצת בהבנת האלגוריתם.

 

[אלדד26]

אלגוריתם mergesort

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

Array 1 = 3, 7, 23, 26, 32, 54, 55, 87, 91, 93 Array 2 = 1, 7, 14, 23, 24, 25, 55, 87, 92, 92​

עכשיו - האינדקסים בהתחלה מצביעים לתאים הראשונים במערך. לוקחים את הנתון "1" מתוך המערך השני, ומכניסים אותו למערך התוצאה. מקדמים את האינדקס במערך השני ל - 2 (האינדקס במערך הראשון עדיין שווה ל - 1); ממשיכים עם הנתון "3" מתוך המערך הראשון (כי עכשיו משווים בין ה - 3 לבין ה - 7), וכן הלאה - עד שהכל ממוין. עכשיו, כשאת יודעת איך לוקחים שתי קבוצות וממזגים אותן לתוך מערך אחד, איך עובד merge sort? הרעיון הוא לקחת את המערך, לחתוך אותו כל פעם באמצע, למיין כל חלק בעזרת mergesort, ולהפעיל את פעולת ה - merge על שני החלקים שמוינו. שימי לב, שההגדרה מכילה קריאה לאלגוריתם עצמו מתוכו - כלומר, רקורסיה. אם היה לך מערך בגודל של 8 נתונים, למשל, האלגוריתם היה כזה: חלקי את המערך לשני חלקים (כל אחד 4 נתונים) מייני את החלק הימני .. חלקי את המערך לשני חלקים (כל אחד 2 נתונים) .. מייני את החלק הימני - זה שני נתונים ולכן אפשר לבצע זאת "ידנית" .. מייני את החלק השמאלי - זה שני נתונים ולכן אפשר לבצע זאת "ידנית" .. מזגי את שני החלקים מייני את החלק השמאלי .. חלקי את המערך לשני חלקים (כל אחד 2 נתונים) .. מייני את החלק הימני - זה שני נתונים ולכן אפשר לבצע זאת "ידנית" .. מייני את החלק השמאלי - זה שני נתונים ולכן אפשר לבצע זאת "ידנית" .. מזגי את שני החלקים מזגי את שני החלקים וזהו - יש לך מערך ממוין! פה נתתי דוגמה מאוד פשוטה, אבל רקורסיבית אפשר למיין הרבה יותר. בהצלחה!