מיון מנייה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Mordechaig (שיחה | תרומות) עריכה, זה כלל לא משנה הסדר שבו עוברים על A כל עוד עוברים על כולו בלי חזרות |
Mordechaig (שיחה | תרומות) ביטול גרסה 20729446 של Mordechaig (שיחה) |
||
שורה 9:
לאחר מכן, סוכמים את מספר המופעים - מוסיפים לכל <math>\ C[i]</math> את קודמו - <math>\ C[i]=C[i]+C[i-1]</math>. באופן זה, בתא <math>\ C[i]</math> שמור מספר האיברים אשר קטנים או שווים ל-<math>\ i</math> במערך <math>\ A</math>.
בשלב הבא עוברים על מערך <math>\ A</math> מהסוף להתחלה, ועל כל איבר <math>\ A[i]</math> מבצעים:
#<math>\ B[C[A[i]]] = A[i] </math>
#<math>\ C[A[i]] = C[A[i]]-1</math>
המערך <math>\ B</math> יהיה ממוין, והסדר בין איברים שווים נשמר, מה שגורם לכך שמיון זה יהיה [[מיון יציב]]. זאת משום שבתא <math>\ C[i]</math> נשמר המופע האחרון המיועד של האיבר <math>\ i</math> במערך <math>\ B</math>, ומשום שהמעבר על מערך <math>\ A</math> היה
==סיבוכיות ותכונות==
| |||