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

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

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۸ دیدگاه

پاسخ دهید

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