לאלה שמכירים ומבינים Counting Sort

[lalal6]

לאלה שמכירים ומבינים Counting Sort

http://he.wikipedia.org/wiki/מיון_מנייה

כאן מתואר האלגוריתם.

דבר ראשון, מדוע מבצעים את השורה zz C = C + C[i - 1] zz

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

אני לא מבין את שתיי השורות האחרונות של האלגוריתם (איפה שכתוב "בשלב הבא עוברים על מערך A מהסוף להתחלה...").

אנסה לתרגם למילים את השורה zz B[ C [ A[ i ] ] ] zz מהחלק הפנימי, לחיצוני: גש לתא באינדקס [ A [ i במערך C. מה יש שם? את מספר האיברים במערך A, שקטנים או שווים ל- [ A[ i . נקרא למספר הזה x.

ניגש למערך B באינדקס x, ונשים בו את [ A[ i

אם אני מבין נכון, זה מה שעושה השורה הראשונה מבין שתיי השורות הללו.

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

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

כלומר הקטן ב-1 את מספר האיברים שקטנים או שווים ל- [ A [ j .

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


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

המון תודה למי שעוזר!

 

[מכור אנונימי לקולה]

הסבר.

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

 

[אורי769]

שאלה

האם נסית להריץ את האלגוריתם על קלט פשוט? אם לא, הנה קלט לדוגמא
[2,5,1,2]
מערך בן ארבע כניסות. n=4 ובמקרה זה k=5. נסה לבנות בצורה מסודרת את המערך C וממנו את B כפי שהאלגוריתם מציע.

 

[lalal6]

בנייה ע"פ האלגוריתם

אכן, k=5 מאחר וטווח הערכים במערך המקורי שנתת חסום ע"י 5. לכן במערך C (מערך המונים) יהיו חמישה תאים.

עתה, מאתחלים את התאים במערך C ל- 0 (זו הלולאה הראשונה באלגוריתם).

כעת, עוברים על מערך הקלט, ולכל אינדקס i במערך הקלט, רואים איזה מספר מופיע במערך הקלט באינדקס i, נקרא למספר הזה x.

x כמובן חסום ע"י 5. ניגש לאינדקס x במערך C ונגדיל ב-1 את הערך באינדקס זה.

בסיום המעבר הזה (על מערך הקלט, שבמהלכו עושים את התהליך שתארתי), נקבל מערך C שבתא ה-i-י שלו, נמצא מספר המופעים של הערך i במערך הקלט.

ז"א, מערך המונים (בשלב הזה) נראה כך: [1,2,0,0,1] = C

כבר בשלב זה, יש לי 2 שאלות...מדוע אני לא יכול לסיים כאן את האלגוריתם? הרי המערך C אומר לי כמה פעמים 0 מופיע במערך המקור, כמה פעמים 1 מופיע במערך המקור,..., כמה פעמים 5 מופיע במערך המקור.

אז אני יכול פשוט להדפיס את 0 (כמספר הפעמים שהוא מופיע במערך המקור), את 1 (כמספר הפעמים שהוא מופיע במערך המקור) וכך הלאה, עד ל-5 (כמספר הפעמים שהוא מופיע במערך המקור).
ויוצא בעצם שהדפסתי את האיברים ממויינים. מה הבעיה כאן?? למה זה לא נכון??

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



חזרה לאלגוריתם המקורי....

לכל אינדקס i שגדול מ-1, נבצע את הפעולה: zz C <-- C[i-1] + C zz , במילים זה אומר שלכל תא, סוכמים את מה שיש בו ועוד מה שיש בתא שלפניו.

לכן המערך C, יקרא כעת כך: zz C = [1,3,3,3,4] zz.

עתה, נעבור על המערך המקורי מהסוף להתחלה. בתא האחרון יש 2. ניגש לאינדקס 2 במערך C. מה יש שם? 3. ניגש לאינדקס 3 במערך הפלט ונכתוב שם 2 (הערך הנוכחי שאנחנו עוברים עליו במערך הקלט), נפחית ב-1 את הערך באינדקס 2 במערך C, וכעת יהיה בו 2.

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

בתא השני במערך המקור יש 5. ניגש לאינדקס 5 במערך C. מה יש שם? 4. ניגש לאינדקס 4 במערך התוצאה ונכתוב לתוכו 5...מפחיתים ב-1 כמו קודם.

בתא הראשון במערך המקור יש 2, ניגש לאינדקס 2 במערך C, יש שם 2 (לא 3 כי כבר הפחתנו ב-1). ניגש לאינדקס 2 במערך התוצאה ונכתוב לתוכו 2.

בסיכומו של דבר, אם לא טעיתי, המערך C הסופי יראה כך: zz C = [0 , 2, 3, 3, 3] zz והמערך תוצאה יראה כך:

zz B = [1,2,2,5] zz. אכן הוא ממויין.

הדבר הראשון שלא ברור לי, זה למה אנחנו סוכמים את מה שיש בתא i עם מה שיש בתא i -1.

גם אחרי שהרצתי את הדוגמה, אני באותו מצב בערך.

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

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

ותודה לך על העזרה.

 

[אורי769]

תשובות

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

המערך C בשלב הראשון אכן מכיל כבר את כל האינפורמציה. האינטגרציה שעושים לו (כך אני קורא לפעולה של החיבור של כל איבר עם קודמו. נסה לחשוב למה) לא מוסיפה לו אינפורמציה, אלא רק מפשטת את העבודה איתו. כדי להבין זאת צירפתי תמונה. בתמונה, העמודות הירוקות מייצגות את מערך C משמאל לימין. קל לראות שהמשלים למלבן משמאל, אם נפרוט אותו לשורות, הוא בדיוק מערך B המבוקש. אם הבנת את זה גם קל יותר להבין את התהליך של חישוב B מ-C דרך התרשים הזה. כאשר שמים את 2 (האחרון) ניגשים לעמודה 2 ורואים שגובהה הוא 3. לכן ה-2 צריך לתפוס את השורה השלישית. כעת ניתן למעשה לשים "פס" על השורה השלישית, כי כבר איישנו אותה. מבחינה אלגוריתמית טהורה, זה מצריך להפחית 1 לא רק מהכניסה ה-2 של C, אלא גם מכניסה 3 ו-4. אלא מה, זה מיותר, כי אנו יודעים שאין 3 ו-4 במערך המקורי.

 

[samini]

השכלתי מתשובותייך אורי

כל הכבוד תודה על האינפורמציה

 

[samini]

השכלתי מתשובותייך אורי

כל הכבוד תודה על האינפורמציה