مرتب‌سازی پایه‌ای

مرتب‌سازی پایه‌ای

کلاس	الگوریتم مرتب‌سازی
داده ساختار	آرایه
بدترین زمان اجرا	$O(kN)$
بدترین پیچیدگی حافظه	$O(kN)$
بهینه	کاملا ٌصحیح

مرتب سازی پایه‌ای یا مرتب سازی مبنایی (به انگلیسی: 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«در می‌آید. اگر ترتیب لغت نامه‌ای برای اعداد صحیح با طول متغیر اعمال شود، آنگاه نمایش اعداد ۱ تا ۱۰ خروجی»۱، ۱۰، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹" را پیدا می‌کند. بنابراین در این حالت برای درست مرتب شدن اعداد باید با گذاشتن فاصله از سمت چپ، اعداد کوتاه تر را با اعداد بلندتر هم طول کرد.

مرتب سازی‌های مبنایی کم ارزش‌ترین رقم

یک مرتب سازی مبنایی کم ارزش‌ترین رقم یک الگوریتم مرتب سازی پایدار سریع است که می‌تواند برای مرتب سازی کلیدها به ترتیب الفبایی استفاده شود. کلیدها ممکن است یک رشته از حروف یا ارقام داده شده در یک "مبناً باشند. پردازش از کم ارزش‌ترین رقم (یعنی رقم سمت راست) شروع می‌شود و به پرارزش‌ترین رقم (رقم سمت چپ) می‌رسد. ترتیبی که رقم‌ها مورد پردازش قرار می‌گیرند در مرتب سازی مبنایی کم ارزش‌ترین رقم برعکس این ترتیب در مرتب سازی مبنایی پرارزش‌ترین رقم است.

یک مرتب سازی مبنایی کم ارزش‌ترین رقم در (O (nk کار می‌کند که n تعداد کلیدها و k میانگین طول کلیدهاست. برای رسیدن به این کارایی در مرتب سازی کلیدها با طول متغیر شما باید همه کلیدها با طول یکسان را در یک گروه قرار دهید و جداگانه یک مرتب سازی مبنایی کم ارزش‌ترین رقم را روی هر گروه از کلیدهای هم طول، از کوتاه‌ترین تا بلندترین اجرا کنید. عموماٌ برای مرتب کردن کارت‌های پانچ در بسیاری از گذرگاه‌ها از الگوریتم مرتب سازی مبنایی استفاده می‌شد. یک الگوریتم کامپیوتری برای مرتب سازی مبنایی در سال ۱۹۴۵ در MIT بوسیله هارولد سوارد اختراع شد. در بسیاری از برنامه‌های بزرگی که نیاز به سرعت دارند، مرتب سازی مبنایی کامپیوتری در مقایسه با مرتب سازی‌های مقایسه‌ای (آرام تر) یک پیشرفت است.

زمان مرتب سازی مبنایی از زمان دیگر الگوریتم‌های مرتب سازی مقایسه‌ای (مانند مرتب سازی سریع یا مرتب سازی ادغامی) که (Ω(nlgn مقایسه لازم دارند، که n تعداد کلیدهایی است که باید مرتب شوند، بهتر است. مرتب سازی‌های مقایسه‌ای نمی‌توانند در زمان بهتر از (Ω(nlgn کار کنند. هر چند زمان اجرای این الگوریتم‌ها از زمان اجرای الگوریتم‌های مرتب سازی لغت نامه‌ای بهتر است ولی این مطلب در بسیاری از برنامه‌های عملی اهمّیتی ندارد.

در ابتدا هر کلید به صورت مجازی به سطحی از پیمانه‌ها می‌رود که متناظر مقدار کم ارزش‌ترین رقمش است. هر پیمانه ترتیب واقعی کلیدهایی که داخلش هستند را حفظ می‌کند. یک تناظر یک به یک بین تعداد پیمانه‌ها و مقادیری که ارقام می‌توانند بگیرند برقرار است. سپس همین عملیات روی رقم کم ارزش بعدی انجام می‌شود و این کار ادامه پیدا می‌کند تا رقم دیگری باقی نماند. به عبارت دیگر:

۱. کم ارزش‌ترین رقم کلیدها را برمی داریم.

۲. کلیدها را براساس آن رقم گروه بندی می‌کنیم، ولی از طرف دیگر ترتیب اصلی کلیدها را حفظ می‌کنیم. (این باعث می‌شود مرتب سازی مبنایی کم ارزش‌ترین رقم، پایدار شود.)

۳. عملیات گروه بندی را با ارقام کم ارزش بعدی ادامه می‌دهیم.

در قدم ۲ مرتب سازی که استفاده می‌شود مرتب سازی پیمانه‌ای یا مرتب ساز شمارشی است که وقتی کارآمد هستند که تعداد کمی عدد داشته باشیم.

یک مثال

۱. لیست اصلی مرتب نشده: ۱۷۰، ۴۵، ۷۵، ۹۰، ۲، ۲۴، ۸۰۲، ۶۶

۲. مرتب سازی با کم ارزش‌ترین رقم (یکان) این لیست را ایجاد می‌کند:۱۷۰، ۹۰، ۲، ۸۰۲، ۲۴، ۴۵، ۷۵، ۶۶

توجه کنید ۲ قبل از ۸۰۲ آمده چون در لیست اصلی هم ۲ قبل از ۸۰۲ بود و همینطور برای ۱۷۰ و ۹۰، و ۴۵ و ۷۵.

۳. مرتب سازی با ارقام بعدی (دهگان) این لیست را ایجاد می‌کند: ۲، ۸۰۲، ۲۴، ۴۵، ۶۶، ۱۷۰، ۷۵، ۹۰

۴. مرتب سازی با پر ارزش‌ترین رقم (صدگان) این لیست را ایجاد می‌کند: ۲، ۲۴، ۴۵، ۶۶، ۷۵، ۹۰، ۱۷۰، ۸۰۲

مهم است که متوجه باشیم که در هرکدام از مراحل بالا فقط یک دور داده‌ها را مرور می‌کنیم و هر شئ بدون اینکه با دیگران مقایسه شود، در پیمانه درست قرار می‌گیرد.

بعضی پیاده سازی‌های مرتب سازی مبنایی کم ارزش‌ترین رقم با اولین شمارش تعداد کلیدهایی که به هر پیمانه متعلق هستند، قبل از انتقال کلیدها به آن پیمانه‌ها، برای پیمانه‌ها فضا می‌گیرند. تعداد دفعاتی که هر رقم اتفاق می‌افتد، در یک آرایه ذخیره می‌شود. لیست قبلی را که به یک صورت متفاوت آمده در نظر بگیرید:

۱۷۰، ۰۴۵، ۰۷۵، ۰۹۰، ۰۰۲، ۰۲۴، ۸۰۲، ۰۶۶

اولین گذر شمارشی روی کم ارزش‌ترین رقم هر کلید شروع می‌شود که یک آرایه برای اندازه پیمانه‌ها تولید می‌کند:

۲(اندازه پیمانه برای رقم‌های ۰: ۰۹۰، ۱۷۰.)

۲(اندازه پیمانه برای رقم‌های ۲: ۸۰۲، ۰۰۲.)

۱(اندازه پیمانه برای رقم‌های ۴: ۰۲۴.)

۲(اندازه پیمانه برای رقم‌های ۵: ۰۷۵، ۰۴۵.)

۱(اندازه پیمانه برای رقم‌های ۶: ۰۶۶.)

دومین گذر شمارشی روی دومین رقم کم ارزش هر کلید اتفاق می‌افتد که باز هم یک آرایه برای اندازه پیمانه‌ها تولید می‌کند:

۲(اندازه پیمانه برای رقم‌های ۰: ۰۰۲، ۸۰۲.)

۱(اندازه پیمانه برای رقم‌های ۲: ۰۲۴.)

۱(اندازه پیمانه برای رقم‌های ۴: ۰۴۵.)

۱(اندازه پیمانه برای رقم‌های ۶: ۰۶۶.)

۲(اندازه پیمانه برای رقم‌های ۷: ۱۷۰، ۰۷۵.)

۱(اندازه پیمانه برای رقم‌های ۹: ۰۹۰.)

سومین و آخرین گذر شمارشی روی پرارزش‌ترین رقم هر کلید اتفاق می‌افتد که باز هم یک آرایه برای اندازه پیمانه‌ها تولید می‌کند:

۶(اندازه پیمانه برای رقم‌های ۰: ۰۹۰، ۰۷۵، ۰۶۶، ۰۴۵، ۰۲۴، ۰۰۲.)

۱(اندازه پیمانه برای رقم‌های ۱: ۱۷۰.)

۱(اندازه پیمانه برای رقم‌های ۲: ۲۰۸.)

پس یک پیاده سازی مرتب سازی مبنایی کم ارزش‌ترین رقم تعداد دفعاتی که یک رقم در هر ستون اتفاق می‌افتد را برای همه ستون‌ها در یک گذر شمارشی می‌شمارد. دیگر پیاده سازی‌های مرتب سازی مبنایی کم ارزش‌ترین رقم فضا را برای پیمانه‌ها، به صورت پویا در زمانی که فضا لازم است، می‌گیرد.

مدل تکراری با استفاده از صف‌ها

یک مدل ساده یک مرتب سازی مبنایی کم ارزش‌ترین رقم، استفاده از صف‌ها به عنوان پیمانه هاست. پردازش زیر به تعداد برابر با تعداد ارقام بلندترین کلید تکرار می‌شود:

۱. اعداد صحیح بر اساس ارقامشان از راست به چپ وارد یک صف ده تایی می‌شوند. کامپیوترها اغلب در داخلشان اعداد را به صورت دودویی با طول ثابت نشان می‌دهند. در اینجا، ما یک کار آنالوگ با ارقام با طول ثابت دهدهی می‌کنیم. پس با استفاده از اعداد مثال قبل، صف برای اولین مرحله به این شکل خواهد بود:

۰: ۰۹۰، ۱۷۰

۱: -

۲: ۸۰۲، ۰۰۲

۳: -

۴: ۰۲۴

۵: ۰۷۵، ۰۴۵

۶: ۰۶۶

۹-۷: -

۲. صف‌ها صف گشایی می‌شوند به یک آرایه از اعداد صحیح به صورت نزولی. با این اعداد، آرایه بعد از اولین مرحله به این شکل خواهد بود:

۱۷۰، ۰۹۰، ۰۰۲، ۸۰۲، ۰۲۴، ۰۴۵، ۰۷۵، ۰۶۶

۳. در دومین گذر، صف‌ها به این شکل خواهد بود:

۰: ۰۰۲، ۸۰۲

۱: -

۲: ۰۲۴

۳: -

۴: ۰۴۵

۵: -

۶: ۰۶۶

۷: ۱۷۰، ۰۷۵

۸: -

۹: ۰۹۰

و آرایه:

۰۰۲، ۸۰۲، ۰۲۴، ۰۴۵، ۰۶۶، ۱۷۰، ۰۷۵، ۰۹۰

۴. و در سومین گذر داریم، صف‌ها:

۰: ۰۹۰، ۰۷۵، ۰۶۶، ۰۴۵، ۰۲۴، ۰۰۲

۱: ۱۷۰

۷-۲: -

۸: ۸۰۲

۹: -

و آرایه:

۰۰۲، ۰۲۴، ۰۴۵، ۰۶۶، ۰۷۵، ۰۹۰، ۱۷۰، ۸۰۲(مرتب شده) هر چند شاید این کارآمدترین الگوریتم مرتب سازی مبنایی نباشد، این نسبتاً ساده‌است و در عین حال بسیار کارآمد.

مرتب سازی مبنایی پرارزش‌ترین رقم

یک مرتب سازی مبنایی پرارزش‌ترین رقم می‌تواند برای مرتب سازی کلیدها در یک ترتیب لغت نامه‌ای استفاده شود. برخلاف مرتب سازی مبنایی کم ارزش‌ترین رقم، این مرتب سازی لزوماً ترتیب واقعی کلیدهایی که دو بار آمده را حفظ نمی‌کند. یک مرتب سازی مبنایی پرارزش‌ترین رقم پردازش را از پرارزش‌ترین رقم یعنی رقم سمت چپ شروع می‌کند و به سوی کم ارزش‌ترین یعنی رقم سمت راست می‌رود، برعکس مرتب سازی مبنایی کم ارزش‌ترین رقم. بعضی از مرتب سازی‌های مبنایی پرارزش‌ترین رقم یک دسته پیمانه برای گروه بندی کلیدها استفاده می‌کند. بقیه مرتب سازی‌های مبنایی پرارزش‌ترین رقم چندین دسته از پیمانه‌ها را استفاده می‌کنند. یک مرتب سازی پستی یک نوع مرتب سازی مبنایی پرارزش‌ترین رقم است.

بازگشت

یک الگوریتم مرتب سازی مبنایی پرارزش‌ترین رقم بازگشتی جزء به جزء به صورت زیر کار می‌کنند:

۱. پرارزش‌ترین رقم هر کلید را برمی دارد.

۲. لیست المان‌ها را برحسب این رقمشان، با گروه گروه کردن المان‌ها در پیمانه‌های متناظر با این رقم‌ها، مرتب می‌کند.

۳. به صورت بازگشتی پیمانه را با شروع از زقم بعدی (سمت راستی) مرتب می‌کند.

۴. پیمانه‌ها را به ترتیب به هم الحاق می‌کند.

پیاده سازی گذری

یک تابع دو گذری را می‌توان برای فهمیدن اینکه هر پیمانه چقدر باید باشد و گذاشتن هر کلید در پیمانه مناسب استفاده کرد. یک سیستم یک گذری هم می‌تواند استفاده شود که هر پیمانه به صورت پویا تخصیص داده شود و هر وقت لازم بود بزرگ شود، اما این باعث خطر قطعه قطعه شدن حافظه و گرفتن حافظه مضر شود که این کارایی را کم می‌کند. از این قطعه قطعه شدن حافظه می‌توان با یک اختصاص حافظه ثابت برای پیمانه‌هایی برای همه مقدارهای ممکن برای ارقام، جلوگیری کرد. اما برای یک رقم ۸ بیتی نیاز به ۲۵۶ پیمانه داریم، حتی اگرهمه پیمانه‌ها استفاده نشوند. پس این روش ممکن است همه حافظه در دسترس را سریعاً استفاده کند و به فضاهای دیگر که داده ذخیره می‌شود روی هارد یا یک حافظه ثانویه به جای حافظه اصلی برود، که این کار کارایی را اساساً کاهش می‌دهد. یک اختصاص حافظه ثابت برای وقتی مناسب است که ارقام کوچک باشند مثل یک بیت.

یک مثال از مرتب سازی مبنایی بازگشتی

این لیست را مرتب کنید:

۱۷۰، ۰۴۵، ۰۷۵، ۰۹۰، ۰۰۲، ۰۲۴، ۸۰۲، ۰۶۶

۱. با پردازش رقم صدگان مرتب می‌کنیم:

پیمانه‌ها با صدگان ۰: ۰۶۶، ۰۲۴، ۰۰۲، ۰۹۰، ۰۷۵، ۰۴۵

پیمانه یکصدها: ۱۷۰

پیمانه هشتصدها: ۸۰۲

۲. مرتب کردن با رقم بعدی (دهگان): (این قسمت فقط برای اعداد با صدگان ۰ لازم است چون دیگر پیمانه‌ها بیش از یک عضو ندارند) پیمانه‌ها با دهگان ۰: ۰۰۲

پیمانه بیست‌ها: ۰۲۴

پیمانه چهل‌ها: ۰۴۵

پیمانه شصت‌ها: ۰۶۶

پیمانه هفتادها: ۰۷۵

پیمانه نودها: ۰۹۰

۳. مرتب کردن با یکان یعنی کم ارزش‌ترین رقم لازم نیست زیرا هیچ کدام از پیمانه‌های دهگان بیش از یک عضو ندارند. پس حالا باید اعداد با صدگان صفر را به هم الحاق کنید و سپس بقیه را به آنها الحاق کنیم:

۰۰۲، ۰۲۴، ۰۴۵، ۰۶۶، ۰۷۵، ۰۹۰، ۱۷۰، ۸۰۲

این مثال اعداد مبنای ۱۰ را برای خوانایی استفاده کرد، اما البته ارقام دودویی برای پردازش در کامپیوترها بهتر هستند.

کارایی

مرتب سازی مبنایی بهینه‌است. فرض کنید که هر مرتب سازی باید همه کلیدها را نگاه کند تا آنها را مرتب کند. پس بهینه بودن در این زمینه به زمان لازم برای مرتب کردن کلیدها به نسبت تعداد کلیدها بستگی دارد. به علاوه فرض کنید حافظه‌ای که برای مرتب کردن کلیدها لازم است نباید با افزایش تعداد کلیدها خیلی زیاد شود. مرتب سازی مبنایی هر دو این عوامل را دارد. این مرتب سازی یک تابع رشد خطی مربوط به حافظه و مقدار زمان لازم برای مرتب کردن کلیدها دارد. در الگوریتم‌های مرتب سازی زمان بهتر از رشد خطی هم نداریم.

منابع

• ویکی‌پدیا انگلیسی
• مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش