מיון הכנסה C

[shahartal]

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

אבל משום מה לא עובד לי האלגוריתם שאני בניתי ואני לא מצליח להבין למה.

את הקוד בניתי בC.

הנה הפונקציה:

void in(int arr[], short n)
{
int tmp;
int j=0;
int indx=0;
for(indx<n; indx++
{
    j=indx;
    for(j<n; j++
    {
        if(arr[indx]>arr[j])
        {
            tmp = arr[indx];
            arr[indx] = arr[j];
            arr[j] = arr[indx];
        }
    }


}
indx=0;
printf("\n");
     while(indx<n)
     {
         printf("arr[%d]: %i",indx,arr[indx]);
         printf("\n");
         indx++;
     }


}

תודה רבה!

[שניצל]

השימוש שלך ב-for שגוי.

[shahartal]

השימוש שלך ב-for שגוי.

להבנתי מגרסא מסויימת אי אפשר להכניס לתוך הfor את הint i=0 אז שמתי בחוץ (אם על זה אתה מדבר)

בכל מקרה תסביר את עצמך

[שניצל]

ל-for יש שלושה חלקים - אתחול, תנאי וקידום. בשימוש שלך ב-for שמת את התנאי במקום של האתחול ואת הקידום במקום של התנאי.

[שכיר חרב]

להבנתי מגרסא מסויימת אי אפשר להכניס לתוך הfor את הint i=0 אז שמתי בחוץ

רוב הסיכויים שמישהו ניסה לעבוד עלייך.

בכל מקרה, ל-for אמור להיות המבנה הבאה:

for (A;B;C)i

ב-A אתה מאתחל את המשתנה (ב-C99 ומעלה ניתן לרשום למשל int i = 0 במקום A. לפני זה היית צריך להצהיר על i מעל ה-for).

ב-B יש את התנאי שייבדק לפני כל כניסה לבלוק.

ב-C יש את העדכון של המשתנה (שמתבצע בסיום כל איטרציה).

(שים לב שגם אצלך יש את C, הוא פשוט ריק.)

[shahartal]

רוב הסיכויים שמישהו ניסה לעבוד עלייך.

בכל מקרה, ל-for אמור להיות המבנה הבאה:

for (A;B;C)i

ב-A אתה מאתחל את המשתנה (ב-C99 ומעלה ניתן לרשום למשל int i = 0 במקום A. לפני זה היית צריך להצהיר על i מעל ה-for).

ב-B יש את התנאי שייבדק לפני כל כניסה לבלוק.

ב-C יש את העדכון של המשתנה (שמתבצע בסיום כל איטרציה).

(שים לב שגם אצלך יש את C, הוא פשוט ריק.)

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

אז חשבתי שגם לא צריך לאתחל אותו בתוך הfor

בכל מקרה אני החלפתי את הfor לwhile שחשדתי שזה העניין והבעיה לא נפתרה ועדיין עכשיו שתקנתי את הfor, הבעיה לא נפתרה.

המערך לאחר ה"מיון" הוא פשוט המספר האחרון במערך לאורך כל המערך

(במקום לסדר את המספרים 1 3 2 4 ל 4 3 2 1, המערך הופך ל4 4 4 4)

[שניצל]

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

בכל מקרה הבעיה שלך לא הייתה שלא אתחלת בתוך ה-for, אלא שדילגת על החלק הזה ב-for בכלל. אין בעיה לעשות מה שעשית, אבל זה צריך להיות ככה:

for ( ; indx<n ; indx++)

אבל כאמור עדיף להצהיר על indx ו-j מחוץ ל-for ואז לאתחל אותם בתוכו, דהיינו:

for (indx=0 ; indx<n ; indx++)

זה גם הופך את הקוד ליותר קריא.

תעלה את הקוד המתוקן.

[shahartal]

באמת יותר ברור ונוח.

הנה הקוד המתוקן: (שלא עובד חח)

void in(int arr[], short n)
{
int tmp;
int j=0;
int indx=0;
for(indx = 0; indx<n; indx++)
{
    j=indx;
    for(j=0; j<n; j++)
    {
        if(arr[indx]>arr[j])
        {
            tmp = arr[indx];
            arr[indx] = arr[j];
            arr[j] = arr[indx];
        }
    }

}
indx=0;
printf("\n");
     while(indx<n)
     {
         printf("arr[%d]: %i",indx,arr[indx]);
         printf("\n");
         indx++;
     }

}

[שניצל]

א. מה הטעם ב-j=indx אם שורה אחרי זה אתה עושה j=0?

ב. האלגוריתם שלך הוא לא מיון הכנסה.

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

[shahartal]

לגביי א' תיקנתי (זאת טעות שנוצרה הרגע כשתקנתי את הfor אבל היא לא משפיע על כלום כי זה במילא לא עובד)

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

האמת שאני לא מצליח להבין מה הבעיה פה,

כל סבב הוא אמור להעביר את המספר הקטן ביותר לתחילת המערך ואז בסבב הבא להתחיל מאחד קדימה (ואז להעביר את ההכי קטן לאחד לפני תחילת המערך וכו..)

המיון הכנסה נראה כלכך פשוט אני לא מבין מה אני מפספס.

למה מה שעשיתי לא ממיין ולמה אתה אומר שזה לא מיון הכנסה?

[שניצל]

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

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

http://he.wikipedia.org/wiki/%D7%9E%D7%99%D7%95%D7%9F_%D7%94%D7%9B%D7%A0%D7%A1%D7%94

[shahartal]

אוקי כתבתי את הקוד מחדש והוא עובד, אבל ממך אני מבין שזה לא מיון הכנסה,

איך עושים מיון הכנסה? איך אני יודע מה המקום של כל איבר בלי לעבור שוב ושוב על כל האיברים? (מה שמאוד לא יעיל)

[שניצל]

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

הרעיון הוא שכשאתה ניגש לטפל באיבר ה-i, כל האיברים מ-0 עד i-1 כבר ממויינים, ואתה רק מוצא לאן צריך לדחוף אותו ביניהם.

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

[shahartal]

תודה רבה עזרת הרבה!