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

[آبجی]

الگوریتم مرتب سازی لانه کبوتری به نقل از ویکی
الگوریتم مرتب سازی لانه کبوتری از درجه ( O(n+N است که n تعداد اعدادی است که باید مرتب شوند و N ارزشهای ممکن برای اعداد است. (لانه های کبوتر) .
الگوریتم به ترتیب زیر است
1) یک آرایه از لانه های کبوتر ایجاد کنید ، هر لانه کبوتر نشانه یک ارزش در بازه کلیدهای موجود است
2) آرایه اصلی (آرایه ای که می خواهد مرتب شود) را مرور کنید و هر شیء را در لانه کبوتر مربوطه به آن جای دهید
3) تکرار به ترتیب بر روی آرایه لانه های کبوتر ، و عقب بردن عنصر ها ی لانه های کبوتر غیر خالی در آرایه اصلی



کد:


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[i]] := b[a[i]]+1

(* 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