مرتب‌سازی لانه‌کبوتری
مرتب‌سازی لانه‌کبوتری: (Pigeonhole sort) و به آن مرتب‌سازی شمارش (count sort) هم گفته می‌شود (و با مرتب‌سازی شمارشیcounting sort متفاوت است) یک الگوریتم از درجه (O(n+N است که n تعداد اعدادی است که باید مرتب شوند و N ارزشهای ممکن برای اعداد است.
| رده | الگوریتم مرتب‌سازی |
|---|---|
| ساختمان داده | آرایه |
| کارایی بدترین حالت | ، که N محدودهٔ مقادیر کلید و n اندازهٔ ورودی می‌باشد. |
| پیچیدگی فضایی |
الگوریتم ویرایش
الگوریتم این مرتب‌سازی به صورت زیر است:
۱. یک آرایه از لانه‌های کبوتر ایجاد کنید، هر لانه کبوتر نشانه یک ارزش در بازه کلیدهای موجود است
۲.آرایه اصلی (آرایه‌ای که می‌خواهد مرتب شود) را مرور کنید و هر شیء را در لانه کبوتر مربوط به آن جای دهید
۳. تکرار به ترتیب بر روی آرایه لانه‌های کبوتر، و عقب بردن عنصرها ی لانه‌های کبوتر غیر خالی در آرایه اصلی
یک شبه کد ساده از الگوریتم:
function pigeonhole_sort(array a[n])
----
array b[N]
var i,j
zero_var (b) (* zero out array b *)
for i in [0...length(a)-1]
b[a]:= b[a[i]]+1
[I](* copy the results back to a *)
j:= 0
for i in [0...length(b)-1]
repeat b[i] times
a[j]:= i
j:= j+1
[I](* copy the results back to a *)
j:= 0
for i in [0...length(b)-1]
repeat b[i] times
a[j]:= i
j:= j+1
تحلیل ویرایش
این الگوریتم به این صورت کار می‌کند که ابتدا مینیمم و ماکزیمم اعدادی که در آرایه به ما داده شده‌اند را پیدا می‌کند. سپس یک آرایهٔ کمکی ایجاد می‌کند با این هدف که سایز این آرایهٔ جدید به تعداد تمام اعداد ممکن بین مینیمم و ماکزیمم اعداد باشد. در این آرایه می‌خواهیم در واقع فراوانی هر عدد را نگه داریم و سپس از ابتدای این آرایه شروع کنیم و به تعداد فراوانی هر خانه عدد مربوط به آن خانه را چاپ کنیم. مثال زیر این مطلب را روشن تر می‌کند:
T ۲ ۳ ۱ ۲ ۱ ۳ ۲ ۱ ۴
U: ۰ ۰ ۰ ۰
۱ ۲ ۳ ۴
۱ ۱ ۱ ۲ ۲ ۲ ۳ ۳ ۴
پیاده‌سازی الگوریتم ویرایش
کد جاوای مرتب‌سازی لانه کبوتری به صورت زیر است که نحوهٔ کار آن مطابق با توضیحات ذکر شده در بالا است:
public static void pigeonhole_sort(int[] a)
{
// size of range of values in the list (ie, number of pigeonholes we need)
int min = a[0], max = a[0];
for (int x: a) {
min = Math.min(x, min);
max = Math.max(x, max);
}
final int size = max - min + 1;
// our array of pigeonholes
int[] holes = new int[size];
// Populate the pigeonholes.
for (int x: a)
holes[x - min]++;
// Put the elements back into the array in order.
int i = 0;
for (int count = 0; count <size; count++)
while (holes[count]--> 0)
a[i++] = count + min;