7.3 מיון-מהיר
(המשך) - השוואה עם מיון-ערמה
מבנה
נתונים ואלגוריתמים
בדיקות
אמפיריות מראות כי מיון-מהיר הוא באופן כללי מהיר יותר מאשר מיון-ערמה.
הטבלה הבאה
מציגה נתונים על פעולות השוואה והחלפה עבור שלושה אלגוריתמים שונים של מיון כאשר
הם רצים על אותו קלט.
|
הכנסה |
ערמה |
מהיר |
n |
|||
|
החלפה |
השוואה |
החלפה |
השוואה |
החלפה |
השוואה |
|
|
899 |
2,595 |
581 |
2,842 |
148 |
712 |
100 |
|
3,503 |
10,307 |
1,366 |
9,736 |
328 |
1,682 |
200 |
|
21,803 |
62,746 |
4,042 |
53,113 |
919 |
5,102 |
500 |
כך, כאשר
"תקלה" מקרית של (n²)O
היא נסבלת, נצפה שבממוצע מיון-מהיר יספק ביצועים טובים יותר באופן
ניכר, במיוחד אם נעשה שימוש באחת מהשיטות המשופרות לבחירת פריט הציר.
במרבית
היישומים המסחריים נעשה שימוש במיון-מהיר בשל ממוצע הביצועים הטוב יותר: הם יכולים
לסבול מקרה מזדמן של זמן ריצה ארוך, בתמורה לזמני ריצה קצרים יותר ברוב המקרים.
אולם, אין
להשתמש במיון-מהיר באפליקציות הדורשות זמני ריצה מובטחים (שאינן מאפשרות מקרים
בודדים שחורגים מסדר הגודל של הערכת הזמן), אלא אם כן מתייחסים אליו כאלגוריתם של
(n²)O עבור זמן
הריצה הגרוע ביותר. כשמדובר בסדר גודל של (n²)O,
אזי כאשר n קטן עדיף להשתמש
במיון-הכנסה (insertion sort), שהוא בעל קוד פשוט
יותר ולכן גם בעל גורמים קבועים קטנים יותר. כאשר n
גדול כדאי להשתמש במיון-ערמה, בשל זמן ה- O(nlogn)
המובטח.
בתוכנות
תומכות-חיים (מערכות ניטור רפואי, מערכות חיוניות במטוסים וחלליות) ובתוכנות
המשמשות למשימות קריטיות (בקרה ושליטה במערכות מחקר ותעשייה המטפלות בחומרים
מסוכנים, שליטת במערכות מטוסים, מערכות הגנה ועוד) זמן המענה בדרך כלל נתון כחלק
ממפרט המערכת. בכל המערכות הללו התכנון לא יכול להיות מבוסס על ביצוע ממוצע, ולכן
יש להתחשב תמיד במקרה הגרוע ביותר ולהתייחס למיון-מהיר כ- (n²)O.
עד כאן
אלגוריתם המיון הטוב ביותר שלנו הוא בעל ביצוע של O(nlogn).
האם ניתן לשפר זאת?
באופן כללי
התשובה היא לא.
אולם, אם קיים
מידע על הפריטים הדרושים למיון, יתכן שאפשר לשפר את הביצוע.
אבל תחילה ננסה
לסחוט את טיפת הביצוע האחרונה של מיון-מהיר.
המשך ל: מיון
מהיר - הטיפה האחרונה חזור
ל: תוכן עניינים