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

سئوال در زمینه مرتب سازی مبنا 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 نوشته شده توسط:  فرض کنید ورودی من اعداد زیر باش:
۲۸ و ۲۴ و ۲۶ و ۲۱ باشد
حالا اگر میتویند بدون الگوریتم مرتب سازی پایدار اون رو مرتب کنید (برای دهگان) و الگوریتم درست هم عمل کند .
نتیجه:
عدم پایداری الگوریتم ارقام اعداد رو به هم نمیریزه و تغیر نمیده اما ممکنه نتیجه مرتب سازی درست نباشه .
بله درست میگید منم ارسالم رو درست میکنم . در واقع استدلال منم شبیه شما بود اما بد بیانش کردم و بد نتیجه گرفتم!
در مثال شما اول بر اساس یکان ۲۱ و ۲۴ و۲۶ و ۲۸ داریم
حالا بر اساس دهگان مرتب سازی میکنیم که در اون اگه الگوریتم ناپایدار باشه چون دهگان همه مثل همه ممکن اونا رو جابه جا کنه یعنی مثلا ۲ مربوط به ۲۱ بعد از ۲ مربوط به ۲۸ بیاره و در نتیجه ۲۱ بعد از ۲۸ نشون بده که غلطه( اینم که گفتم اعداد بهم میریزه برا همینه )اما اگه الگوریتم مرتب سازی پایدار باشه طبق مرتب سازی مرحله قبل( یکان )۲۱ قبل از ۲۸ هست و حالا که نوبت به دهگان میرسه چون الگوریتم پایداره و ۲=۲ پس ۲۸ و ۲۱ رو جاب جا نمیکنه( اما در مرتب سازی ناپایدار ممکمه حتی با شرط ۲=۲ اعداد رو جا به جا کنه )
و در اخر از شما ممنونم .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  زمینه تحقیقاتی برای سمینار و پایانامه ارشد iman ۲۹۰ ۱۱۷,۸۱۹ ۱۴ شهریور ۱۳۹۹ ۰۶:۳۰ ب.ظ
آخرین ارسال: p.gh
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۱,۳۹۵ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  ایجاد شغل در زمینه خدمات hiradupvc ۱ ۸۹۲ ۲۱ دى ۱۳۹۸ ۰۵:۱۴ ب.ظ
آخرین ارسال: parisa1140
  سئو چیست؟ - سئو - بهینه سازی سایت msnmsn ۲ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۳ ب.ظ
آخرین ارسال: xiaomi
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۵۶۸ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work
  برگ برگ سازی Sanazzz ۱ ۵۵۴ ۱۳ فروردین ۱۳۹۸ ۰۸:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  راهنمایی برای انتخاب موضوع قابل پیاده سازی در زمینه بیگ دیتا برای پایان نامه one hacker alone ۱ ۱,۴۵۹ ۱۸ بهمن ۱۳۹۷ ۰۶:۳۶ ب.ظ
آخرین ارسال: Happiness.72
  زمینه مشکی برای صفحات chrome moslem73421 ۴ ۷۷۶ ۱۷ دى ۱۳۹۷ ۱۱:۲۷ ب.ظ
آخرین ارسال: ph0en1x
  انتخاب موضوع پایان نامه ارشد در زمینه پردازش تصویر Rezvan0411 ۱ ۱,۳۲۷ ۰۷ آذر ۱۳۹۷ ۰۸:۵۱ ب.ظ
آخرین ارسال: Baran15
  ابزار شبیه سازی پروتکل های امنیت شبکه - ابزار اسکایتر mavin1200 ۰ ۶۹۳ ۰۱ آذر ۱۳۹۷ ۰۱:۵۰ ق.ظ
آخرین ارسال: mavin1200

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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