מיון דליים

[FireStar]

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

הוא גם נתן לנו משימות לבית :

הרעיון במיון דליים הוא יצירת מערך זמני שהגודל שלו יהיה גודל תחום הערכים המוגבל וערכי איבריו יהיה 0. בשלב השני נעבור על ריברי המערך a (בגודל n), ועבור כל ערך בתא נגדיל ב- 1 את התא במערך Temp עם אינדקס שערכו שווה לערך התא במערך a. כאשר נסיים לעבור על איברי המערך a, המערך Temp יכיל את מספר המופעים של כל ערך שמופיע במערך a. עתה נוכל בעצם לעבור על המערך Temp ולבנות באמצעותו את המערך a בצורה ממויינת.

א. בהנחה שגודל מערך a הוא n, וגודל מערך Temp הוא m, כתוב מהי סיבוכיות הזמן.

ב. כתוב פונקציה אשר תקבל מערך a בגודל n המכיל ציונים (בין 0-100). על הפונקציה למיין את המערך a בשיטת הדליים (++C).

אז איך בדיוק הדליים קשורים פה? מהי הסיבוכיות ואיך הפונקציה הזאת נראית?

[Holy]

הסיבוכיות היא

O(n+m)

או

O(max(n,m))

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

לכתוב פונקציה כזאת? אני בטוח שאתה מסוגל לכתוב לבד

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

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

קוראים לזה דליים (פעם ראשונה שאני שומע את השם הזה) כי בעצם יש לך דלי לכל ערך ועבור כל ערך שאתה מוצא אותה שם אותו בדלי המתאים ובסוף עובר על כל הדליים ובונה את המערך.

זה המיון הכי פשוט שיש גם מבחינת הבנה וגם מבחינת מימוש.

[FireStar]

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

[kikkler]

bubble sort doesnt sort in lg(n), it sorts in n^2

there are far more complicated sorting algorithms than bin sort, it just that most of them don't base on foreknowledge you have about your input. considering you dont know Nothing, there's no way you can sort in less than nlg(n) (mathematically proved)

p.s - n+m > lg(n)

[ktbnus]

מצאתי אתר אחד שאולי יכול לעזור לך..

מימושים של כל מיני אלגוריתמים של מיון המחשה שלהם

המימושים הם ב JAVA אבל זה לא ממש משנה

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

[elico]

מיון בכלל לא משהו

ולא מבין מאיפה הוא דפק את השם הזה

יותר הגיוני לקרוא לזה מיון אינדקס או משהו כזה

ובכללי שיטת המיון הטובה ביותר היא ראדיקס

[ktbnus]

ובכללי שיטת המיון הטובה ביותר היא ראדיקס

מה שנכון נכון

[kikkler]

there's no "best" sorting algorithm, it dependes on the Circumstances

and even if there was, it wouldn't be radix sort

[FireStar]

מיון בכלל לא משהו

ולא מבין מאיפה הוא דפק את השם הזה

יותר הגיוני לקרוא לזה מיון אינדקס או משהו כזה

ובכללי שיטת המיון הטובה ביותר היא ראדיקס

גם אנחנו בהרצאה לא בדיוק הבנו מאיפה הוא הקריץ את הדליים הללו...

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

ותודה לכל העוזרים

[rk666]

מיון דליים == bucket soft

זה המיון הבסיסי,

עד כמה שאני יודע המיון הכי טוב הוא quicksort (לא הבסיסי, יש טיפה יותר מתקדם שהוא nlogn)

זה גם מה שיש בSTL.

[icebreak]

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Sort_algorithm

וגם

http://en.wikipedia.org/wiki/NIST_Dictionary_of_Algorithms_and_Data_Structures

http://en.wikipedia.org/wiki/List_of_algorithms

[DXT]

אייס, תגיד, לא קל יותר פשוט לשים קישור לויקיפדיה בחתימה שלך או משהו?

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

[kikkler]

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

youre kidding right ?

[DXT]

אופס, התבלבלתי עם Counting-Sort (שגם הוא, אגב, רץ בזמן לינארי).

אני אצטט את "מבוא לאלגוריתמים" בקשר למיון דלי:

מיון דלי מבוסס על חלוקת הקטע (0,1] ל- n תת-קטעים או דליים (buckets), שווים בגדלם, ופיזור מספרי הקלט בין הדליים השונים.

...

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

וצריך כמובן לזכור ש-

מיון דלי מניח שהקלט נוצר על-ידי תהליך אקראי המפזר את האיברים בהתפלגות אחידה בקטע (0,1].

עכשיו זה צריך להיות יותר ברור

[Ghosthunter]

COUNTING SORT סופר כמה יש לפיו וממיין לפי זה.