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

الگوریتم مرتب سازی لانه کبوتری به نقل از ویکی
الگوریتم مرتب سازی لانه کبوتری از درجه ( 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

---