تبلیغات


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

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

sort-counting

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

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

– مفهوم مرتب سازی

bubble sort

-insertion sort

-merge sort

quick sort

-Distribution sorts

– Concurrent sorts

– Heap sort

-Radix sort

– Counting 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 هست، به زودی اضافه میشوند.
        ممنون

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

نظر خود را بنویسید.

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