7. מיון

מבנה נתונים ואלגוריתמים

 

 

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

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

 

7.1 מיון-בחירה, מיון-הכנסה, מיון-בועות

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

 

/* Insertion sort for integers */

void insertion( int a[], int n ) {

/* Pre-condition: a contains n items to be sorted */

    int i, j, v;

/* Initially, the first item is considered 'sorted' */

/* i divides a into a sorted region, x<i, and an

        unsorted one, x >= i */

for(i=1;i<n;i++) {

        /* Select the item at the beginning of the

               as yet unsorted section */

        v = a[i];

 /* Work backwards through the array, finding where v should go */

        j = i;

     /* If this element is greater than v,

            move it up one */

        while ( a[j-1] > v ) {

              a[j] = a[j-1]; j = j-1;

              if ( j <= 0 ) break;

              }

   /* Stopped when a[j-1] <= v, so put v at position j */

   a[j] = v;

   }

}    

 

 

מיון-בועות

גרסה נפוצה של הליך המיון נקראת מיון-בועות:

 

/* Bubble sort for integers */

#define SWAP(a,b)   { int t; t=a; a=b; b=t; }

void bubble( int a[], int n )

/* Pre-condition: a contains n items to be sorted */

    {

     int i, j;

     /* Make n passes through the array */

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

          {

        /* From the first element to the end

                   of the unsorted section */

          for(j=1;j<(n-i);j++)

             {

        /* If adjacent items are out of order, swap them */

             if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);

             }

          }

} 

 

 

ניתוח

כל אחד מאלגוריתמים אלה דורש n-1 מעברים: בכל מעבר ממוקם פריט אחד במקומו הנכון (הפריט ה-n  ממוקם במקום הנכון בעקבות המעברים הקודמים). המעבר ה- i יוצר i או n-i השוואות והזזות.

לכן:

 

כלומר O(n²) - אך אנו כבר יודעים שניתן להשתמש בערמות על מנת לקבל אלגוריתם של

 O(nlogn). לכן אלגוריתם זה מתאים רק עבור בעיות קטנות שהקוד הפשוט שלהן מאפשר להן לפעול מהר יותר בדרך זו מאשר בעזרת הקוד המורכב של אלגוריתם של O(nlogn).

 

כלל אצבע: צפה למצוא אלגוריתם של O(nlogn) כמהיר יותר עבור n>10 , אך הערך המדויק תלוי במידה רבה במחשבים השונים עצמם.

 

 

מושגים

 

מיון-בועות, מיון-הכנסה ומיון-בחירה

אלגוריתמים פשוטים של מיונים, בעלי סיבוכיות של O(n²) - מתאימים למיון מספר קטן של פריטים בלבד.

 

 

המשך ל: מיון-ערמה                    חזור ל: תוכן עניינים