زمان کنونی: ۲۴ آذر ۱۳۹۷, ۰۵:۳۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سئوال در زمینه مرتب سازی مبنا Radix Sort

ارسال:
  

hadi_m پرسیده:

سئوال در زمینه مرتب سازی مبنا Radix Sort

من دلیل اینکه چرا در مرتب سازی مبنا برای مرتب کردن ارقام حتما باید از یکی الگرویتم مرتب سازی پایدار یا stable استفاده کنیم رو متوجه نمیشم !!!!
ممنون میشم اگر کسی در این رابطه توضیح بده .

[tex]Radix Sort(A,d)[/tex]
For i to d
Do Use a Stable Sort to sort array A on digit i

۰
ارسال:
  

mfXpert پاسخ داده:

سئوال در زمینه مرتب سازی مبنا Radix Sort

تو این الگوریتم دو تا عدد رو در نظر بگیرید که قراره در گذر dام(یا همون رقم dام) مرتب بشن.اگر رقم dام هر دو عدد برابر باشن نباید جابجا بشن چون در حال حاضر در حالت مرتب خودشون قرار دارن و اگر الگوریتم stable نباشه ممکنه این دو عدد رو جابجا کنه و کار رو خراب کنه

۰
ارسال:
  

Msccom پاسخ داده:

سئوال در زمینه مرتب سازی مبنا Radix Sort

منم متوجه نمیشم که چرا تو این الگوریتم مدام مرتب میکنه و دوباره به هم میریزدش تا رقم مرحله بالاتر رو مرتب کنه!!!

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: سئوال در زمینه مرتب سازی مبنا Radix Sort

فرض کن داری اعداد ۱۲۵ و ۲۳۱ و ۴۲۰ رو مرتب میکنی در مرحله اول بر اساس یکان ‌، پس داریم:
۴۲۰ - ۲۳۱ - ۱۲۵ دقت کن رقم یکان ۱۲۵ از همه بزرگتره
حالا نوبت رقم دهگان میرسه‌، اینجا ۲ عدد ۱۲۵ و ۴۲۰ دارای رقم یکسان است‌، پس باید در مرتب سازی بر اساس رقم دهگان‌، مرتب سازی پایدار باشه تا یه وقت اشتباه نکنیم که اعداد رو جا به جا کنیم پس در این مرحله داریم‌: ۴۲۰ - ۱۲۵ - ۲۳۱ دقت کن دهگان ۲۳۱ از همه بزرگتره
در مرحله اخر هم داریم‌: ۱۲۵ - ۲۳۱ - ۴۲۰ یعنی مرتب سازی بر اساس رقم صدگان.
در ارسال های پایین مثال بهتری زده شده!

۰
ارسال:
  

hadi_m پاسخ داده:

سئوال در زمینه مرتب سازی مبنا Radix Sort

ممنونم از توضیحاتتون:
امااونچه که باعث میشه در صورت پایدار نبودن الگوریتم جواب اشتباه بشه به هم ریختن ارقام اعداد نیست و به نظرم این جالت پیش نمی‌اید چون ما وقتی داریم بر اساس مثلا دهگان مرتب میکنم فقط ارقام دهگان به تنهایی رو که جابه جا نمیکنیم و وسایر ارقام اعدد هم با هاش جابه جا میشه و در اینصورت امکان به هم ریختی اعداد نخواهیم شد اما مشکل دیگری برایش پیش می اید
و حتی اگر پایدار هم نباشه به نظرم در نهایت اشتباه نمیکنه .
طبق مثال شما ارایه ورودی هست (از راست به چپ):
۱۲۵ و ۲۳۱ و ۴۲۰
بعد از مرتب سازی بر اساس رقم یکان (راست به چپ):
۴۲۰ و ۲۳۱ و ۱۲۵
بعد از مرتب سازی رقم دهگان بدون پایداری الگوریتم:
۱۲۵ و ۴۲۰ و ۲۳۱ (۱۲۵ میبایست بعد از ۴۲۰ ظاهر میشد چون بعد از مرتب سازی بر اساس یکان بعد از ان ظاهر شده )
و مرتب سازی بر اساس رقم صدگان‌ Sadاز راست به چپ)
۱۲۵ و ۲۳۱ و ۴۲۰

در اینجا الگوریتم هیچوقت اشتباه نمیکند .اما یه حالت هست که الگوریتم دچار اشتباه میشود .
فرض کنید ورودی من اعداد زیر باش:
۲۸ و ۲۴ و ۲۶ و ۲۱ باشد
حالا اگر میتویند بدون الگوریتم مرتب سازی پایدار اون رو مرتب کنید (برای دهگان) و الگوریتم درست هم عمل کند .
نتیجه:
عدم پایداری الگوریتم ارقام اعداد رو به هم نمیریزه و تغیر نمیده اما ممکنه نتیجه مرتب سازی درست نباشه .
دیشب نتونستم دلیلش رو متوجه بشم اما امروز خوب که فکر کردم دیدم دلیلش اینه که وقتی با ارزش ترین ارقام برابر باشند در این حالت ترتیبی که ارقام کم ارزش قرار گرفته اند تاثیر جدی در نتیجه حاصله دارد وباید به ازای ارقام بارزش برابر این ترتیب حفظ شود تا در نهایت نتیجه درست حاص شود.

ارسال:
  

Masoud05 پاسخ داده:

RE: سئوال در زمینه مرتب سازی مبنا Radix Sort

(۱۱ دى ۱۳۹۰ ۰۲:۳۱ ب.ظ)hadi_m نوشته شده توسط:  فرض کنید ورودی من اعداد زیر باش:
۲۸ و ۲۴ و ۲۶ و ۲۱ باشد
حالا اگر میتویند بدون الگوریتم مرتب سازی پایدار اون رو مرتب کنید (برای دهگان) و الگوریتم درست هم عمل کند .
نتیجه:
عدم پایداری الگوریتم ارقام اعداد رو به هم نمیریزه و تغیر نمیده اما ممکنه نتیجه مرتب سازی درست نباشه .
بله درست میگید منم ارسالم رو درست میکنم . در واقع استدلال منم شبیه شما بود اما بد بیانش کردم و بد نتیجه گرفتم!
در مثال شما اول بر اساس یکان ۲۱ و ۲۴ و۲۶ و ۲۸ داریم
حالا بر اساس دهگان مرتب سازی میکنیم که در اون اگه الگوریتم ناپایدار باشه چون دهگان همه مثل همه ممکن اونا رو جابه جا کنه یعنی مثلا ۲ مربوط به ۲۱ بعد از ۲ مربوط به ۲۸ بیاره و در نتیجه ۲۱ بعد از ۲۸ نشون بده که غلطه( اینم که گفتم اعداد بهم میریزه برا همینه )اما اگه الگوریتم مرتب سازی پایدار باشه طبق مرتب سازی مرحله قبل( یکان )۲۱ قبل از ۲۸ هست و حالا که نوبت به دهگان میرسه چون الگوریتم پایداره و ۲=۲ پس ۲۸ و ۲۱ رو جاب جا نمیکنه( اما در مرتب سازی ناپایدار ممکمه حتی با شرط ۲=۲ اعداد رو جا به جا کنه )
و در اخر از شما ممنونم .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتب سازی درجی f_a ۲ ۱,۷۱۱ ۲۲ مهر ۱۳۹۱ ۱۰:۳۲ ب.ظ
آخرین ارسال: f_a
  نکات - مرتب سازی Masoud05 ۱ ۵,۶۱۱ ۲۰ فروردین ۱۳۹۱ ۰۸:۲۴ ب.ظ
آخرین ارسال: yaser_ilam_com
  Kتا عنصر اول یک آرایه - فصل مرتب سازی Mansoureh ۱۰ ۴,۱۴۲ ۰۱ بهمن ۱۳۹۰ ۱۲:۴۵ ق.ظ
آخرین ارسال: shervinrs
  مرتب سازی ادغامی livane_abi ۳ ۲,۷۹۳ ۱۳ آبان ۱۳۹۰ ۱۱:۲۶ ب.ظ
آخرین ارسال: mfXpert

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close