الگوریتم مرتب سازی شمارشی یا Counting-sort

اول از همه عید تون شاد باد! این پست هم به مناسبت عید ایجاد کردم تا شب عید بدون پست نباشیم. در این پست یکی دیگه از روش های مرتب سازی بررسی می کنیم که با روش های قبلی فرق دارد. روش های قبلی بر اساس مقایسه بود و عناصر آرایه توسط تابع مرتب سازی با هم مقایسه می شدند و  بعد از مقایسه عنصر ها جایشان عوض می شد . در الگوریتم  های مرتب  سازی بر اساس مقایسه هزینه الگوریتم بین n^2 , n Lg n بود ولی الگوریتم مرتب سازی شمارشی (Counting Sort) از درجه n است و به آن مرتب سازی خطی (Linear Sort) می گویند چون براساس مقایسه نیست! البته با اینکه سرعت خوبی داره ولی حافظه زیادی می گیرد.

قبل از شرح الگوریتم مروری کنیم بر مباحثی که بررسی کردیم و می خواهیم بررسی کنیم :

مرتب سازی شمارشی

فرض کنید آرایه پنج عضوی  A را به صورت زیر داریم

و می خواهیم  آن را با مرتب سازی شمارشی مرتب کنیم ، ابتدا در آرایه  جست و جو می کنیم و بزرگ ترین عضو آرایه را پیدا می کنیم و یک آرایه با طول بزرگترین عضو آرایه به علاوه یک می سازیم.اگر بزرگ ترین عضو A را در متغییر Max برزیم ما آرایه ای به طول Max+1  می سازیم و اسم آن را B می گذاریم و همه ی خانه های آن را صفر می کنیم.

آرایه B به طول پنج:

مرحله  بعد  مرحله شمارش یا همون counting است که از اول آرایه A شروع به حرکت می کنیم  .اولین خانه آرایه  A  مقدار چهار است بعد از خواندن ۴ از آرایه A

به خانه ی چهارم به علاوه یک آرایه  B  می رویم و مقدار آن را یکی افزایش می دهیم
آرایه جدید B :

بعد به خانه ی بعدی در آرایه A می رویم که مقدار آن یک است و ما بعد از خواندن یک به خانه ی اول  به علاوه یک آرایه B  می رویم و مقدار آن را به علاوه ی یک می کنیم:

آرایه B :

و همین طوری در آرایه A پیش می رویم و تعداد هر کدام از عناصر را می شماریم و در آرایه B می ریزیم.

آرایه B بعد از شمارش همه ی اعضای درون A:

بعد از پر کردن آرایه B و پر کردن آن با تعداد اعضای A ، فراوانی اعضای A را در B بدست می آوریم  برای این کار اعضای آرایه B را با عضو های قبلی جمع می کنیم
آرایه  B بعد از جمع عضوهایش:

در مرحله ی بعد که مرحله آخر است یک آرایه دیگر هم اندازه A به اسم C می سازیم و از آخرین خونه A شروع می کنیم و به اول آرایه می آییم .خانه ی آخر آرایه A عدد ۳ است و به خانه ی سه به علاوه  یک درون آرایه B می رویم که  مقدار سه درون آن است یکی از آن کم می کنیم و بعد به خانه سه منهای یک درون آرایه C می رویم و مقدار ۳ را درون آن می گذاریم:

آرایه C:

و این  کار را ادامه می دهیم.

آرایه نهایی C :

این هم کد برنامه مرتب سازی شمارشی – counting sort

 

۹ نظر

  • معرکه!

  • بسیاااااااااااار عالی بود
    خیلی خیلی ممنونم واقعا کمکم کرد

  • نازنین

    ممنوووون …واقعاعالی توضیح داده بووودین…مررسی

  • سلام آقا فرهاد
    این الگوریتم چه کاربردی داره؟ مرتبه زمانیش چنده؟

    • فرهاد دلیرانی

      این الگوریتم یکی از روش های سورت کردن است که هزینش o(n) است و سرعت خوبی داره ولی تنها مشکلی که داره باید داده ها با شکل خاصی ذخیره شده باشند ، اگه از اول داده ها رو به فرمی درست ذخیره کنیم الگوریتم خوبی ، این الگوریتم در الگوریتم مرتب سازی radix sort هم استفاده می شود.
      مرتب سازی شمارشی بیشتر برای اعداد صحیح به کار می رود

    • سلام اقا فرهاد میشه مرتب سازیc# هم بنویسی ممنون میشم

      • اگر منظور شما پیاده سازی الگوریتم های مرتب سازی به زبان #C هست، به زودی اضافه میشوند.
        ممنون

  • آقا تشکر از زحماتتون، فقط اگه می شه وقفه های بین پست هاتون رو کم کنید.

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *