מידע מורחב

  • תאריך
  • שעה 16:56
  • ע"י
  • צפיות 12312
  • תגובות 4
  • דירוג 4 /5
 

++C למתחילים - חלק שמיני: מיון מערכים

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

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


סוגי המיון שנבחן הם: (מהאיטי והקל למהיר והמסובך)
  • מיון בועות/החלפה – bubble sort
  • מיון הכנסה – insert sort
  • מיון מהיר - quick sort
  • מיון בחירה – select sort
  • מיון מיזוג – merge sort (הכי מהיר)



מיון בועות – Bubble sort:
מיון זה נקרא מיון בועות, מהדרך בה מבעבעים אלמנטים מהמערך.

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

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

קוד המיון הוא:
void bubble_sort(int data[], int ARRAY_SIZE)
{
      int   temp,
            counter1,
            counter2;
 
      for (counter1 = 0; counter1 < ARRAY_SIZE-1; counter1++)
      {
            for (counter2 = 0; counter2 < ARRAY_SIZE-counter1-1; counter2++)
            {
                  if (data[counter2] > data[counter2+1])
                  {
                        temp = data[counter2];
                        data[counter2] = data[counter2 + 1];
                        data[counter2+1] = temp;
                  }
            }
      }
}



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

כעת בחרו למטה בחלון את סוג המיון הרצוי sort kind והקישו start.

זמן הריצה: זמן הריצה של אלגוריתם זה הוא .

זמן ריצה ? מה זה בכלל ?

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

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

ככל שמספר הפעולות קטן יותר, כל האלגוריתם יותר יעיל ומהיר.

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


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

קוד המיון הוא:
void insert_sort(int data[], int ARRAY_SIZE)
{
      int   temp,
            counter1,
            counter2;
 
      for (counter2 = 1; counter2 < ARRAY_SIZE; counter2++)
      {
            counter1 = counter2 - 1;
            temp = data[counter2];
            while ((counter1 >= 0) && (temp < data[counter1]))
            {
                  data[counter1+1] = data[counter1];
                  counter1--;
            }
            data[counter1+1] = temp;
      }
}



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

זמן הריצה: זמן הריצה של אלגוריתם זה הוא .



מיון מהיר – Quick sort:
אלגוריתם מיון מהיר הוא אלגוריתם הפועל בשיטת הפרד ומשוך.
נפרט את האלגוריתם בצעדים הבאים:

  1. בהינתן סדרת איברים, בחר איבר מהסדרה באקראי (נקרא: pivot, או "איבר ציר").
  2. סדר את כל האיברים כך שהאיברים הגדולים מאיבר הציר יופיעו אחרי האיברים הקטנים מאיבר הציר.
  3. באופן רקורסיבי, הפעל את האלגוריתם על סדרת האיברים הגדולים יותר ועל סדרת האיברים הקטנים יותר.
  4. תנאי העצירה של האלגוריתם הוא כאשר ישנו איבר אחד, ואז האלגוריתם מודיע כי הסדרה ממוינת.



קוד המיון הוא:
void quick_sort(int data[], int left, int right)
{
      int counter1,
            counter2,
            temp,
            mid,
            center;
 
      counter1 = left;
      counter2 = right;
      center = data[mid];

      do
      {
            while (data[counter1] < center)
                  counter1++;
            while (center < data[counter2])
                  counter2--;

            if (counter1 <= counter2)
            {
                  temp = data[counter1];
                  data[counter1] = data[counter2];
                  data[counter2] = temp;
                  counter1++;
                  counter2--;
            }
      }
      while (counter1 < counter2);  
      if (left < counter2)
            quick_sort(data,left,counter2);
      if (counter1 < right)
            quick_sort(data,counter1,right);
}




זמן הריצה: זמן הריצה של אלגוריתם זה בממוצע הוא
ובמקרה הגרוע .



מיון בחירה – Select sort:
מיון זה פועל בצורה באופן הבא:
תחילה אנו מוצאים את האיבר הנמוך ביותר במערך ושמים אותו בתחילת המערך.
את פעולה זו אנו עושים שוב ושוב על שאר המערך ובכך נקבל מערך ממוין.

קוד המיון הוא:
void select_sort(int data[], int ARRAY_SIZE)
{
      int min,
            temp,
            counter1,
            counter2,
            min_id;
 
      for (counter1 = 0; counter1 < ARRAY_SIZE - 1; counter1++)
      {
            min = data[counter1];
            for (counter2 = counter1+1; counter2 < ARRAY_SIZE; counter2++)
            {
                  if (data[counter2] < min)
                  {
                        min = data[counter2];
                        min_id = counter2;
                  }
            }
            temp = data[counter1];
            data[counter1] = data[min_id];
            data[min_id] = temp;
      }
}



זמן הריצה: זמן הריצה של אלגוריתם זה הוא .




מיון מיזוג – Merge sort:
מיון זה נחשב לאלגוריתם ההשוואתי היעיל ביותר.
מיון זה פועל בשיטת הפרד ומשול.
אנו מחלקים את הבעיה למספר חלקים שווים (פחות או יותר).

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


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

לדוגמא נראה את האלגוריתם על מערך מסוים:


קוד המיון הוא:
void merge_sort(int data[], int low, int high)
{
      int mid;

      if(low < high)
      {
            mid = (low+high)/2;
            merge_sort(data,low,mid);
            merge_sort(data,mid+1,high);
            merge(data,low,high,mid);
      }
}

//------------merge------------
void merge(int data[], int low, int high, int mid)
{
      int counter1,
            counter2,
            counter3,
            newarray[ARRAY_LEN]; //ARRAY_LEN is constant
 
      counter1=low;
      counter2=mid+1;
      counter3=low;
 
      while((counter1<=mid)&&(counter2<=high))
      {
            if(data[counter1] < data[counter2])
            {
                  newarray[counter3] = data[counter1];
                  counter3++;
                  counter1++;
            }
            else
            {
                  newarray[counter3] = data[counter2];
                  counter3++;
                  counter2++;
            }
      }
 
      while(counter1<=mid)
      {
            newarray[counter3] = a[counter1];
            counter3++;
            counter1++;
      }

      while(counter2<=high)
      {
            newarray[counter3] = data[counter2];
            counter3++;
            counter2++;
      }
    
      for(counter1=low; counter1 < counter3 ; counter1++)
      {
            data[counter1] = newarray[counter1];
      }
}



זמן הריצה: זמן הריצה של אלגוריתם זה הוא .



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

ישנם עוד אלגוריתמים של מיון מערך, אך אלה הנפוצים ביותר ואני מקווה שתשתמשו בהם כמה שיותר ושיבואו לכם תועלת כמו שלי הביאו.
עדיין לא נרשמת לאתר ? לחץ כאן להרשמה מהירה
נא המתן...
דירוג
  1. תודה על המאמר אבל יש לך כאן טעות.
    זמן הריצה הממוצע של quicksort הוא O(n log n), הזמן הגרוע ביותר הוא O(n^2).

    לגבי האלגוריתם של mergesort, לשם קריאות הקוד כדאי בפעולת הmerge לבצע את קידום counter1/2/3 בתוך ההשמה עצמה ולא בשורות שלאחר מכן.
  2. היי תודה על התגובה
    מסתבר שכתבתי את זמן הריצה הנכון של מיון מהיר, אך הפירסוס של המאמר העלים חלק מהמשפט ואת התמונה הראשונה (באג שלי), סידרתי את זה ידנית ואת הבאג אתקן.
    לגבי מיון מיזוג החלטתי להשאיר את זה איך שזה... אתה מוזמן לרשום פה בהערה את הקוד בצורה קריאה יותר
  3. עבודה נפלאה, תודה על המאמר.
  4. מיון מערכים הינו משהו שנעשה היום יותר בתור תרגיל לימודי
    הספריה הסטנדרטית של C++ באה כבר עם מימושים של מיונים לבחירת המשתמש:

    #include <algorithm>
    
    ...
    
    int main() {
    
    ...
    
    int ar[50];
    
    ...
    
    std::sort(ar, ar+50);
    
    ...
    
    }
    


    המימוש המדוייק של sort תלוי במהדר בו אתם משתמשים (אבל הוא יהיה לפחות מהיר כמו מיון מהיר)
    באופן דומה יש stable_sort

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


עליך להתחבר כדי להגיב. לחץ כאן להתחברות.