יעילות – חלק ג'

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

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

מיון בועות

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

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

האיור הבא ידגים את מיון הבועות על מערך שבו שישה איברים, המערך המקורי מוצג בצד ימין והמערך לאחר המעבר הראשון מוצג בצד שמאל:

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

סדר גודל זמן הריצה של מיון בועות

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

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

כלומר, סיבוכיות זמן הריצה של אלגוריתם מיון בועות הוא n*n (ז"א N בריבוע), כלומר סדר גודל ריבועי . לא התייחסנו כאן למקדם של n*n שהוא 0.5 וגם לא ל -n/2 משום שהם זניחים בהשוואה ל n*n לגבי ערכי n גדולים.

מיון מיזוג

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

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

להלן איור המדגים את מיון מיזוג, האיברים המוצבעים מובלטים:

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

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

האלגוריתם למיון מיזוג נראה כך:

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

סיכום

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

זמן ריצה נחשב לבלתי סביר כאשר הפונקציה המתארת אותו היא פונקציה מערכית או אקספוננציאלית (Exponential function). בפונקציות כאלו N שמסמל את אורך הקלט מופיע במעריך החזרה והבסיס גדול מ 1.

למשל: 4^n ו 3^n הן דוגמא לפונקציה מערכית פשוטה שקצב גידולה מהיר מאוד, קיימות פונקציות שקצב גידולן מהיר הרבה יותר, נניח n^n, n!, n*2^n ועוד.