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

יש לי כמה שאלות -

1. האם מיון סלים הוא אותו מיון המוכר לי בשם מיון דלי? (Bucket sort)
2. אחד המשפטים בערך -

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

נראה לי תמוה מעט. ברור לי שהטענה לא נכונה כמו שהיא, (מאחר וכפי שצויין בערך, מיוני השוואה פועלים בסיבוכיות של לפחות $\ \Omega (nlog(n))$) אבל אולי הכותב התכוון שבתנאים מסויימים ניתן לחסוך בזמן הריצה על חשבון הזכרון? אם כן, חשוב יהיה להבהיר באילו מקרים. (מיון דלי, מיון בסיס ומיון מנייה למשל פועלים בזמן ריצה ליניארי אבל מניחים הנחות ביחס לקלט שלהם) יובל מדר

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

- הכן מערך בגודל N.
- עבור על המערך, ובל תא במערך תעשה זאת:
     - הכנס את האובייקט a[i] לתא a[i] במערך (כשהאינדקסים מתחילים ב 1).

כך אתה עושה את זה. יש כמה בעיות בזה: הנחנו הנחה מאוד מאוד בוטה - שהמערך הוא פרמוטציה. אתה יכול לשנות את זה לכך שזה יעבוד על מספרים כלליים, ראה מיון דלי. החסם התחתון $\ \Omega (nlog(n))$ הוא רק לאלגוריתמיי השוואה, והוא נכון כשאתה לא מניח הנחות מיוחדות. אני לא יכול להגיד לך בדיוק תחת אילו הנחות זמן הריצה יכול להיות לינארי, בגלל שיש מספר אינסופי של הנחות מתמטיות אפשריות. זה פשוט להבין למה פרמוטציה זו דרישה כזו, למה Abs(A[i+1] - A[i])=1 זו הנחה כזו, ויש עוד רבות כאלו. --Ekuurh - שיחה 21:39, 15 במאי 2011 (IDT)

גם לי יש שאלה:

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

שינוי שם

לאלגוריתם מיון. כמו אלגוריתם חיפוש‎. יוניון ג'ק - שיחה 12:49, 30 בספטמבר 2023 (IDT)

בוצע. ברק אברגיל ~ דברו איתי ~ זוכרים את המוזיקה הישראלית ~ מיזם האירוויזיון 23:11, 8 באוקטובר 2023 (IDT)