אלגוריתם מיון – הבדלי גרסאות

*'''[[מיון מסרק]]''' (comb sort) הוא אלגוריתם מיון שמשפר את [[מיון בועות]]. הרעיון הבסיסי הוא להעלים ''צבים''- ערכים קטנים המופיעים לקראת סוף הרשימה, היות שבמיון בועות הללו מאטים מאוד את המיון. (''ארנבים''- ערכים גדולים סביב תחילת הרשימה- לא מהווים בעיה במיון בועות).

*'''[[רשת מיון]]''' (sorting network) מאפשרת למיין מספר קבוע מראש של קלטים. היתרון הגדול של רשת מיון הוא שהיא נוחה למיקבול (כלומר לחלוקה למשימות היכולות להתבצע במקביל). כך, כשהמיון נעשה על מחשב המאפשר בצוע מקבילי ניתן להגיע באופן מעשי לביצועים של <math>O(log^2n)</math>.

'''מיונים עם הנחות נוספות על הקלט''':

* '''[[מיון מנייה]]''' (counting sort) הוא אלגוריתם למיון [[מספר שלם|מספרים שלמים]] המתבסס על העובדה שהמספרים נמצאים בטווח חסום כדי לבצע את המיון בזמן מהיר יותר מזה שמסוגלים לו אלגוריתמי המיון מבוססי ההשוואות. בצורה אינטואיטיבית, די למיון לעבור על קבוצת האיברים שרוצים למיין ולמנות את מספר המופעים של כל אחד מהאיברים, ומכאן שמו של האלגוריתם.

* '''[[מיון סלים]]''' (bucket sort) הוא מיון של קבוצת מספרים ממשיים כאשר ידוע שפיזור האיברים אחיד (קרי, מקיימים [[התפלגות אחידה בדידה]]).

* '''[[מיון בסיס]]''' (radix sort) הוא אלגוריתם למיון מספרים, המסתמך על מידע נוסף שאומר שכמות הספרות שבאמצעותן מיוצג כל מספר חסומה על ידי קבוע. (למשל: כמות הספרות של המספר 1234567 היא 7).

 

במיונים הללו (מנייה, סלים, בסיס) בעזרת מידע נוסף על הקלט סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון מבוסס השוואות עד ל<math>O\left(n\right)</math> במקום <math>O\left(n\log n\right)</math>.