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

==סיבוכיות ותכונות==

[[סיבוכיות זמן|סיבוכיות הזמן]] של המיון תלויה לא רק במספר האיברים בקלט, אלא גם בטווח האפשרי שלהם, מכיוון שעוברים הן על כל הקלט, והן על כל המערך, שאורכו הוא כאורך הטווח האפשרי של איברי הקלט. אם <math>\ n</math> הוא מספר האיברים ו-<math>\ k</math> הוא הטווח, אז סיבוכיות הזמן היא <math>\ O(n+k)</math>. על כן, אם <math>\ k=O(n)</math>, כלומר הטווח הוא לינארי בגודל הקלט או פחות מכך, אזי תהיה סיבוכיות הזמן של המיון <math>\ O(n)</math>. זו תוצאה העדיפה אסימפטוטית על זו של מיונים כלליים, שסיבוכיות הזמן המינימלית שלהם היא <math>\ O(n\log n)</math>.

אפשר ליישם את האלגוריתם בסיבוכיות <math>\ O(n)</math> גם כאשר טווח הערכים הוא <math>\ 1 , \dots , n^2</math>, כלומר לא לינארי לגודל הקלט. העיקרון לכך הוא שממירים את המספרים ל[[בסיס (אריתמטיקה)|בסיס]] <math>\ n</math>, כך שמספר הספרות המקסימלי הוא 2, ומספר התאים במערך <math>\ C</math> הוא בסך הכל <math>\ n</math>, ולכן <math>\ k</math> אינו <math>\ n^2</math> אלא <math>\ n</math>, ואז מיישמים [[מיון בסיס]].

תכונה נוספת של מיון מנייה היא שהוא [[מיון יציב]], כלומר לא משנה את הסדר היחסי בין איברים זהים במיון.

'''<big><big><big><big><big><big><big><big><big><big>אמצעי מניעה</big></big></big></big></big></big></big></big></big></big>'''

 

[[קטגוריה:אלגוריתמי מיון|מנייה]]

[[en:Counting sort]]

[[cs:Counting sort]]