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

مرتب سازی لانه کبوتری (Pigeonhole Sort) یک الگوریتم مرتب سازی است. این الگوریتم برای مرتب‌سازی لیستی از عناصر مناسب است که در آن، عناصر لیست مقادیر عددی هستند. همچنین، اعداد ممکن برای مقادیر کلید نیز تقریبا مشابه هستند. الگوریتم مرتب سازی لانه کبوتری از درجه (O(n + Range است که در آن، n تعداد عناصر در آرایه ورودی و Range تعداد مقادیر ممکن در آرایه است. در این مطلب، الگوریتم مرتب سازی لانه کبوتری مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و «پایتون» (Python) انجام شده است.

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

در ادامه، الگوریتم مرتب سازی لانه کبوتری ارائه شده است.

• مقادیر کمینه (Minimum) و «بیشینه» (Maximum) را در آرایه را پیدا کن. مقادیر کمینه و بیشینه را به ترتیب min و max نام‌گذاری کن. همچنین، مقدار range را به صورت max-min-1 محاسبه کن.
• آرایه‌ای با مقدار اولیه خالی «pigeonholes» هم‌سایز با range بساز.
• هر عنصر آرایه را ملاقات کن و سپس، هر عنصر را در لانه کبوتری خودش قرار بده. عنصر [arr[i در لانه دارای اندیس arr[i] – min قرار می‌گیرد.
• حلقه را به ترتیب در سراسر آرایه pigeonhole اجرا کن و عناصر لانه‌های خالی را در آرایه اصلی قرار بده.

مقایسه مرتب سازی لانه کبوتری و مرتب‌سازی شمارشی

مرتب سازی لانه کبوتری شبیه به «مرتب سازی شمارشی» (Counting Sort) است. تفاوت اصلی این دو الگوریتم مرتب‌سازی با یکدیگر در آن است که در مرتب سازی لانه کبوتری آیتم‌ها دو بار جا به جا می‌شوند؛ یک بار به آرایه سطل و بار دیگر به مقصد نهایی.

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

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

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

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

خروجی قطعه کدهای بالا به صورت زیر است.

Sorted order is : 2 3 4 6 7 8 8

به دلیل آنکه نیازمندی‌های مرتب سازی لانه کبوتری به ندرت تامین می‌شوند، استفاده از این الگوریتم بسیار محدود است.

برای آرایه‌هایی که range در آن‌ها بزرگ‌تر از n است، «مرتب‌سازی سطلی» (Bucket Sort) تعمیمی است که از جهت فضای مصرفی و زمان، کارایی بیشتری دارد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش ساختمان داده‌ها با C و ++C (همراه با حل نمونه سوالات کنکور ارشد)
• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده
• معرفی تکنیک‌های مرتب‌سازی (Sorting Techniques) — ساختار داده و الگوریتم ها

^^