الگوریتم مرتب سازی لانه کبوتری (Pigeonhole Sort)

  • چهارشنبه 20 نوامبر 2019
  • بازدید ۵۹ نفر

pigeonhole sort algorithm 7379 تصویر

الگوریتم مرتب سازی لانه کبوتری (Pigeonhole Sort)

الگوریتم مرتب سازی لانه کبوتری (Pigeonhole Sort) یک الگوریتم مرتب سازی غیر مقایسه ای است که برای برای لیست هایی که عناصر آن ها مقادیر عددی هستند و همچنن لیست هایی ، اعداد ممکن برای مقادیر کلید نیز تقریبا مشابه اند، مناسب است. این الگوریتم از درجه O(n + Range) است که در آن n تعداد عناصر آرایه ورودی و Range تعداد مقادیر ممکن در آرایه است.

نحوه کار الگوریتم Pigeonhole Sort

  • ابتدا مقادیر کمینه و بیشینه را در بین عناصر آرایه پیدا می کنیم. سپس مقدار کمینه را min و مقدار بیشینه را max نامگذاری می کنیم.
  • مقدار Range را به شکل max-min+1 بدست می آوریم.
  • یک آرایه به اندازه Range با نام “pigeonholes” و مقدار اولیه خالی ایجاد می کنیم.
  • هر یک از عناصر را بررسی و در لانه کبوتری خودش قرار می دهیم. عنصر موجود در اندیس arr[i]، در لانه ای که دارای اندیس arr[i] – min است، قرار می گیرد.
  • حلقه را در سراسر آرایه “pigeonholes” اجرا می کنیم و عناصر لانه هایی که خالی نیستند را در آرایه اصلی قرار می دهیم.

الگوریتم Pigeonhole Sort و Counting Sort

تفاوت اصلی موجود بین این دو الگوریتم مرتب سازی در این است که در مرتب سازی لانه کبوتری، عناصر دوبار جا به جا می شوند. بار اول به آرایه pigeonhole و بار دوم به آرایه اصلی.

pigeonhole sort algorithm 7379 تصویر

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

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

امتحان کنید

خروجی:

از آنجا که موارد مورد نیاز برای الگوریتم مرتب سازی لانه کبوتری به ندرت تامین می شود، استفاده از آن بسیار محدود است. در آرایه هایی که در آن مقدار Range بزرگتر از مقدار n است، الگوریتم Bucket Sort کارایی بهتری دارد.

نکات

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

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