کد محصول: 1266
تعداد صفحه: 1 صفحه
نوع فایل: ZIP
قیمت: 31000 تومان
مرتبسازی پایهای یا مرتبسازی مبنایی (Radix sort)
مرتبسازی پایهای یا مرتبسازی مبنایی (به انگلیسی: Radix sort) الگوریتمی است که لیستی با اندازهٔ ثابت و اعضایی با طول k را در زمان (O(kn اتجام میدهد. ورودیها را به بخشهای کوچکی تقسیم میکنیم (اگر یک کلمه است آن را به حرفهایش میشکنیم و اگر عدد است آن را به ارقامش) سپس ابتدا لیست را بر اساس کم ارزش ترین بیت (حرف یا رقم) مرتب میکنیم، سپس بر اساس دومین بیت، تا در نهایت بر اساس پرارزش ترین بیت. به این ترتیب پس از k مرحله لیست مرتب میشود. این روش مرتبسازی پایدار است و در تهیهٔ واژه نامهها و مرتبسازی اعداد استفاده میشود. این مرتبسازی به کار هرمان هولریث در سال ۱۸۸۷ روی ماشینهای جدول بندی بر میگردد.
بیشتر کامپیوترهای دیجیتال در داخل، اطلاعاتشان را به صورت نمایش الکترونیکی از اعداد دودویی نشان میدهند، پس پردازش ارقام اعداد صحیح با نمایش دودویی خیلی راحت تر است. دو دسته از مرتبسازیهای مبنایی عبارت است از: مرتبسازی مبنایی کم ارزشترین رقم و مرتبسازی مبنایی پر ارزشترین رقم. مرتبسازیهای مبنایی کم ارزشترین رقم کم ارزش شروع میکنند و به طرف رقم پرارزش میروند، و مرتبسازیهای مبنایی پرارزشترین رقم برعکس عمل میکنند.
معمولاً اعداد صحیحی که با الگوریتمهای مرتبسازی پردازش میشوند را «کلیدها» میگویند، که میتوانند به تنهایی موجود باشند یا همراه دادههای دیگر. مرتبسازیهای مبنایی کم ارزشترین رقم معمولاً اینگونه مرتب میکنند: کلیدهای کوتاه قبل از کلیدهای بلندتر میآید و کلیدهای هم طول هم به صورت لغت نامهای مرتب میشوند. این با ترتیب معمولی اعداد صحیح منطبق است. مثل ترتیب: ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰. مرتبسازیهای مبنایی پرارزشترین رقم ترتیب لغت نامهای دارند که برای مرتب کردن رشتهها مناسب است. مثل کلمات یا اعداد صحیح با طول ثابت. یک ترتیب مثل»b،c،d،e،f،g،h،i،j،ba «وقتی لغت نامهای مرتب شود به صورت»b،ba،c،d،e،f،g،h،i،j «در میآید. اگر ترتیب لغت نامهای برای اعداد صحیح با طول متغیر اعمال شود، آنگاه نمایش اعداد ۱ تا ۱۰ خروجی»۱، ۱۰، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹” را پیدا میکند؛ بنابراین در این حالت برای درست مرتب شدن اعداد باید با گذاشتن فاصله از سمت چپ، اعداد کوتاه تر را با اعداد بلندتر هم طول کرد. (منبع: ویکی پدیا)
توجه: این پروژه حاوی فایل سورس برنامه مرتب سازی می باشد.