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

[zahra11]

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

[whitehat]

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