من دلیل اینکه چرا در مرتب سازی مبنا برای مرتب کردن ارقام حتما باید از یکی الگرویتم مرتب سازی پایدار یا stable استفاده کنیم رو متوجه نمیشم !!!!
ممنون میشم اگر کسی در این رابطه توضیح بده .
[tex]Radix Sort(A,d)[/tex]
For i to d
Do Use a Stable Sort to sort array A on digit i
For i to d
Do Use a Stable Sort to sort array A on digit i
تو این الگوریتم دو تا عدد رو در نظر بگیرید که قراره در گذر dام(یا همون رقم dام) مرتب بشن.اگر رقم dام هر دو عدد برابر باشن نباید جابجا بشن چون در حال حاضر در حالت مرتب خودشون قرار دارن و اگر الگوریتم stable نباشه ممکنه این دو عدد رو جابجا کنه و کار رو خراب کنه
منم متوجه نمیشم که چرا تو این الگوریتم مدام مرتب میکنه و دوباره به هم میریزدش تا رقم مرحله بالاتر رو مرتب کنه!!!
فرض کن داری اعداد ۱۲۵ و ۲۳۱ و ۴۲۰ رو مرتب میکنی در مرحله اول بر اساس یکان ، پس داریم:
۴۲۰ - ۲۳۱ - ۱۲۵ دقت کن رقم یکان ۱۲۵ از همه بزرگتره
حالا نوبت رقم دهگان میرسه، اینجا ۲ عدد ۱۲۵ و ۴۲۰ دارای رقم یکسان است، پس باید در مرتب سازی بر اساس رقم دهگان، مرتب سازی پایدار باشه تا یه وقت اشتباه نکنیم که اعداد رو جا به جا کنیم پس در این مرحله داریم: ۴۲۰ - ۱۲۵ - ۲۳۱ دقت کن دهگان ۲۳۱ از همه بزرگتره
در مرحله اخر هم داریم: ۱۲۵ - ۲۳۱ - ۴۲۰ یعنی مرتب سازی بر اساس رقم صدگان.
در ارسال های پایین مثال بهتری زده شده!
ممنونم از توضیحاتتون:
امااونچه که باعث میشه در صورت پایدار نبودن الگوریتم جواب اشتباه بشه به هم ریختن ارقام اعداد نیست و به نظرم این جالت پیش نمی‌اید چون ما وقتی داریم بر اساس مثلا دهگان مرتب میکنم فقط ارقام دهگان به تنهایی رو که جابه جا نمیکنیم و وسایر ارقام اعدد هم با هاش جابه جا میشه و در اینصورت امکان به هم ریختی اعداد نخواهیم شد اما مشکل دیگری برایش پیش می اید
و حتی اگر پایدار هم نباشه به نظرم در نهایت اشتباه نمیکنه .
طبق مثال شما ارایه ورودی هست (از راست به چپ):
۱۲۵ و ۲۳۱ و ۴۲۰
بعد از مرتب سازی بر اساس رقم یکان (راست به چپ):
۴۲۰ و ۲۳۱ و ۱۲۵
بعد از مرتب سازی رقم دهگان بدون پایداری الگوریتم:
۱۲۵ و ۴۲۰ و ۲۳۱ (۱۲۵ میبایست بعد از ۴۲۰ ظاهر میشد چون بعد از مرتب سازی بر اساس یکان بعد از ان ظاهر شده )
و مرتب سازی بر اساس رقم صدگان
از راست به چپ)۱۲۵ و ۲۳۱ و ۴۲۰
در اینجا الگوریتم هیچوقت اشتباه نمیکند .اما یه حالت هست که الگوریتم دچار اشتباه میشود .
فرض کنید ورودی من اعداد زیر باش:
۲۸ و ۲۴ و ۲۶ و ۲۱ باشد
حالا اگر میتویند بدون الگوریتم مرتب سازی پایدار اون رو مرتب کنید (برای دهگان) و الگوریتم درست هم عمل کند .
نتیجه:
عدم پایداری الگوریتم ارقام اعداد رو به هم نمیریزه و تغیر نمیده اما ممکنه نتیجه مرتب سازی درست نباشه .
دیشب نتونستم دلیلش رو متوجه بشم اما امروز خوب که فکر کردم دیدم دلیلش اینه که وقتی با ارزش ترین ارقام برابر باشند در این حالت ترتیبی که ارقام کم ارزش قرار گرفته اند تاثیر جدی در نتیجه حاصله دارد وباید به ازای ارقام بارزش برابر این ترتیب حفظ شود تا در نهایت نتیجه درست حاص شود.
(۱۱ دى ۱۳۹۰ ۰۲:۳۱ ب.ظ)hadi_m نوشته شده توسط: فرض کنید ورودی من اعداد زیر باش:بله درست میگید منم ارسالم رو درست میکنم . در واقع استدلال منم شبیه شما بود اما بد بیانش کردم و بد نتیجه گرفتم!
۲۸ و ۲۴ و ۲۶ و ۲۱ باشد
حالا اگر میتویند بدون الگوریتم مرتب سازی پایدار اون رو مرتب کنید (برای دهگان) و الگوریتم درست هم عمل کند .
نتیجه:
عدم پایداری الگوریتم ارقام اعداد رو به هم نمیریزه و تغیر نمیده اما ممکنه نتیجه مرتب سازی درست نباشه .
در مثال شما اول بر اساس یکان ۲۱ و ۲۴ و۲۶ و ۲۸ داریم
حالا بر اساس دهگان مرتب سازی میکنیم که در اون اگه الگوریتم ناپایدار باشه چون دهگان همه مثل همه ممکن اونا رو جابه جا کنه یعنی مثلا ۲ مربوط به ۲۱ بعد از ۲ مربوط به ۲۸ بیاره و در نتیجه ۲۱ بعد از ۲۸ نشون بده که غلطه( اینم که گفتم اعداد بهم میریزه برا همینه )اما اگه الگوریتم مرتب سازی پایدار باشه طبق مرتب سازی مرحله قبل( یکان )۲۱ قبل از ۲۸ هست و حالا که نوبت به دهگان میرسه چون الگوریتم پایداره و ۲=۲ پس ۲۸ و ۲۱ رو جاب جا نمیکنه( اما در مرتب سازی ناپایدار ممکمه حتی با شرط ۲=۲ اعداد رو جا به جا کنه )
و در اخر از شما ممنونم .