مرتب بودن اما به چه قیمتی

​

اعمال مرتب سازی و جستجوی داده ها در دنیای کامپیوتر از اعمالی محسوب می شوند که بیشترین مورد استفاده را دارند. در بسیاری از برنامه‌ها به نحوی از الگوریتم‌های مرتب‌سازی و جستجو استفاده می‌شود. وقتی‌که فایل‌های یک پوشه بر اساس نام مرتب می‌شود؛ وقتی‌که در سرویس ایمیل خود به دنبال ایمیل خاصی می‌گردید و نتایج جستجو بر اساس زمان مرتب می‌شوند؛ یا هنگامیکه یک فایل فشرده Zip را باز می‌کنید و… . شاید به چشم نیاید ولی در همه این کارها به نحوی با مرتب‌سازی و جستجو سروکار دارید. از طرف دیگر، عملیات مرتب‌سازی (Sorting) رابطه بسیار نزدیکی با عملیات جستجو (Searching) دارد.

از همان ابتدای شکل‌گیری کامپیوتر مباحث مربوط به مرتب‌سازی و جستجوی داده‌ها وجود داشته و تا به امروز هم ادامه دارد که باعث به‌وجود آمدن شاخه‌ای با نام الگوریتم‌های جستجو و مرتب‌سازی (Sorting & Searching Algorithm) شده است. ما در این نوشتار قصد داریم فقط نیم نگاهی به موضوع مرتب‌سازی (Sorting) بیاندازیم و مبحث جستجو را به زمانی دیگر موکول می‌کنیم. جالب است بدانید که اولین الگوریتم مرتب‌سازی، مرتب‌سازی حبابی نام داشت و در سال 1956 به‌وجود آمد. اما از آن سال تا به امروز انواع دیگری از الگوریتم‌های مرتب‌سازی شکل گرفتند. حتی در سال 2006 الگوریتم جدیدی با نام مرتب‌سازی کتابخانه‌ای، مطرح شد. سوالی که هم‌اکنون ذهن بسیاری از خوانندگان را درگیر خود کرده‌ این است که وقتی که در سال 1956 راه‌حلی برای مرتب‌سازی پیدا شد، چه نیازی به طراحی کردن راه‌حل و الگوریتم‌های جدید است؟ پاسخ سوال شما فقط یک کلمه است: کارایی.
کارایی هر الگوریتم در شرایط مختلف، متفاوت است. تصور کنید که قرار است 100 کارت که روی آنها از عدد 1 تا 100 نوشته شده و نامرتب هستند، مرتب شود. وقتی وظیفه مرتب‌سازی این کارت‌ها به افراد مختلف داده شود، خواهید دید که هر شخص روش متفاوتی را برای مرتب‌ کردن استفاده می‌کنند. برای نمونه شخص اول در کل کارت‌ها به دنبال کوچک‌ترین عدد (در اینجا عدد یک است) می‌گردد و پس از پیدا کردن، آن را در دست خود نگه می‌دارد. سپس در مابقی کارت‌ها به دنبال عدد بعدی می‌گردد. او به همین ترتیب ادامه می‌دهد تا کارت‌ها مرتب شوند. اما شخص دوم به این روش عمل می‌کند که دو کارت اول را بر می‌دارد و مقدارشان را با یکدیگر مقایسه می‌کند. کارت کوچک‌تر را در بالا و کارت بزرگ‌تر را در زیر قرار می‌دهد. سپس کارت بعدی را بر می‌دارد و با کارت‌هایی که در دست خود دارد مقایسه می‌کند و بسیاری راه‌حل دیگر که اگر خواهیم هر کدام را توضیح دهیم، چندین صفحه نیاز داریم. تمام روش‌هایی که اشخاص مختلف استفاده می‌کنند به نتیجه می‌رسد؛ ولی مباحث سرعت و زمان، میزان مصرف انرژی و منابع، پیچیدگی روش و… وجود دارد که کارایی آن روش و در واقع آن الگوریتم به آنها بستگی دارد. مثلا ممکن است یک الگوریتم با تعداد پایین داده بسیار سریع عمل کند ولی وقتی تعداد داده‌ها بالا می‌رود، مدت زمانیکه آن الگوریتم نیاز دارد تا آنها را مرتب کنند، به صورت تصاعدی بالا می‌رود و در نهایت به بدترین الگوریتم تبدیل شود.
به طور کلی الگوریتم‌های مرتب‌سازی بر اساس این معیارها مقایسه می‌شوند:
1- پیچیدگی: مباحث بهترین عملکرد، بدترین عملکرد و عملکرد میانگین با توجه به تعداد داده یا عناصر لیست شکل می‌گیرند. در بخش نماد O بزرگ بیشتر در این باره صحبت می‌کنیم.
2- حافظه (و سایر منابع کامپیوتر): بعضی از الگوریتم‌ها علاوه بر حافظه‌ای که خود داده‌ها آن را اشغال کرده‌اند، برای مرتب‌سازی به حافظه‌های جانبی و کمکی نیاز دارند. ولی برخی دیگر که به آنها الگوریتم‌های In Place گفته می‌شود، به جز مقداری حافظه کم برای جابه‌جایی داده‌ها به حافظه کمکی نیازی ندارند.
3- طبیعی بودن یا نبودن: فرض کنید ما از یک تعداد داده دو لیست در اختیار داریم:1- لیست مرتب 2- لیست نامرتب. اگر این دو لیست به یک الگوریتم داده شد و آن الگوریتم توانست در لیست مرتب شده کارایی بهتری از خود نشان دهد (سریع‌تر به نتیجه برسد)، آنگاه آن الگوریتم طبیعی محسوب می‌شود. این معیار از این جهت اهمیت دارد که ما نمی‌دانیم که لیست داده‌های ما تا چه اندازه نظم دارد و مرتب است. مثلا شاید در لیست ما فقط جای دو عنصر جابه‌جا باشد و در اینجا الگوریتم نسبت به حالات نامنظم‌تر باید سریع‌تر عملیات خود را انجام دهد و نتیجه را برگرداند.
4- پایداری: الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌هایی که کلیدهای برابر حفظ می‌کنند. یعنی اگر در لیست اولیه، دو عنصر A و B دارای مقدار یکسان هستند و عنصر B بعد از عنصر A آمده باشد، با الگوریتم مرتب‌سازی که پایدار باشد، همین ترتیب A و B در لیست مرتب شده نیز حفظ می‌شود.
5- تعویضی بودن یا نبودن: در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به‌وسیله یک عملگر مقایسه، مرتب می‌شوند.
6- روش مرتب‌سازی عمومی: تقریبا تمامی الگوریتم‌های مرتب‌سازی از یکی انواع روش‌های عمومی‌ مرتب‌سازی استفاده می‌کنند. درجی، جابه‌جایی، گزینشی، ترکیبی و… . برای نمونه الگوریتم مرتب‌سازی حبابی از روش عمومی تعویضی (Exchange) استفاده می‌کند.
نشانه O بزرگ
در نظریه پیچیدگی محاسبا‌تی، نماد O بزرگ (Big O notation) برای نشان دادن رابطه میان تعداد داده‌ها و منابع محاسباتی مورد نیاز برای حل یک مساله با استفاده از یک الگوریتم استفاده می‌شود. نشانه O بزرگ در علوم کامپیوتر، به زبانی ساده در واقع نمایش‌دهنده میزان کارایی یک الگوریتم در هنگام کار با مقدار داده‌های متعدد است.

​

مثلا وقتی تعداد داده ورودی فلان الگوریتم به اندازه‌ای مشخص رشد پیدا کرد، آن الگوریتم چه مقدار زمان نیاز دارد تا آن داده‌ها را حل کند؛ درواقع نرخ رشد آن الگوریتم چه مقدار است. این نشانه به طراحان الگوریتم و برنامه‌نویسان اجازه می‌دهد که رفتار کدهایشان را پیش‌بینی کنند و بر اساس داده‌هایی که قرار است برنامه به عنوان ورودی دریافت کند، الگوریتم‌های مناسب را انتخاب کرده و در کدهای خود استفاده کنند.
فرض کنید یک الگوریتم را آنالیز کرده‌اید و نتیجه آن معادله زیر است که n، تعداد داده ورودی و T(n)، مدت زمانی است که الگوریتم صرف می‌کند که آن تعداد داده را حل کند:
T(n) = 3n2 + 2n – 1
حالا وقتی تعداد داده ورودی خیلی زیاد شود (به‌طوریکه بتوانیم بگوییم به بی‌نهایت میل می‌کند) آنگاه 2n – 1 و ضریب n2 که عدد 3 است تاثیر زیادی در کل زمان ندارد و می‌توان از آنها صرف‌نظر کرد و مقدار n2 می‌ماند. پس معادله به صورت زیر در‌ می‌آید:
T(n) = n2
(T(n) = O(n2
بدین ترتیب در حالت کلی اگر تعداد داده دو برابر شود، تعداد مراحل انجام الگوریتم و مدت زمانیکه طول می‌کشد آن الگوریتم اجرا شود، 4 برابر می‌شود. اگر هزار داده ورودی باشد، زمان مورد نیاز یک میلیون است. حال اگر یک‌میلیون داده داشته باشیم، زمان آن به هزار و 12 می‌رسد!
بهترین حالتی که برای یک لیست وجود دارد این است که آن لیست مرتب شده باشد. اما بدترین حالت زمانی است که عناصر آن لیست برعکس مرتب شده باشند. همانطور که در بالاتر اشاره کردیم، یکی از معیارهای مقایسه بین الگوریتم‌های مرتب‌سازی، پیچیدگی آن الگوریتم است. در حالت کلی 3 فاکتور برای پیچیدگی الگوریتم‌ها بیان می‌شود: 1- بهترین حالت 2- بدترین حالت 3- حالت میانگین.
در مرتب‌سازی‌های معمولی عملکرد خوب(O(n log n و عملکرد بد (O(n2 است. بهترین عملکرد برای مرتب‌سازی (O(n محسوب می‌شود.
در جدول الف نام برخی از پرکاربردترین الگوریتم‌های مرتب‌سازی به همراه این اطلاعات آمده است.
نوع روش عمومی، پایدار بودن یا نبودن، بهترین حالت، حالت میانگین بدترین حالت و مقدار حافظه کمکی (بیانگر مقدار حافظه کمکی که علاوه بر حافظه اشغال‌شده توسط خود داده‌ها، مورد استفاده الگوریتم قرار می‌گیرد).

​

در این مقاله ما نام برخی از الگوریتم‌های مرتب‌سازی را نوشته‌ایم و تعداد الگوریتم‌ها بیشتر از این تعداد است. برخی از آنها برای اجرا نیاز به سخت‌افزار خاصی دارند(مانند Bead Sort) و برخی فقط برای مقاصد خاصی مورد استفاده می‌شوند (مانند Sorting Network) و… . در ادامه، طی این شماره و شماره هفته آینده شما با چند مورد از پرکاربردترین الگوریتم‌ها آشنا خواهید شد. فقط به این نکته اشاره کنم که به دلیل محدود بودن فضا، فقط توضیح مختصری در مورد آنها داده می‌شود. اگر مایل بودید می‌توانید با یک جستجوی ساده، الگوریتم پیاده‌سازی هر کدام از الگوریتم‌ها را در زبان‌های مختلف پیدا کنید.
مرتب‌سازی سریع

​

این الگوریتم به دلیل سرعت بالا و مصرف کم حافظه یکی از بهترین الگوریتم‌های مرتب‌سازی محسوب می‌شود. مهم‌ترین نکته مرتب با مرتب‌سازی سریع ساختار پیاده‌سازی آنکه به صورت بازگشتی (Recursive) صورت می‌گیرد، است. در این الگوریتم هر لیست بزرگ به دو زیر لیست کوچک‌تر تقسیم می‌شود و سپس به صورت بازگشتی، هر زیر لیست مرتب می‌شود.
به‌طور کلی مراحل این الگوریتم به این صورت است که ابتدا یکی از عناصر به عنوان عنصر محور (Pivot) انتخاب می‌شود. سپس تمامی عناصر به گونه‌ای جابه‌جا‌ می شوند که عناصر کوچک‌تر از عنصر محور قبل از آن و عناصر بزرگ بعد از آن قرار می‌گیرند . بدین ترتیب جای درست عنصر محور معین می‌شود. در ادامه به صورت بازگشتی، همین مراحل برای هر یک از زیر‌لیست‌ها انجام می‌شود. یعنی یک عنصر محور برای آنها انتخاب می‌شود و بقیه مراحل روی آنها انجام می‌پذیرد.
این الگوریتم برای لیست‌هایی با عناصر کم مناسب نیست و پیشنهاد می‌شود که برای چنین لیست‌هایی سراغ الگوریتم‌های دیگر بروید. همچنین چند نوع الگوریتم بهینه شده از مرتب‌سازی سریع وجود دارد که می‌توانید از آنها استفاده کنید؛ مانند: Balanced و External quicksort.
مرتب‌سازی ادغامی
این الگوریتم در ابتدا بررسی می‌کند که طول لیست صفر یا یک است یا خیر. اگر اینگونه بود، آن لیست را مرتب‌شده در نظر می‌گیرد. اما اگر طول آن بیش از یک بود بدین صورت عمل می‌کند: لیست را به دو قسمت تقریبا مساوی تقسیم می‌کند (دو زیرلیست پدید می‌آید) و دوباره هر زیرلیست را دوباره به دو زیرلیست دیگر تقسیم می‌کند. آنقدر این کار را ادامه می‌دهد تا به زیر لیست‌هایی با طول یک برسد. در آن موقع به صورت بازگشتی (Recursive) و از همان انتها هر دو زیر لیست را با یکدیگر مقایسه می‌کند و آن دو را به صورت مرتب ادغام می‌کند. سپس یک قدم به عقب بر‌می‌گردد. در این مرحله که زیر لیست‌هایی با طول دو وجود دارند و هر زیر لیست برای خود مرتب هستند را با یکدیگر به‌صورت مرتب‌شده ادغام می‌کند. این رویه را تا رسیدن به لیست اصلی ادامه می‌دهد. این الگوریتم بر اساس دو اصل شکل گرفته است:
1- مرتب‌سازی یک لیست کوچک‌تر بسیار سریع‌تر از یک لیست بزرگ انجام می‌گیرد.
2- ادغام دو لیست مرتب شده بسیار سریع‌تر از ادغام دو لیست نامرتب انجام می‌گیرد.
الگوریتم‌های بهینه‌شده‌ای از مرتب‌سازی ادغامی نیز وجود دارد؛ مانند tiled merge sort
با وجود اینکه Big O الگوریتم‌ مرتب‌سازی هرمی (Heapsort) شبیه این الگوریتم بوده و حتی با در نظر گرفتن اینکه مقدار حافظه مصرفی آن کمتر است و در نتیجه بهتر از الگوریتم ادغامی محسوب می‌شود؛ یا برای مثال مرتب‌سازی سریع از نظر بسیاری از افراد سریع‌ترین الگوریتم محسوب می‌شود، ولی در برخی موارد مرتب‌سازی ادغامی بهتر عمل می‌کند. مطمئنا می‌پرسید در کدام موارد؟ الگوریتم ادغامی در مرتب‌سازی لیست‌های پیوندی (Linked Lists) الگوریتم مناسبی محسوب می‌شود. حتی اگر این الگوریتم درست پیاده سازی شود، میزان حافظه آن (O(1 خواهد شد. از طرفی در لیست‌های پیوندی کارایی الگوریتم مرتب‌سازی سریع پایین می‌آید و حتی الگوریتم هرمی در لیست‌های پیوندی جواب نمی‌دهد.

​

مرتب‌سازی درجی

​

این الگوریتم جزو ساده‌ترین الگوریتم‌ها محسوب می‌شود و به هیچ وجه کارایی الگوریتم‌های سریع، هرمی و ادغامی را در لیست‌های بزرگ را ندارد. یعنی درواقع این الگوریتم برای لیست‌های نسبتا کوچک مورد استفاده قرار می‌گیرد و در این لیست‌های کوچک بهتر از الگوریتم‌های حبابی (Bubble) و انتخابی (Selection) عمل می‌کند. از طرفی پیاده‌سازی آن ساده، پایدار و مصرف حافظه آن (O(1 است.
این الگوریتم به این صورت عمل می‌کند که ابتدا یکی از عناصر را انتخاب کرده و در جایی قرار می‌دهد. سپس عنصر دوم را انتخاب شده و این دو عنصر را با یکدیگر مقایسه شده و به صورت مرتب شده در جای خود قرار می‌گیرند.
حالا عنصر سوم انتخاب می‌شود و با دو عنصر قبلی مقایسه می‌شود و در جای مناسب قرار می‌گیرد. همین روال تا مرتب شدن کامل لیست ادامه پیدا می‌کند. یک مثال ملموس از این الگوریتم:
پنج کارت که روی آنها اعداد یک تا پنج نوشته شده است، به پشت روی میز قرار دارند. هر کدام را که مایل هستید بر می‌دارید و در دست خود می‌گیرید. سپس به انتخاب خود یکی دیگر از کارت‌ها را بر می‌دارید؛ اگر عدد آن کوچک‌تر بود، در سمت چپ کارت قبل و اگر بزرگ‌تر بود در سمت راست قرار می‌دهید. حالا کارت سوم را بر‌می‌دارید و با دو کارت قبلی مقایسه می‌کنید و الی آخر.
بهترین حالت برای این الگوریتم این است که لیست مرتب باشد. در آن صورت Big O آن (O(n است. اما بدترین حالت این است که لیست معکوس مرتب باشد که در آن صورت (O(n2 می‌شود. برای این الگوریتم نیز نسخه‌های بهینه‌شده‌ای وجود دارد.
الگوریتم مرتب‌سازی شل (Shell) یک نسخه بهینه‌شده از الگوریتم درجی است که توسط D.L Shell و در سال 1959 معرفی شد.
مرتب‌سازی حبابی
به دلیل سادگی پیاده‌سازی Bubble Sort آن را در همه دانشگاه‌ها به عنوان یکی از اولین الگوریتم‌های مرتب‌سازی آموزش می‌دهند. این الگوریتم را با نام sinking نیز می‌شناسند به این نحو عمل می‌کند که ابتدا دو عنصر اول را انتخاب کرده و آنها را از نظر بزرگ‌تری و کوچک‌تری مقایسه می‌کند؛ این دو عنصر باید مرتب‌ شده باشند، اگر اینطور نبود با یک تعویض جای آنها را در لیست تعویض می‌شود.
حالا عنصر دوم با عنصر سوم مقایسه می‌شود. اگر این دو عنصر مرتب نبودند، جای آنها نیز عوض می‌شود. این رویه را ادامه می‌دهد تا به انتهای لیست برسد و بدین ترتیب به‌صورت خودکار بزرگ‌ترین عنصر به انتهای لیست منتقل می‌شود.
چون که جای عنصر بزرگ مشخص شده است، پس نیازی ندارد که در مرتب‌سازی‌های بقیه عناصر مورد بررسی قرار بگیرد. پس برای پیدا کردن دومین عنصر بزرگ، الگوریتم عملیات مرتب‌سازی حبابی را تا یکی مانده به آخرین عنصر انجام می‌دهد.
این روش تا مرتب شدن کل لیست ادامه پیدا می‌کند. کارایی این الگورتیم حتی از مرتب‌سازی درجی هم پایین‌تر است؛ به همین دلیل پیشنهاد می‌شود که این الگوریتم را به‌طور کل آموزش ندهند یا نهایتا برای آشنایی بیشتر، فقط کد آن در محیط‌های آموزشی مروری شود.
اما متاسفانه همچنان این الگوریتم در محیط‌های آموزشی‌ ایران به عنوان یک الگوریتم مهم آموزش داده می‌شود. برای مثال من با الگوریتم حبابی در دانشــگاه آشنا شدم و همیشه فکر می‌کردم که به‌طور کل 4 یا 5 الگوریتم مرتب‌سازی داریم و حبابی یکی از الگوریتم‌های خوب محسوب می‌شود.
ولی بعد از اینکه درباره الگوریتم‌های مرتب‌سازی تحقیق کردم، متوجه شدم نه‌ تنها تعداد زیادی الگوریتم برای این فرآیند وجود دارد، بلکه حبابی یکی از بدترین‌‌ها محسوب می‌شود!
مرتب‌سازی رقابتی
این الگوریتم یک نسخه بهبود یافته از روش انتخابی (Selection) محسوب می‌شود.
به این دلیل که همان الگوریتم انتخابی را با استفاده از صف‌های اولویت‌دار (Priority Queue) پیاده‌سازی می‌کند.
روش کار بدین صورت است که از فایل، مقداری داده‌ها خوانده می‌شود و در یک صف اولویت‌دار قرار می‌گیرد تا آن صف پر شود. حالا کوچک‌ترین عنصری که در صف است پیدا شده و از آن خارج (Pull) می‌شود و به عنوان اولین اجرا (First Run)، نوشته می‌شود.
در ادامه دوباره یک داده از فایل خوانده می‌شود که در صف قرار گیرد. ترفند این الگوریتم در این قسمت به کار گرفته می شود: اگر مقدار داده خوانده شده از فایل، از مقدار آخرین عنصر خارج شده از صف، کمتر باشد، اولویت این داده یک واحد افزایش پیدا می‌کند و در صف با اولویت بالاتر قرار می‌گیرد.
در نتیجه به عنوان بخشی از اجرای بعدی (Next Run) خواهد شد.
مرتب‌سازی هرمی
در این الگوریتم ابتدا یک هرم از عناصر‌ها ساخته‌ می‌شود که در آن بزرگ‌ترین عدد در بالا قرار می‌گیرد. عدد بزرگ از بالای هرم حذف شده و به انتهای یک لیست فرستاده می‌شود. در مرحله بعد دوباره از عناصر مانده یک هرم ساخته می‌شود تا دومین عنصر بزرگ پیدا شود. این عنصر دوباره از بالای هرم حذف می‌شود و قبل از عنصر بزرگ قبلی قرار می‌گیرد. این رویه تا جایی ادامه پیدا می‌کند که هیچ عنصری در هرم باقی نماند و تمامی عناصر به صورت مرتب‌شده در آن لیست جدید قرار بگیرند، ادامه پیدا می‌کند. این روال برای ساخت لیست مرتــب شــده صـعــودی بــود و بــه آن Max-Heapsort گفته می‌شود. اما اگر خواستید لیست نزولی بسازید، باید هرم‌هایی بسازید که عنصر کوچک‌تر بالاتر از بقیه قرار بگیرد. در آن صورت به آن Min-Heapsort می‌گویند. این الگوریتم جزو سریع‌ترین الگوریتم‌ها محسوب می‌شود، ولی متاسفانه پایدار نیست؛ یعنی اگر این الگوریتم‌ روی یک لیست مرتب شده اعمال شود، کارایی آن بهتر از یک لیست نامرتب نیست و تقریبا همان اندازه زمان صرف می‌کند.

​

مرتب‌سازی انتخابی
این الگوریتم یکی از قدیمی‌ترین الگوریتم‌های مرتب‌سازی است که ساختار و پیاده‌سازی آن بسیار ساده است. الگوریتم انتخابی یک مرتب‌سازی درجا (In Place) محسوب می‌شود و مصرف حافظه آن فقط 1 است. از این نظر عالی است ولی این الگوریتم در لیست‌های بسیار بزرگ کارایی‌اش را کاملا از دست می‌دهد. تصور کنید که در دست خود چند برگه دارید که اعداد یک تا بیست روی آنها نوشته شده و نامرتب هستند. حالا می‌خواهید آنها را مرتب کنید. بدین شکل عمل می‌کنید که یک‌بار لیست را پیمایش می‌کنید و کمترین مقدار (که در اینجا عدد یک است) را می‌یابید. سپس آن برگه به ابتدای لیست‌ برگه‌ها منتقل می‌کنید. حالا مابقی برگه‌ها را دوباره پیمایش می‌کنید و کوچک‌ترین عدد را در بین آن پیدا می‌کنید( که حالا عدد دو است). آن برگه را به ابتدای لیست می‌آورید و بعد از برگه اول قرار می‌دهید. همین روش را تا مرتب شدن کل برگه‌ها ادامه می‌دهید. همانطور که دیدید برای پیدا کردن هر برگه نیاز است یک بار کل برگه‌های باقی مانده را پیمایش کنید و از این جهت کارایی این الگوریتم پایین محسوب می‌شود. نماد O بزرگ مرتب‌سازی انتخابی در بهترین و بدترین حالت، (O(n2 است.
مرتب‌‌سازی کتابخانه‌ای
همانطور که هفته پیش اشاره کردم این الگوریتم در سال 2006 توسط سه محقق ابداع شد. این روش به نوعی فرزند مرتب‌سازی درجی (Insertion Sort) محسوب می‌شود و کارکردی شبیه به آن دارد.
تصور کنید که شما در کتابخانه کار می‌کنید و تمامی کتاب‌های یک بخش، بر اساس حروف الفبا از الف تا ی مرتب شده‌اند. حال اگر کسی یک کتاب با نام «باران در آسمان نگاهت» اهدا کند و بخواهید آن کتاب را در جای مناسب قرار دهید، ‌باید آن را در حرف ب گذاشته و تمامی کتاب‌های بعد از آن را یک مکان جابه‌جا کنید یا به اصطلاح Shift دهید. این روش همان مرتب‌سازی درجی است.
اما اگر از قبل، به اندازه یک کتاب فضای خالی بعد از هر دسته کتاب‌های متعلق به یک حرف ایجاد کرده باشید (مثلا یک فضای خالی بعد از حرف ب)، آنگاه وقتی بخواهید کتاب مورد نظر را در جای درستش قرار دهید، فقط نیاز است که تعداد کمی کتاب را به اندازه یک مکان جا‌به‌جا کنید (فقط برخی از کتاب‌های حرف ب)؛ نه کل کتاب‌های بعد از آن را.
این کار دقیقا روشی است که الگوریتم کتابخانه‌ای انجام می‌دهد. البته ناگفته نماند اگر از این الگوریتم استفاده کنید، به فضاهای هرز (Gap) بیشتری نیاز خواهید داشت.
مرتب‌سازی درختی

​

همانطور که از نام این روش مرتب‌سازی مشخص است، این الگوریتم بر اساس روش درخت جستجوی دودویی (Binary Search Tree) طراحی شده است. دانشجویان کامپیوتر که درس ساختمان داده را گذرانده‌اند با این روش جستجو آشنا هستند.
اما روش کاری مرتب سازی درختی به این شکل است که ابتدا یک درخت دودویی از عناصر لیست می‌سازد، سپس آن درخت را به صورت میان ترتیب (In-Order) پیمایش کرده و نتیجه آن یک لیست مرتب شده خواهد بود.
از این الگوریتم بیشتر زمانی استفاده می‌شود که بخواهید داده‌ها را از یک فایل بخوانید و آنها را مرتب کنید. به صورت کلی وقتی داده‌هایی از یک فایل خوانده می‌شود آنها را در یک ساختمان داده‌ای مانند آرایه به صورت موقت ذخیره می‌کنند و سپس روی آن عملیات مرتب‌سازی انجام می‌شود.
ولی وقتی از مرتب‌سازی درختی استفاده کنید، هنگام خواندن داده‌ها و قرار دادن آن در درخت دودویی، داده‌ها مرتب می‌شوند. این الگوریتم جزو روش‌های سریع محسوب می‌شود.
ولی یک مشکل بزرگ دارد که مصرف حافظه آن (O(n است. حتی اگر این الگوریتم را برای لیست‌های پیوندی (Linked List) استفاده کنید، اوضاع بدتر می‌شود و مصرف حافظه آن به (O(n2 خواهد رسید؛ یا یک لیست مرتب شده به این الگوریتم داده شود که مرتب کند. اما این حالات بد را می‌توان را با یک نسخه بهینه شده از درخت جستجوی دودویی با نام درخت جستجوی باینری خود توازن کمی بهبود بخشید.
مرتب‌سازی تیم
الگـوریتم تـیم که به افتخار مخترع آن تیم پیترز نام‌گذاری شده است، یکی از بهترین الگوریتم‌ها محسوب می‌شود که در سال 2002 معرفی شد.
این الگوریتم یک الگوریتم مرتب‌سازی دورگه یا مختلط بوده که از ترکیب الگوریتم‌های درجی و ادغامی شکل گرفته است (در مورد درجی و ادغامی در شماره هفته پیش صحبت کردیم).
به دلیل قدرت بالا، این الگوریتم به عنوان مرتب‌ساز پیش‌فرض در جاوا و همچنین سیستم‌عامل اندروید استفاده می‌شود.
مرتب‌سازی روان
این روش مرتب‌سازی در سال 1981 طراحی شد و یک فرزند از الگوریتم هرمی محسوب می‌شود و کارکردی کلی شبیه به آن دارد. اما مرتب‌سازی روان (Smoothsort) به دلیل روش متفاوتی که استفاده می‌کند در هنگامی که به یک لیستی مواجه شود که برخی از عناصر آن مرتب شده هستند، کارکردی بهتر از خود نشان می‌دهد و به جای O(n log n) پیچیدگی آن به (O(n کاهش می‌یابد. به دلیل پیچیدگی بالای پیاده‌سازی، از توضیح درباره نحوه کارکرد آن صرف نظر می‌کنیم؛ اگر علاقه‌مند هستید می‌توانید به دایره المعارف ویکی‌پدیا مراجعه کنید.
مرتب‌سازی مقدمه‌ای
پدر این الگوریتم، مرتب‌سازی سریع و مادر آن مرتب‌سازی هرمی است. این حرف از اینجا نشات می‌گیرد که وقتی مرتب‌سازی مقدمه‌ای آغاز می‌شود، از روش الگوریتم مقدمه‌ای استفاده می‌کند و در ادامه کار روش‌ را تغییر می‌دهد و از الگوریتم هرمی برای مرتب‌سازی استفاده می‌کند. همانطور که والدین این الگوریتم از روش مقایسه‌ای برای مرتب‌سازی استفاده می‌کنند، مرتب‌سازی مقدمه‌ای هم این روش استفاده می‌کند ولی عملکردی بهتر از هر دو والد دارد؛ پیچیدگی عملکرد بد آن نهایتا (O(n log n خواهد بود.
مرتب‌سازی بوگو
این الگوریتم که با نام‌های مرتب‌سازی بوگو، مرتب‌سازی تصادفی، مرتب‌سازی میمونی و مرتب‌سازی شات‌گان شناخته می‌شود، اصولا برای مقاصد آموزشی و مقایسه‌ای برای کارکرد این الگوریتم و الگوریتم‌هایی که کارایی بالاتری دارند، استفاده می‌شود. در واقع در هیچ کدی از این روش استفاده نمی‌شود.
با وجود اینکه این الگوریتم صرفا برای آموزش است ولی بعید می‌دانم که شما به عنوان یک دانشجو یا فارغ‌التحصیل رشته‌های کامپیوتری، نام این مرتب‌سازی را شنیده‌ باشید!
راه‌کاری که این الگوریتم استفاده می‌کند، بسیار ساده‌ است و بدین صورت خواهد بود که ابتدا بررسی می‌شود که آیا لیست مرتب است یا خیر. اگر نبود، ترتیب عناصر لیست داده‌های را به صورت تصادفی تغییر می‌دهد و دوباره بررسی می‌کند که آیا لیست مرتب شد یا خیر. تا زمانیکه به یک لیست مرتب از داده‌ها برسد این رویه را ادامه می‌دهد. جالب است بدانید نام این مرتب‌سازی از واژه Bogus به معنای جعلی و ساختگی آمده است.
یک الگوریتم با نام Bozo Sort وجود دارد که به نوعی خواهر‌خوانده مرتب‌سازی بوگو محسوب می‌شود و روشی مشابه را انجام می‌دهد. در مرتب‌سازی بوزو در صورت مرتب نبودن لیست، به جای اینکه کل عناصر لیست را درهم بریزد (مانند روش بوگو) فقط دو عنصر انتخاب می‌شوند و جای آنها جابه‌جا شده و سپس بررسی می‌شود که لیست مرتب شده است یا خیر.
حرف پایانی
در طی این دو هفته، شما کم و بیش با 12 الگوریتم معروف و مهم مرتب‌سازی آشنا شدید. علاوه بر اینها درباره مـــفهوم نشانه O بــرزگ (Big O) که میزان پیچیدگی‌ الگوریتم‌ها را نشان می‌دهد، بحث کردیم و در جدولی مقایسه‌ای میان نشانه O بزرگ مهمترین الگوریتم‌ها داشتیم؛ هم بهترین و بدترین پیچیدگی، هم پیچیدگی میانگین و در نهایت میزان مصرف حافظه در صورت استفاده از آن روش برای مرتب‌سازی.
آشنا بودن به این روش‌ها کمک بسیار زیادی به سرعت و کارایی برنامه‌هایی که می‌نویسیم می‌کند. این موضوع خیلی مهم است که بدانیم هنگام کار با انواع ساختمان داده‌ها، کدام روش برای ما نتیجه بهتری می‌دهد یا وقتی میزان داده کمی داریم چرا لقمه را دور سر بچرخانیم و الگوریتم‌های پیچیده را به کار ببریم؛ در حالیکه می‌توانیم یک الگوریتم ساده را بنویسیم که با میزان داده کم، کارایی آن مشابه الگوریتم پیچیده خواهد بود.
ستون حافظه در جدول کنار صفحه اهمیت زیادی دارد. این ستون میزان مصرف حافظه توسط الگوریتم‌های مختلف هنگام مرتب‌سازی داده‌ها را نشان می‌دهد. حالتی که مقدار حافظه مورد نیاز عدد 1 است، بهترین حالت است. زیرا فقط یک قسمت از حافظه برای انجام عملیات مرتب‌سازی مورد استفاده قرار می‌گیرد. تصور کنید که شما می‌خواهید یک لیست 1 میلیونی از داد‌ه‌ها را مرتب کنید و دو الگوریتم پیش‌رو دارید: الگوریتم الف و الگوریتم ب. هر دو الگوریتم هم پیچیدگی و کارایی یکسانی دارند. میزان مصرف حافظه الگوریتم الف، یک است، درحالیکه میزان حافظه مورد نیاز الگوریتم ب، n است. بدون شک شما باید به سراغ الگوریتم الف بروید.
به طور کلی آشنا بودن با انواع روش‌ها (هر چند آشنایی کم) کمک بسیار زیادی به کدنویسی و افزایش کارایی کد شما خواهد داشت.
به نقل از عصر ارتباط