الگوریتم مرتب سازی پایه ای (Radix Sort)

radix sort algorithm 7335 تصویر

الگوریتم مرتب سازی پایه ای (Radix Sort)

الگوریتم مرتب سازی پایه ای (Radix Sort) یا مبنایی یکی دیگر از الگوریتم های مرتب سازی است که لیستی با طول ثابت و تعداد عناصر k را در زمان O(kn) مرتب می کند. در این الگوریتم روش کار به این صورت است که ورودی را به بخش های کوچک تقسیم می کنیم (اگر ورودی عدد باشد، به رقم ها و اگر رشته باشد به کاراکترها) و آرایه را بر اساس ارزش بیت ها (رقم یا کاراکتر) از کم ارزش ترین بیت به پر ارزش ترین بیت مرتب می کنیم. به این ترتیب آرایه ما پس از طی k مرحله مرتب می شود.

پیاده سازی Radix Sort

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

امتحان کنید

خروجی:

نکات

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

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