אז לא הבנתי. אם כך זה לא ניתן ב-(1)O אלא ב-(O(n

אין כזה דבר מיון ב-(o(1. במינימום אתה צריך לבצע מעבר אחד על הנתונים שלך, שזה (o(n.

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

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

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

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

נ.ב. ממש מציק לכתוב (O(n

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

נכון, ואז מה הקטע של bucket sort? יהיה לך מערך של דליים ובמעבר אחד שים כל איבר בתא המתאים לו וזהו. זה כבר דומה יותר ל-hashing.

כי במיון דליים אין שום דרישה שמספר הדליים יהיה זהה למספר האיברים.

יכול להיות שיהיו n איברים ו-k דליים, ככה שבכל דלי יש בתוחלת (o(n/k איברים.

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

נו, ואז לא יהיה לך איבר אחד בכל דלי.

נכון, למה שיהיה לך? מיון דליים הוא כללי יותר מזה.

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

טוב..עוד שאלה אחרונה לתקופה הקרובה(מקווה..)

בקשר לסעיף ב פה:

http://www.fastup.co.il/images/1548587.bmp

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

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

1. hash ולא hush.

2. אם פונקציית הגיבוב מכניסה מפתח שונה לאותו תא, הרי שהיא לא מוצלחת אבל גם זה יכול לקרות. יוצרים רשימה מקושרת ואז במקום (1)O

תקבל O של אורך הרשימה.

אוקי..ועדיין אפשר לומר שבממוצע זה o(1) ?

אם לא אז מה הפתרון לשאלה?