الگوریتم مرتب سازی سطلی (Bucket Sort)

bucket sort algorithm 7345 تصویر

الگوریتم مرتب سازی سطلی (Bucket Sort)

الگوریتم مرتب سازی سطلی (Bucket Sort) زمانی مناسب است که ورودی به صورت یکنواخت در یک رنج توزیع شده باشد. برای مثال مسئله زیر را در نظر بگیرید. مجموعه بزرگ اعداد اعشاری که در رنج ۰٫۰ تا ۱٫۱ قرار دارند و به صورت یکنواخت در آن رنج توزیع شده اند را مرتب کنید. یک روش ساده برای حل این مسئله استفاده از الگوریتم های مرتب سازی مبتنی بر مقایسه است. این گونه الگوریتم ها نمی توانند مسئله فوق را بهتر از nLogn مرتب کنند.

آیا می توانیم آرایه در زمان خطی مرتب کنیم؟ مرتب سازی شمارشی برای حل این مسئله کاربردی ندارد. چون در این الگوریتم از کلیدها به عنوان اندیس استفاده می شود، اما در اینجا کلیدهای به صورت اعداد اعشاری هستند. یک ایده مناسب استفاده از الگوریتم مرتب سازی سطلی است. در زیر الگوریتم مربوط به Bucket Sort را مشاهده می کنید:

پیاده سازی الگوریتم Bucket Sort

در زیر می توانید نحوه پیاده سازی الگوریتم مرتب سازی سطلی در زبان سی پلاس پلاس را مشاهده کنید:

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی در بدترین حالت برابر است با O(n2).
  • پیچیدگی زمانی در حالت متوسط برابر است با O(n + k).
  • پیچیدگی فضایی در بدترین حالت برابر است با O(n . k).
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است