מיון דלי (Bucket Sort)

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

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

 

הקוד של האלגוריתם ב פסאודו קוד

BUCKET-SORT(A)
  n <- length[A]
  for i <- 1 to n
    insert A[i] into list B[nA[i]]
  for i <- 0 to n-1
    sort list B[i] with insertion sort
  concatenate the lists B[0], B[1], .., B[n-1] together in order

להלן פעולתו של מיון דלי על מערך בן 10 מספרים

Bucket Sort Algorithm

הקוד מניח שהקלט הוא מערך A בן n איברים, ושכל איבר [A[i במערך מקיים 1 > [A[i => 0 הקוד דורש מערך עזר [B[0..n-1 של רשימות מקושרות (דליים), ומניח שקיים מנגון לטיפול ברשימות כאלה.

 

הסבר מופשט:
תנאי הכרחי לא

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

  • כמו שציינתי בעבר, במדעי המח

    1. נקבל מערך: { 30, 10, 9, 6, 5, 4, 3, 1 }. A זהו מצביע למערך, p זה מצביע לתחילת המערך (תא מס’ 0), r מצביע לסוף המערך (תא מס’ 7), ו x זהו הערך שאנחנו מחפשים, בואו ניקח לדוגמה את 10.
    2. שורה 2: אם r < p אז.., מכיוון

סיבוכיות זמן ריצה: ((O(n*d רץ בתחולת זמן לינארית אם מקורו של הקלט בהתפלגות אחידה. סיבוכיות מקום: תלויה במיון היציב בו אנו משתמשים.