streamalism.org

1. סקירה כללית

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

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

2. ספירת מיון

ספירת מיון, בניגוד לרוב אלגוריתמי המיון הקלאסיים, אינה ממיינת את הקלט הנתון על ידי השוואת האלמנטים. במקום זאת, זה מניח שאלמנטים הקלט הם נ מספרים שלמים בטווח [0, k]. מתי k = O (n), ואז מיון הספירה יעבור פנימה עַל) זְמַן.

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

2.1. מערך תדרים

נניח שנלך למיין מערך קלטעם ערכים בטווח [0, 5]:

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

לדוגמא, מכיוון ש- 5 מופיע 3 פעמים במערך הקלט, הערך לאינדקס 5 שווה ל- 3.

עכשיו נתון למערך C, עלינו לקבוע כמה אלמנטים קטנים או שווים לכל אלמנט קלט. לדוגמה:

• אלמנט אחד קטן או שווה לאפס, או במילים אחרות, יש רק ערך אפס אחד, השווה ל- ג [0]
• שני אלמנטים קטנים או שווים לאחד, שהוא שווה ל- C [0] + C [1]
• ארבעה ערכים הם קטנים או שווים לשניים, וזה שווה ל- C [0] + C [1] + C [2]

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

2.2. האלגוריתם

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

• זה מחזיר את מערך הקלט לאחור
• לכל אלמנט אני, ג [i] - 1 מייצג את מיקום המספר אני במערך הממוין. זה בגלל העובדה שיש C [i] אלמנטים קטנים או שווים ל- אני
• ואז, זה מקטין את C [i] בסוף כל סיבוב

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

לכן, 5 צריך להיות האלמנט ה -11 במערך הממוין, ומכאן האינדקס 10:

מכיוון שעברנו 5 למערך הממוין, עלינו להקטין את ה- ג [5]. האלמנט הבא בסדר ההפוך הוא 2. מכיוון שיש 4 אלמנטים שקטן או שווה ל -2, מספר זה צריך להיות האלמנט הרביעי במערך הממוין:

באופן דומה, אנו יכולים למצוא את המקום הנכון עבור האלמנט הבא שהוא 0:

אם נמשיך לחזור ולהפוך ולהזיז כל אלמנט כראוי, נגיע למשהו כמו:

3. מיון ספירה - יישום ג'אווה

3.1. מחשוב מערך התדרים

ראשית, בהתחשב במערך קלט של אלמנטים וה- k, עלינו לחשב את המערך ג:

int [] countElements (int [] קלט, int k) {int [] c = int int [k + 1]; מערכים. מילוי (c, 0); עבור (int i: קלט) {c [i] + = 1; } עבור (int i = 1; i <c.length; i ++) {c [i] + = c [i - 1]; } להחזיר ג; }

בואו נפרט את חתימת השיטה:

• קֶלֶט מייצג מערך מספרים שאנחנו הולכים למיין
• ה קֶלֶט מערך הוא מערך של מספרים שלמים בטווח [0, k] - כך k מייצג את המספר המרבי ב- קֶלֶט
• סוג ההחזרה הוא מערך של מספרים שלמים המייצגים את ג מַעֲרָך

וכאן איך countElements השיטה עובדת:

• ראשית, אתחזנו את ה- ג מַעֲרָך. כמו שהטווח [0, k] מכיל k + 1 מספרים, אנו יוצרים מערך המסוגל להכיל k + 1 מספרים
• ואז עבור כל מספר ב קֶלֶט, אנו מחשבים את תדירות המספר הזה
• ולבסוף, אנו מוסיפים אלמנטים עוקבים יחד כדי לדעת כמה אלמנטים הם פחות או שווים למספר מסוים

כמו כן, אנו יכולים לאמת כי countElements השיטה עובדת כצפוי:

@ Count void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected () {int k = 5; int [] קלט = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] c = CountingSort.countElements (קלט, k); int [] צפוי = {1, 2, 4, 6, 8, 11}; assertArrayEquals (צפוי, ג); }

3.2. מיון מערך הקלט

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

int [] sort (int [] input, int k) {int [] c = countElements (input, k); int [] מיון = int int [input.length]; עבור (int i = input.length - 1; i> = 0; i--) {int current = input [i]; ממוין [c [הנוכחי] - 1] = זרם; c [הנוכחי] - = 1; } להחזיר ממוינת; }

הנה איך סוג השיטה עובדת:

• ראשית, זה מחשב את ג מַעֲרָך
• ואז, זה מאחר את קֶלֶט מערך הפוך ולכל אלמנט ב קֶלֶט, מוצא את המקום הנכון שלו במערך הממוין. ה ith אלמנט ב קֶלֶט צריך להיות ה ג [i] אלמנט במערך הממוין. מכיוון שמערכי Java הם באפס אינדקס, ה- C [i] -1 הכניסה היא ג [i] אלמנט - למשל, ממוינת [5] הוא האלמנט השישי במערך הממוין
• בכל פעם שאנחנו מוצאים התאמה, זה מקטין את המקביל C [i] ערך

באופן דומה, אנו יכולים לאמת כי סוג השיטה עובדת כצפוי:

@Test בטל sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] קלט = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] sorted = CountingSort.sort (קלט, k); // אלגוריתם המיון שלנו ו- Java צריכים להחזיר את אותה התוצאה Arrays.sort (קלט); assertArrayEquals (קלט, ממוין); }

4. בדיקה חוזרת של אלגוריתם המיון לספירה

4.1. ניתוח מורכבות

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

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

בואו נראה כמה זמן זה לוקח למיין את הקלט:

• זה מחשב את ג מערך ב O (n + k) זמן: פעם אחת זה מאתחל מערך קלט עם גודל נ ב עַל) ואז איטרציה של ג ב בסדר) - כך זה יהיה O (n + k) בסך הכל
• לאחר חישוב ה- C, הוא ממיין את הקלט על ידי איטרציה של מערך הקלט וביצוע מספר פעולות פרימיטיביות בכל איטרציה. אז, פעולת המיון בפועל נמשכת עַל)

בסך הכל, ספירת המיון נמשכת O (n + k) זמן לרוץ:

O (n + k) + O (n) = O (2n + k) = O (n + k)

אם נניח k = O (n), ואז ספירת אלגוריתם מיון ממיין את הקלט בזמן ליניארי. בניגוד לאלגוריתמי מיון למטרות כלליות, ספירת מינים מניחה את הקלט ולוקחת פחות מ- O(n יומן n) הגבול התחתון לביצוע.

4.2. יַצִיבוּת

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

• מדוע עלינו לחזור על מערך הקלט לאחור?
• מדוע אנו מקטינים את C [i] בכל פעם שאנחנו משתמשים בזה?

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

באיטרציה הראשונה, עלינו למצוא את המיקום הממוין עבור 1 הראשון:

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

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

מה קורה אם אנחנו לא מקטינים את C [i] ערך לאחר כל שימוש? בוא נראה:

שתי המופעים של מספר 1 מקבלים את המקום האחרון במערך הממוין. אז אם אנחנו לא מקטינים את C [i] ערך לאחר כל שימוש, אנו עלולים לאבד כמה מספרים בזמן מיון אותם!

5. מסקנה

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

כרגיל, קודי המדגם זמינים בפרויקט GitHub שלנו, אז דאגו לבדוק זאת!