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

[zahra11]

سلام بچه ها
من در مورد معرفی روش مرتب سازی سریع و مرتب سازی لانه کبوتری(pigeonhole sort) و تاریخچه ان و اینکه چه کسی آن را ابداع کرد و دیگر در مورد تحلیل الگوریتم از لحاظ زمان و مصرف حافظه به زبان فارسی می خوام اگه کسی می تونه به من کمک کنه :ناراحت:

[whitehat]

الگوریتم مرتب سازی لانه کبوتری به نقل از ویکی (http://en.wikipedia.org/wiki/Pigeonhole_sort)
الگوریتم مرتب سازی لانه کبوتری از درجه ( 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] := 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