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

مرتب سازی لانه کبوتری: ( Pigeonhole sort ) و به آن مرتب سازی شمارش ( count sort ) هم گفته می شود ( و با مرتب سازی شمارشیcounting sort متفاوت است ) یک الگوریتم از درجه ( O ( n+N است که n تعداد اعدادی است که باید مرتب شوند و N ارزشهای ممکن برای اعداد است.
الگوریتم این مرتب سازی به صورت زیر است:
۱. یک آرایه از لانه های کبوتر ایجاد کنید، هر لانه کبوتر نشانه یک ارزش در بازه کلیدهای موجود است
۲. آرایه اصلی ( آرایه ای که می خواهد مرتب شود ) را مرور کنید و هر شیء را در لانه کبوتر مربوط به آن جای دهید
۳. تکرار به ترتیب بر روی آرایه لانه های کبوتر، و عقب بردن عنصرها ی لانه های کبوتر غیر خالی در آرایه اصلی
یک شبه کد ساده از الگوریتم:
function pigeonhole_sort ( array a ) - - - - array b var i, j zero_var ( b ) ( * zero out array b * ) for i in b:= b]+1 ( * copy the results back to a * ) j:= 0 for i in repeat b times a:= i j:= j+1 ( * copy the results back to a * ) j:= 0 for i in repeat b times a:= i j:= j+1 تحلیل این الگوریتم به این صورت کار می کند که ابتدا مینیمم و ماکزیمم اعدادی که در آرایه به ما داده شده اند را پیدا می کند. سپس یک آرایهٔ کمکی ایجاد می کند با این هدف که سایز این آرایهٔ جدید به تعداد تمام اعداد ممکن بین مینیمم و ماکزیمم اعداد باشد. در این آرایه می خواهیم در واقع فراوانی هر عدد را نگه داریم و سپس از ابتدای این آرایه شروع کنیم و به تعداد فراوانی هر خانه عدد مربوط به آن خانه را چاپ کنیم. مثال زیر این مطلب را روشن تر می کند: T ۲ ۳ ۱ ۲ ۱ ۳ ۲ ۱ ۴
U: ۰ ۰ ۰ ۰ ۱ ۲ ۳ ۴
۱ ۱ ۱ ۲ ۲ ۲ ۳ ۳ ۴