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

مرتب‌سازی پایه‌ای یا مرتب‌سازی مبنایی (به انگلیسی: Radix sort) الگوریتمی است که لیستی با اندازهٔ ثابت و اعضایی با طول k را در زمان (O(kn انجام می‌دهد. ورودی‌ها را به بخش‌های کوچکی تقسیم می‌کنیم (اگر یک کلمه است آن را به حرف‌هایش می‌شکنیم و اگر عدد است آن را به ارقامش) سپس ابتدا لیست را بر اساس کم ارزش‌ترین بیت (حرف یا رقم) مرتب می‌کنیم، سپس بر اساس دومین بیت، تا در نهایت بر اساس پرارزش‌ترین بیت. به این ترتیب پس از k مرحله لیست مرتب می‌شود. این روش مرتب‌سازی پایدار است و در تهیهٔ واژه نامه‌ها و مرتب‌سازی اعداد استفاده می‌شود. این مرتب‌سازی به کار هرمان هولریث در سال ۱۸۸۷ روی ماشین‌های جدول بندی بر می‌گردد.

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

رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	$O(kN)$
پیچیدگی فضایی	$O(k+N)$

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

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

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

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

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

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

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

یک مثال

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

۰: ۰۹۰، ۱۷۰

۱: -

۲: ۸۰۲، ۰۰۲

۳: -

۴: ۰۲۴

۵: ۰۷۵، ۰۴۵

۶: ۰۶۶

۹-۷: -

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

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

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

۰: ۰۰۲، ۸۰۲

۱: -

۲: ۰۲۴

۳: -

۴: ۰۴۵

۵: -

۶: ۰۶۶

۷: ۱۷۰، ۰۷۵

۸: -

۹: ۰۹۰

و آرایه:

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

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

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

۱: ۱۷۰

۷-۲: -

۸: ۸۰۲

۹: -

و آرایه:

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

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

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

بازگشت

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

کارایی

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

منابع

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