מיון שייקר

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

אנימציה של מיון שייקר

פסאדו קוד

הצורה הכי פשוטה עוברת על כל הרשימה בכל פעם:

 procedure cocktailShakerSort( A : list of sortable items ) defined as:
 do
 swapped := false
 for each i in 0 to length( A ) - 2 do:
 if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
 swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
 swapped := true
 end if
 end for
 if not swapped then
 // we can exit the outer loop here if no swaps occurred.
 break do-while loop
 end if
 swapped := false
 for each i in length( A ) - 2 to 0 do:
 if A[ i ] > A[ i + 1 ] then
 swap( A[ i ], A[ i + 1 ] )
 swapped := true
 end if
 end for
 while swapped // if no elements have been swapped, then the list is sorted
end procedure

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

הבדלים ממיון בועות

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

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

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

סיבוכיות

הסיבוכיות של מיון שייקר בסימון אסימפטוטי הוא $O(n^{2})$ במקרה הגרוע ובמקרה הממוצע, אבל הוא מתקרב ל $O(n)$ אם הרשימה ברובה ממוינת לפני ביצוע המיון. לדוגמה, אם כל איבר נמצא במקום ששונה בלא יותר מ-k ‏(k ≥ 1) מהמקום בו הוא יסיים, הסיבוכיות של המיון הופכת להיות $O(kn)$.