مرتب سازی شمارشی (Counting Sort)
در «مرتب سازی شمارشی (Counting Sort)» تعداد هر مقدار شمرده می شود. سپس با همین شمارش، آرایه مرتب ساخته می شود. این روش مقایسه نمی کند و فقط با اعداد صحیحِ نامنفی کار می کند.
ایده اصلی در یک نگاه
یک آرایه شمارنده بساز. بعد، روی آرایه اصلی بگرد و شمارنده مقدارها را زیاد کن. سپس از روی شمارنده، آرایه مرتب را بازسازی کن.
شرایط استفاده از Counting Sort
- فقط اعداد صحیح: هر مقدار با یک اندیس جور می شود.
- فقط نامنفی: اندیس منفی در آرایه معنا ندارد.
- دامنه محدود: اگر تعداد مقادیر ممکن زیاد شود، روش به صرفه نیست.
پیاده سازی Counting Sort در پایتون
در کد زیر، بیشینه آرایه را پیدا می کنیم تا اندازه آرایه شمارنده درست باشد.
def countingSort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
while len(arr) > 0:
num = arr.pop(0)
count[num] += 1
for i in range(len(count)):
while count[i] > 0:
arr.append(i)
count[i] -= 1
return arr
mylist = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
mysortedlist = countingSort(mylist)
print(mysortedlist)
گام های عملی
- بیشینه آرایه را پیدا کن.
- آرایه شمارنده با اندازه مناسب بساز.
- روی آرایه بگرد و شمارنده ها را زیاد کن.
- از روی شمارنده، آرایه مرتب را بساز.
پیچیدگی زمانی
به طور کلی، زمان برابر O(n+k) است. اگر دامنه مقادیر کوچک باشد، تقریباً O(n) می شود. اما اگر دامنه خیلی بزرگ باشد، کارایی می ریزد و حتی بدتر از O(n^2) می شود.
جمع بندی سریع
- بدون مقایسه مقدارها کار می کند.
- فقط برای اعداد صحیحِ نامنفی است.
- دامنه کوچک، نتیجه سریع می دهد.
- مرتب سازی سریع برای دامنه بزرگ بهتر است.
- مرتب سازی درج در لیست های کوچک مناسب است.