چگونه یک مرتب سازی سطلی انجام می دهید؟

2024 نویسنده: Lynn Donovan | [email protected]. آخرین اصلاح شده: 2024-01-18 08:23

مرتب سازی سطلی به صورت زیر عمل می کند:

1. تنظیم یک آرایه از ابتدا خالی " سطل ها ".
2. Scatter: روی آرایه اصلی بروید و هر شی را در آن قرار دهید سطل .
3. مرتب سازی هر غیر خالی سطل .
4. جمع کنید: بازدید کنید سطل ها به ترتیب و همه عناصر را به آرایه اصلی برگردانید.

علاوه بر این، مرتب سازی سطلی با مثال چیست؟

همچنین، شما کار پیدا خواهید کرد مثال ها از مرتب سازی سطلی در C، C++، جاوا و پایتون. مرتب سازی سطلی هست یک مرتب سازی تکنیکی که مرتب می کند عناصر را ابتدا با تقسیم عناصر به چند گروه به نام سطل ها . عناصر ابتدا به داخل پراکنده می شوند سطل ها سپس عناصر سطل ها هستند مرتب شده است.

علاوه بر این، مرتب سازی سطلی در کجا استفاده می شود؟ مرتب سازی سطلی عمدتاً زمانی مفید است که ورودی به طور یکنواخت در یک محدوده توزیع شود. برای مثال مشکل زیر را در نظر بگیرید. مرتب سازی مجموعه بزرگی از اعداد ممیز شناور که در محدوده 0.0 تا 1.0 قرار دارند و به طور یکنواخت در سراسر محدوده توزیع شده اند.

با در نظر گرفتن این موضوع، چگونه تعداد سطل ها را در یک مرتب سازی سطلی پیدا می کنید؟

اگر سطل ها هر کدام 2^k طول دارد سطل دارای سایز یک و مرتب سازی سطلی به شمارش منحرف می شود مرتب سازی . بنابراین، شما هر کدام را می خواهید سطل اندازه بیشتر از 1 باشد. اگر n داشته باشیم سطل ها ، و msbits(x, k) مقدار 2^k و سپس هر یک را برمی گرداند سطل اندازه 2^k/n است.

پیچیدگی زمانی مرتب سازی سطلی چقدر است؟

میانگین پیچیدگی زمانی برای مرتب سازی سطلی O(n + k) است. بدترین پیچیدگی زمانی O(n²) است. فضا پیچیدگی برای مرتب سازی سطلی O(n+k) است.