مرتب‌سازی رتبه‌ای

**مرتب‌سازی رتبه‌ای**  یا مرتب‌سازی سرشماری  یک الگوریتم مرتب‌سازی از مرتبه‌ی زمانی O(n^2) است که در آن برای مشخص کردن جایگاه هر عدد در لیست مرتب شده، تعداد عناصر کوچک‌تر از آن شمرده می‌شود.

این الگوریتم با توجّه به این که ورودی در یک داده‌ساختار میانی ذخیره می‌شود، یک نوع مرتّب‌سازی توزیعی است.

## تحلیل

بندانگشتی|محاسبه‌ی رتبه‌ی هر عنصر در مرتب‌سازی رتبه‌ای|400px

### روش کار
برای به دست آوردن رتبه‌ی هر عنصر، کافی است تعداد اعداد کوچک‌تر از آن را بشماریم. شکل مقابل، نمونه‌ای از این کار را نشان می‌دهد.

### عملکرد
مرتبه‌ی زمانی اجرای مرتب‌سازی رتبه‌ای در تمام حالت‌ها O(n^2) است؛ زیرا مستقل از مرتب بودن یا نبودن آرایه‌ی ورودی، محاسبه‌ی رتبه‌ی تمام عنصرها لازم است. با این حال، می‌توان با پردازش موازی زمان اجرا را بهبود داد. با استفاده از n پردازنده، می‌توان زمان اجرا را به O(n) رساند؛ در این حالت، هر پردازنده با اجرای یک حلقه، رتبه‌ی یک عنصر را محاسبه می‌کند. با وجود عملیاتی نبودن، می‌توان با استفاده از n^2 پردازنده زمان اجرای الگوریتم را تا O(lg(n)) هم کاهش داد.

## پیاده‌سازی
### پیاده‌سازی ترتیبی
قطعه کد زیر، پیاده‌سازی ترتیبی مرتب‌سازی رتبه‌ای را به زبان پایتون نشان می‌دهد. در این قطعه، آرایه‌ی نامرتب Input به صورت مرتب شده در آرایه‌ی Output ذخیره می‌شود.

```python
for i in range(n):
    rank = 0 # Number of elements less than Input[i]
    for j in range(n):
        if Input[j] < Input[i]:
            rank += 1
    Output[rank] = Input[i] # Put Input[i] in output array based on its rank
```


اگر لیست اولیه شامل اعداد تکراری باشد، قطعه کد بالا درست کار نمی‌کند؛ اما می‌توان با اعمال تغییراتی، این مشکل را برطرف کرد. قطعه کد زیر، نسخه‌ی بهبود یافته‌ی مرتب‌سازی رتبه‌ای را به زبان پایتون نشان می‌دهد.


```python
Output = [None] * n

for i in range(n):
    rank = 0 # Number of elements less than Input[i]
    for j in range(n):
        if Input[j] < Input[i]:
            rank += 1
    
    while Output[rank] is not None: # As long as an element has the same rank
        rank += 1
    
    Output[rank] = Input[i] # Put Input[i] in output array based on its rank
```


### پیاده‌سازی موازی

بندانگشتی|روش‌های پیاده‌سازی موازی مرتب‌سازی رتبه‌ای|300px

از آن جا که محاسبه کردن رتبه‌ی هر عنصر مستقل از عناصر دیگر است، می‌توان مرتب‌سازی رتبه‌ای را به صورت موازی پیاده‌سازی کرد. از دیدگاه تئوری، با این کار می‌توان زمان اجرای این الگوریتم را تا O(1) کاهش داد. برای پیاده‌سازی موازی روش‌های مختلفی وجود دارد. دو تا از این روش‌ها عبارت‌اند از:

الف) عناصر آرایه را طوری بین پردازنده‌ها تقسیم کنیم که هر پردازنده، رتبه‌ی تعدادی از عناصر را محاسبه کند.

ب) آرایه به چند بخش تقسیم کنیم و در اختیار هر پردازنده قرار دهیم. هر پردازنده رتبه‌ی تمام عناصر را در لیستی که در اختیار دارد محاسبه می‌کند (رتبه‌ی جزئی). رتبه‌ی نهایی حاصل جمع رتبه‌های جزئی است.

قطعه کد زیر، پیاده‌سازی موازی مرتب‌سازی رتبه‌ای در زبان سی شارپ را نشان می‌دهد.

برای آسان‌تر شدن پردازش موازی، از یک آرایه‌ی واسط به نام آرایه‌ی رتبه‌ها  استفاده می‌شود که در جایگاه iاُم آن، رتبه‌ی iامین عنصر آرایه‌ی ورودی قرار می‌گیرد. اگر این آرایه را با R نشان دهیم

```python
Output[R[i]] = Input[i]
```


## جستارهای وابسته
* الگوریتم‌های مرتب‌سازی

## منابع

## پیوند به بیرون
* مرتب‌سازی رتبه‌ای به زبان سی
* مرتب‌سازی رتبه‌ای و مرتب‌سازی پایه‌ای 

رده:الگوریتم‌های مرتب‌سازی
رده:مرتب‌سازی‌های پایدار