شمارش مرتب یک الگوریتم منظم کارآمد است که برای مرتب کردن اعداد صحیح در یک محدوده خاص استفاده می شود.این با شمارش تعداد وقوع هر مقدار و سپس محاسبه موقعیت هر عنصر در آرایه مرتب شده کار می کند.این روش به ویژه هنگامی مفید است که دامنه داده های ورودی به طور قابل توجهی بزرگتر از تعداد عناصر به نوع نیست.

چگونه شمارش انواع کارها

الگوریتم با ایجاد یک آرایه شمارش شروع می شود که فرکانس هر مقدار را در داده های ورودی ذخیره می کند، سپس این آرایه شمارش را اصلاح می کند تا شامل موقعیت های واقعی هر عنصر در خروجی مرتب شده باشد.در نهایت، آن آرایه مرتب شده را با قرار دادن عناصر در موقعیت های صحیح خود بر اساس آرایه شمارش ایجاد می کند.

مثال محاسبه

فرض کنید که آرایه داریم: [4، 2، 8، 3، 3، 1] دامنه ارزش ها از 1 تا 8 است. فرآیند شمارش منجر به یک آرایه شمارش می شود:

[0, 1, 2, 1, 1, 0, 0, 1]

این نشان دهنده فرکانس هر عدد است. الگوریتم سپس شمارش تجمعی را برای تعیین موقعیت محاسبه می کند:

[0, 1, 3, 5, 6, 6, 7]

استفاده از این، آرایه ی مرتب شده می شود: (۱۸، ۲، ۳، ۳، ۳، ۴، ۸)

سناریوهای کاربردی

شمارش مرتب برای سناریوهایی مناسب است که داده های ورودی شامل اعداد صحیح در محدوده ای شناخته شده و محدود است.این اغلب در موارد استفاده می شود:

  • مرتب کردن نمرات دانشجویی (به عنوان مثال، ۰-۱۰)
  • سازماندهی داده ها در تجزیه و تحلیل فرکانس
  • تنظیم اعداد کوچک در سیستم های جاسازی شده
  • اجرای رادون به عنوان یک تابع

بهره وری آن بستگی به اندازه دامنه نسبت به تعداد عناصر دارد.هنگامی که دامنه کوچک است، دسته بندی شمارش می تواند الگوریتم های مقایسه ای مانند Quicksort یا ادغام را به صورت پیش فرض کند.