שאלה על מיון מערך

[demultiplexer]

שאלה על מיון מערך

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

 

[vinney]

בוודאי שיש

יש הרבה מיונים שונים ומשונים. מה שאתה עשית זה אכן מיון בועות. תחפש בגוגל על מיון מיזוג, זה אחד מהיותר פשוטים למימוש, ויעיל ביותר (רקורסיבי ודורש זכרון נוסף בגודל המערך הממוין). יש כל מיני דברים גם כמו quicksort (יש לזה פונקציה ב ANSI C אפילו) שאתה יכול להשתמש בהם. אם אתה יודע משהו על האיברים במערך (גדלים או משהו), אז אתה יכול להשתמש במיונים יעילים יותר אפילו, כמו למשל Bucket sort.

 

[demultiplexer]

מיון בועות יותר יעיל

התחלתי לקרוא על מיון בועות בwebmaster. לפי הנסיונות שהרצתי המיון בועות שאני חשבתע עליו יעיל יותר. כמו שכתבתי אני משווה כל איבר במערך איברים אחרים מהמערך אבל מסוף במערך לתחילתו. כלומר אני לוקח את איבר 0 ומשווה אותו לאיבר N אם הוא קטן מאיבר N אני מחליף ביניהם אם לא אני משווה אותו מול איבר N-1 וכך הלאה. זה יוצא הרבה פחות חזרות מאשר אם אני בודק צמדים כמו שמראים בWEBMASTER.

 

[demultiplexer]

טעות שלי זה אותו דבר

 

[vinney]

זה PIVOT, לא בועות

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

 

[BeyondTheWall]

המקרה הגרוע ביותר ...

במקרה הגרוע ביותר לא חשוב באיזו שיטת מיון נשתמש הסיבוכיות היא N נכון?

 

[vinney]

כלל וכלל לא

מיון ניתן לעשות מינימום בNLOG N במקרה הגרוע ביותר (לדוגמא מיון מיזוג). בPIVOT או מיון בועות המקרה הגרוע ביותר מניב סיבוכיות של N^2.

 

[BeyondTheWall]

הכוונה הייתה לN^2, התבלבלתי ...

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

 

[IP yuval]

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

להחליף בין כל שתי תאים קרובים במערך אם הם לא ממוינים. ככה לרוץ על כל המערך הרבה פעמים עד שיש סיבוב שלם בלי החלפות - המערך ממוין. נראה לי שאתה עשית מיון בחירה - מצאת כל פעם את האיבר הקטן ביותר בחלק הלא ממוין במערך, ולחליף בינו לבין האיבר הראשון(שני/שלישי...), אח"כ לרוץ שוב... שניהם לא יעילים במיוחד, אבל כל אחד יעיל יותר למקרה אחר. יכול להיות שאני טועה.

 

[demultiplexer]

אז ככה..

עשיתי couner-ים. במיון בועות רגיל, במערך בעל 7 ספרות אני רץ 21 פעמים על המערך ומבצע 10 החלפות ובPIVOT 4 החלפות. אבל לא חשבתי על זה שעדיף לרוץ עד שיש סבב בו אין החלפות וזהו. אני תמיד רצתי כמספר האיברים במערך. עכשיו אני ישפר גם את זה. אני צריך לממש עמוד בו ניתן לדרג פריטים. הפריטים נמצאים בבסיס נתונים. מה שעשיתי עד עכשיו זה על כל עדכון של עדיפות לשלוח את הטופס לשרת לעדכן את בסיס הנתונים ואז לקבל את הטבלה מסודרת לפי הדירוג החדש. עכשיו החלטתי לשפר את זה ולהעביר לצד לקוח. לאחר שכחל הדירוגים יתבצעו הטופס יישלח פעם אחת לשרת. העניין הוא שאני רוצה בכל שינוי של עיפות לשנות את מראה הדף ולסדר את הטבלה לפי העדיפויות החדשות.

 

[demultiplexer]

איך בכלל אני אמור לבחור סוג מיון

לכתוב אלגוריתם לכל סוג להריץ ולבדוק מה יותר יעיל ? או שיש דרך לחשב או להחליט איזה יותר יעיל לכל מצב ואז לכתוב אלגוריתם ?

 

[vinney]

לכתוב תוכנית שמממשת אלגוריתם

סוג מיון <=> אלגוריתם. לכל אלגוריתם יש חסמים למקרה הגרוע ביותר, חלק מהאלגוריתמים מתנהגים שונה במקרה הגרוע ביותר ובמקרה הממוצע (למשל - PIVOT, או QUICKSORT המבוסס עליו), ועבור חלק החסם הוא הדוק, וסיבוכיות היא קבועה בכל מקרה (כמו מיון מיזוג).

 

[demultiplexer]

לפי מה שקראתי בויקפידה

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

 

[vinney]

נכון

אבל הרעיון דומה (או שלא הבנתי מה ניסית לעשות?)

 

[demultiplexer]

זה מה שעשיתי

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

 

[demultiplexer]

זה הבועות הרגיל

 

[® רן]

נחמד אבל

1. מה שחשוב הוא לא מספר ההחלפות אלא מספר ההשוואות, שהוא שווה למספר הסיבובים שהלולאות רצות (בתוכנית שלך, אתה סופר את זה כ roundCntr). נכון שמבחינה מעשית החלפה לוקחת יותר זמן מהשוואה, אבל גם השוואה היא פעולה. סיבוכיות של אלגוריתם נמדדת במדעי המחשב ככמות פעולות כפונקציה של הקלט - משך הזמן שלוקח לבצע פעולה בודדת אינו משנה. האלגוריתם שלך ומיון בועות שניהם מבצעים את אותו מספר של פעולות השוואה (O(N^2. 2. ניתן לשפר את האלגוריתם (גם שלך וגם את הבועות) ע"י תנאי שאומר שאם בריצה מסוימת של הלולאה הפנימית לא בוצע אף חילוף, הרי שהמערך כבר ממויין ואפשר לעצור. זה לא עוזר למקרה הגרוע ביותר אבל עוזר במקרים ממוצעים. 3. ניתן להוכיח מתמטית שכל אלגוריתם מיון חייב לבצע לפחות (N*log(N השוואות.

 

[vinney]

לגבי 3 - כל אלגוריתם ג'נרי

 

[demultiplexer]

תקנו אותי אם אני טועה אבל בשיטה שלי

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

 

[® רן]

נראה לי שאתה צודק

בשיטה שלך, אם המערך הוא (למשל)

[1,9,8,7,6,5]​

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