مقایسه الگوریتم‌های مرتب‌سازی

در این مقاله سعی شده است با نگاه تخصصی تری به الگوریتم‌های مرتب سازی، کارایی آن‌ها و همسنجی الگوریتم‌ها، در حالت‌های مختلف پرداخته شود. به همین دلیل از توضیح دقیق رویهٔ الگوریتم‌ها و شبه کدها که در صفحات دیگر ویکی‌پدیا و دیگر سایت‌ها به وفور یافت می‌شود، خودداری کرده‌ایم و فرض می‌کنیم خواننده حداقل آشنایی ای با الگوریتم‌های معروف مرتب سازی دارد.
هر شیوه مرتب سازی در ۳ بخش بررسی شده است. در بخش "درباره" سعی شده یادآوری کوتاهی از رویه الگوریتم شود. در بخش "مقایسه"، هر الگوریتم با الگوریتم‌های مشابه از لحاظ پیاده سازی و کارآمدی مقایسه شده است. در بخش "گونه‌های دیگر" الگوریتم‌های مرتب سازی مشتق شده از آن شیوه، معرفی شده است. درنهایت پیوندی قرار داده شده است که پیاده سازی آن روش به اکثر زبان‌ها را در خود جای داده است.

تعریف

در ابتدا بعضی مفاهیم پایه‌ای مربوط به مرتب سازی را توضیح می‌دهیم:

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

مقایسه الگوریتم‌های مرتب‌سازی برای پیاده سازی هر یک از روشهای مرتب سازی، ممکن است الگوریتم‌های مختلفی وجود داشته باشند. این الگوریتم‌ها را می‌توان بر اساس فاکتورهای زیر با یکدیگر مقایسه نمود: 1- سرعت متوسط مرتب سازی اطلاعات 2- سرعت الگوریتم مرتب سازی در بهترین و بدترین حالت 3- رفتار الگوریتم (طبیعی یا غیر طبیعی) 4- شرکت عناصر مساوی در مرتب سازی

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

کاری از نیلوفر خلیلی

همسنجی سریع

جدول زیر مربوط به الگوریتم‌های تطبیقی است. به کمک درخت تصمیم می‌توان ثابت کرد حداقل زمان مرتب سازی با روش مقایسه در حالت میانگین، $O(n logn) \!$ می‌باشد.

نام	میانگین	بدترین	حافظه	پایداری	روش	نکات اضافه
مرتب سازی حبابی	02 $\mathcal{} n^2$	03 $\mathcal{} n^2$	01 $\mathcal{} {1}$	بله	تعویض	کد کوتاه
مرتب‌سازی حبابی دوسویه	03 —	03 $\mathcal{} n^2$	01 $\mathcal{} {1}$	بله	تعویض
مرتب سازی شانه‌ای	03 —	04 —	01 $\mathcal{} {1}$	خیر	تعویض	کد کوتاه
مرتب‌سازی گورزاد	03 —	03 $\mathcal{} n^2$	01 $\mathcal{} {1}$	بله	تعویض	کد کوتاه
مرتب سازی انتخابی	02 $\mathcal{} n^2$	03 $\mathcal{} n^2$	01 $\mathcal{} {1}$	بستگی دارد	انتخاب	پایدار بودن آن به پیاده سازی بستگی دارد
مرتب سازی درجی	02 $\mathcal{} n^2$	03 $\mathcal{} n^2$	01 $\mathcal{} {1}$	بله	درج	حالت میانگین همچنین $\mathcal{O}\left({n + d} \right)$، می‌باشد که d تعداد درج هاست
مرتب سازی شل	03 —	02 $\mathcal{} {n \log^2 n}$	01 $\mathcal{} {1}$	خیر	درج
مرتب سازی درخت دودویی	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {n \log n}$	03 $\mathcal{} n$	بله	درج	باید از یک درخت دودویی جستجو خودمتوازن گر استفاده شود
مرتب سازی کتاب خانه‌ای	01 $\mathcal{} {n \log n}$	03 $\mathcal{} n^2$	03 $\mathcal{} n$	بله	درج
مرتب سازی ادغامی	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {n \log n}$	03 $\mathcal{} n$	بله	ادغام
مرتب سازی ادغامی درجا	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {1}$	بستگی دارد	ادغام	نمونه پیاده سازی اینجا: [۱]؛ می‌تواند به عنوان یک مرتب سازی پایدار پیاده سازی شود: [۲]
مرتب سازی هرمی	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {1}$	بله	انتخاب
مرتب‌سازی روان	03 —	01 $\mathcal{} {n \log n}$	01 $\mathcal{} {1}$	خیر	انتخاب
مرتب سازی سریع	01 $\mathcal{O}\left({n \log n} \right)$	03 $\mathcal{O}\left(n^2 \right)$	02 $\mathcal{O}\left({\log n} \right)$	بستگی دارد	تقسیم بندی	با توجه به شیوه‌ای که محور عمل می‌کند، می‌تواند به صورت پایدار پیاده سازی شود [[گونهٔ دیگری از آن از حافظه $\mathcal{O} \left(n \right)$ استفاده می‌کند.
مرتب سازی درونگرا	01 $\mathcal{O}\left({n \log n} \right)$	01 $\mathcal{O}\left({n \log n} \right)$	02 $\mathcal{O}\left({\log n} \right)$	خیر	مرکب	استفاده شده در پیاده سازی‌های SGI STL
مرتب‌سازی شکیبانه	03 —	01 $\mathcal{O} \left({n \log n} \right)$	03 $\mathcal{O}\left(n \right)$	خیر	درج و انتخاب	بزرگ ترین زیردنباله‌های افزایشی را با $O(n logn) \!$ پیدا می‌کند.
مرتب‌سازی رشته‌ای	01 $\mathcal{O}\left({n \log n} \right)$	03 $\mathcal{O} \left({n^2} \right)$	03 $\mathcal{O}\left(n \right)$	بله	انتخاب
Tournament sort	01 $\mathcal{O}\left({n \log n} \right)$	01 $\mathcal{O}\left({n \log n} \right)$			انتخاب

جدول زیر مربوط به الگوریتم‌های ناتطبیقی است. این الگوریتم‌ها محدودیت $O(n logn) \!$ الگوریتم‌های تطبیقی را ندارند. $k$ اندازه کلیدها و $s$ مقداری است که در پیاده سازی استفاده شده است. خیلی از این الگوریتم‌ها بر این فرض استوارند که سایز کلیدها به قدری بزرگ است که همهٔ کلیدها مقدار یکسانی دارند. و $<< \!$ یعنی "خیلی کمتر از".

نام	میانگین	بدترین	حافظه	پایداری	n << 2k	نکات دیگر
مرتب‌سازی لانه‌کبوتری	$\mathcal{O}\left({n + 2^k} \right)$	$\mathcal{O}\left({n + 2^k} \right)$	$\mathcal{O}\left({2^k} \right)$	بله	بله
مرتب سازی سطلی	$\mathcal{O}\left({n \cdot k} \right)$	$\mathcal{O}\left({n^2 \cdot k} \right)$	$\mathcal{O}\left({n \cdot k} \right)$	بله	خیر	فرض می‌کند عناصر در محدودهٔ خود یکنواخت پخش شده‌اند.
مرتب سازی شمارشی	$\mathcal{O}\left({n + k} \right)$	$\mathcal{O}\left({n + k} \right)$	$\mathcal{O}\left({n + 2^k} \right)$	بله	بله	اگر k = $\mathcal{O}\left({n} \right)$ آنگاه میانگین = $\mathcal{O}\left({n} \right)$
مرتب سازی مبنایی از کم ارزش ترین	$\mathcal{O}\left({n \cdot \frac{k}{s}} \right)$	$\mathcal{O}\left({n \cdot \frac{k}{s}} \right)$	$\mathcal{O}\left(n \right)$	بله	خیر
مرتب سازی مبنایی از پرارزش ترین	$\mathcal{O}\left({n \cdot \frac{k}{s}} \right)$	$\mathcal{O}\left({n \cdot \frac{k}{s} \cdot 2^s} \right)$	$\mathcal{O}\left({\frac{k}{s} \cdot 2^s} \right)$	خیر	خیر
مرتب سازی گسترده	$\mathcal{O}\left({n \cdot \frac{k}{s}} \right)$	$\mathcal{O}\left({n \cdot \left({\frac{k}{s} + s} \right) } \right)$	$\mathcal{O}\left({\frac{k}{s} \cdot 2^s} \right)$	خیر	خیر

الگوریتم‌های مرتب سازی تطبیقی

مرتب سازی حبابی

درباره

نمایش مرتب سازی حبابی

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

مقایسه

در مرتب سازی حبابی موقعیت عناصر درون لیست نقش بسزایی در تعیین عملکرد آن دارد. از آنجایی که عناصر بزرگ در ابتدای لیست به سرعت جابجا (swap) می‌شوند، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی‌کنند. اگرچه عناصر کوچک نزدیک به آخر لیست (که باید به سمت ابتدای لیست بیایند) بسیار کند حرکت می‌کنند. این تفاوت در سرعت به حدی است که به عناصر بزرگ، لاک پشت‌ها، و به عناصر کوچک، خرگوش‌ها می‌گویند.
تلاش بسیاری انجام شده که سرعت حرکت لاک پشت‌ها در مرتب سازی حبابی افزایش یابد. از جمله می‌توان از Cocktail sort نام برد که در این زمینه بسیار خوب عمل می‌کند ولی بدترین زمان اجرای آن هنوز $O(n^2) \!$ است. مرتب سازی شانه‌ای (Comb sort) عناصر بزرگ با فاصله‌های زیاد را مقایسه می‌کند و لاک پشت‌ها را با سرعت فوق العاده‌ای حرکت می‌دهد سپس با کم تر و کم تر کردن این فاصله‌ها لیست را به سرعت مرتب می‌کند، به طوری که سرعت متوسط آن قابل مقایسه با الگوریتم‌های پر سرعتی مثل مرتب سازی سریع (Quick Sort) می‌باشد.
علی رغم پیاده سازی ساده، مرتب سازی حبابی در عمل در مقایسه با الگوریتم‌های دیگری که پیچیدگی $O(n^2) \!$ دارند، کارایی کمتری دارد. تا جایی که تحقیقات نشان می‌دهد مرتب سازی حبابی در عمل ۵ برابر کند تر از مرتب سازی درجی و ۴۰ درصد کندتر از مرتب سازی انتخابی می‌باشد.

گونه‌های دیگر

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

مرتب سازی انتخابی

درباره

نمایش مرتب سازی انتخابی

یک الگوریتم تطبیقی ساده دیگر برای مرتب سازی یک لیست، مرتب سازی انتخابی است. شیوه مرتب کردن آن به این صورت است که در هر مرحله کوچکترین (یا بزرگترین) عنصر آرایه را با $O(n) \!$ می‌یابد و آن را به مکان خود می‌برد. بعد دومین عنصر کوچک (یا بزرگ) و به همین ترتیب ادامه می‌دهد تا آرایه مرتب شود.

مقایسه

در بین الگوریتم‌های هم مرتبه، مرتب سازی انتخابی عموما سریع تر از مرتب سازی حبابی و (Gnome sort) عمل می‌کند. اما در مقایسه با مرتب سازی درجی کندتر است.(با یک محاسبهٔ ساده مرتب سازی درجی حدودا نصف مقایسه‌های مرتب سازی انتخابی را انجام می‌دهد). در عمل این الگوریتم برای مرتب سازی یک لیست کوچک، الگوریتمی نسبتا کارا به شمار می‌رود. نمودار کارایی الگوریتم برحسب ورودی‌ها را در زیر می‌بینید:

نمودار زمان برحسب تعداد ورودی

گونه‌های دیگر

پیاده سازی دوطرفهٔ مرتب سازی انتخابی، cocktail sort نامیده می‌شود که در هر پیمایش عنصر کمینه و بیشینه را با هم پیدا می‌کند. این کار تعداد پیمایش‌ها را به نصف کاهش داده اما تعداد مقایسه‌ها و جابه جایی‌ها را کاهش نمی‌دهد. البته cocktail sort غالبا به عنوان گونهٔ تغییر یافتهٔ مرتب سازی حبابی شناخته می‌شود.
Bingo sort نیز گونهٔ تغییریافتهٔ دیگری از مرتب سازی انتخابی است برای زمانی که داده‌های تکراری زیادی میان ورودی‌ها وجود داشته باشد. این الگوریتم کلیدها را برحسب تعداد تکرارشان مرتب می‌کند تا به بزرگترین کلید برسد سپس آن کلیدها را به تعداد تکرارشان به مکان نهایی خود می‌برد، مثل مرتب سازی شمارشی. در واقع مرتب سازی انتخابی برای انتقال یک مقدار به مکان نهایی خود یک پیمایش بر روی داده‌های باقیمانده انجام می‌دهد. در حالی که در Bingo sort برای هر کلید (value و نه Item) دو بار پیمایش انجام می‌شود. یک بار برای یافتن کلید بزرگتر بعدی و یک بار برای انتقال تمام خانه‌ها با آن کلید به محل نهاییشان. بنابراین اگر به طور متوسط، از هر کلید ۲ تکرار یا بیشتر داشته باشیم Bingo sort عموما سریع تر عمل خواهدکرد.

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

درباره

نمایش گرافیکی مرتب سازی درجی

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

مقایسه

این الگوریتم در عمل از بسیاری از الگوریتم‌های هم مرتبه خود مثل مرتب سازی حبابی و مرتب سازی انتخابی بهتر عمل می‌کند و متوسط زمان اجرای آن $n^2/4 \!$ می‌باشد و برای تعداد ورودی‌های کم الگوریتم کارایی محسوب می‌شود. همچنین برای مرتب سازی مجموعه‌ای از داده‌های تقریبا مرتب کارآمد است. و اگر تعداد وارونگی‌ها، d باشد، این الگوریتم دارای زمان اجرای O(n)+d خواهد بود.
بهترین ورودی برای آن داده‌های مرتب و بدترین ورودی آرایه‌ای است که به صورت معکوس مرتب شده باشد.
در حالت کلی، مرتب سازی درجی در آرایه $O(n^2) \!$ بار عمل نوشتن انجام می‌دهد؛ درحالیکه مرتب سازی انتخابی تنها $O(n) \!$ بار می‌نویسد. به همین دلیل مرتب سازی انتخابی در مواردی که نوشتن در حافظه نیازمند هزینه زیادی باشد، سریعتر عمل می‌کند مانند نوشتن در flash memory.
برخی الگوریتم‌های حل و تقسیم، مثل مرتب سازی ادغامی یا مرتب سازی سریع که با تقسیم لیست به صورت بازگشتی به زیرلیست‌های مرتب شده، عمل مرتب سازی را انجام می‌دهند. یک راه بهینه سازی برای این الگوریتم‌ها، استفاده از مرتب سازی درجی برای مرتب کردن زیرلیست‌های کوچک است که در کل موجب تسریع الگوریتم می‌شود. سایز زیرلیست‌هایی که استفاده از مرتب سازی درجی برای آن‌ها کارایی بهتری دارد حدودا بین ۸ تا ۲۰ عنصر است.

گونه‌های دیگر

مرتب سازی درجی دودویی گونه‌ای از مرتب سازی درجی است که در آن برای یافتن محل مناسب هر عنصر از جستجوی دودویی استفاده می‌شود. این الگوریتم برای زمانی که هزینهٔ مقایسه‌ها از هزینهٔ جابه جایی‌ها بیشتر باشد، مانند زمانی که لیست ورودی مرتب شده است، مناسب تر می‌باشد.
D.L.Shell مرتب سازی درجی را با الگوریتمی تحت عنوان Shell sort بهبود بخشید. این الگوریتم مرتب سازی را با مقایسه دو عنصر که فاصله آن‌ها از هم در هر مرحله کم می‌شود، انجام می‌دهد. مرتب سازی شل پیچیدگی الگوریتم را در عمل به طور قابل توجهی افزایش داده که در دو نسخه مختلف با $(O(n^(3/(2)) \!$ و $O(n^(4/3)) \!$ عمل می‌کند.
گونهٔ تغییریافتهٔ دیگری از مرتب سازی درجی در سال ۲۰۰۶ با نام مرتب سازی کتابخانه‌ای طراحی شد که در آن تعداد کمی فضای بدون استفاده در سراسر آرایه پخش می‌شود. این کار باعث تسریع شدن درج‌های بعدی می‌شود. طراحان ثابت کرده‌اند که این الگوریتم با احتمال زیادی در زمان $O(n log n) \!$ اجرا می‌شود.
Gnome sort نیز الگوریتم دیگری است که با تغییر کوچکی در مرتب سازی درجی ایجاد شده است به این ترتیب که در هر مرحله برای درج عنصر به جای شیفت دادن از جابه جایی تعدادی از عناصر مجاور استفاده می‌شود، مثل مرتب سازی حبابی.

مرتب سازی ادغامی

درباره

نمایش مرتب سازی ادغامی

این مرتب سازی به طریقهٔ تقسیم و حل، لیست را مرتب می‌کند. به این صورت که آرایه را به دو لیست با اندازهٔ تقریبا مساوی تقسیم کرده، هر زیر لیست را به صورت بازگشتی مرتب و سپس با هم ادغام می‌کند.

مقایسه

مرتبهٔ این الگوریتم از حل رابطهٔ بازگشتی $T(n)=2T(n/2)+n \!$ حاصل می‌شود. در بدترین حالت تعداد مقایسه‌های آن تقریبا $n \left \lceil log n \right \rceil - 2^\left \lceil log n \right \rceil +1 \!$ می‌باشد که در حالت متوسط مقدار آن a.n تا کم می‌شود که در آن a=0.2645.
تعداد مقایسه‌های مرتب سازی ادغامی دربدترین حالت حدود ۰٫۳۹ کمتر از مرتب سازی سریع در حالت متوسط است. بدترین حالت مرتب سازی ادغامی زمانی اتفاق می‌افتد که کلید تمام عناصر با هم برابر باشند. لازم به ذکر است این حالت برای مرتب سازی سریع بهترین حالت است! در پیاده سازی بازگشتی آن تابع مرتب سازی در بدترین حالت ۲n-1 بار صدا زده می‌شود در حالی که در مرتب سازی سریع n بار صدا زده می‌شود.
پیاده سازی معمولی مرتب سازی ادغامی به صورت غیردرجا و با حافظه کمکی n است. (البته پیاده سازی‌هایی نیز وجود دارد که به صورت غیردرجاست اما به n/2 حافظه اضافی نیاز دارد). پیاده سازی درجای آن (بدون نیاز به حافظه کمکی) نیز امکان پذیر است اما پیچیده بوده و در عمل کارآیی آن را کاهش می‌دهد. مرتب سازی ادغامی درجا برخلاف نوع ساده آن لزوما پایدار نیست.
در مقایسه مرتب سازی ادغامی با دیگر الگوریتم‌ها، می‌توان گفت اگرچه در اکثر موارد از مرتب سازی هرمی کندتر عمل می‌کند و همچنین حافظهٔ بیشتری می‌گیرد، و اگرچه در یک نگاه کلی مرتب سازی سریع به عنوان سریع‌ترین الگوریتم مرتب سازی شناخته می‌شود، اما مرتب سازی ادغامی یک مرتب سازی پایدار است که اجرای موازی آن بهتر عمل می‌کند و همچنین اغلب بهترین انتخاب برای مرتب سازی یک لیست پیوندی است. زیرا اجرای مرتب سازی هرمی روی آن غیرممکن و اجرای مرتب سازی سریع کارایی چندانی ندارد.
در جاوا، دستور Array.sort() یا از مرتب سازی ادغامی استفاده می‌کند یا از یک نوع مرتب سازی سریع وابسته به نوع داده که برای کارایی بیشتر هنگامی که کمتر از ۷ ورودی داریم به مرتب سازی درجی تغییر می‌کند.
Python نیز از timsort استفاده می‌کند که ترکیبی از مرتب سازی ادغامی و درجی می‌باشد.

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

درباره

نمایش گرافیکی مرتب سازی هرمی

این مرتب سازی که از خانواده مرتب سازی انتخابی محسوب می‌شود، ابتدا داخل آرایه یک هرم بیشینه (یا کمینه) می‌سازد، سپس بزرگترین مقدار را در انتهای آرایه قرار می‌دهد. سپس با اعداد باقیمانده دوباره این عمل را انجام می‌دهد. بزرگترین مقدار را در هرم یافته و در مکان درست خود قرار می‌دهد و این کار را تا زمانی که هرم خالی شود انجام می‌دهد.

مقایسه

این الگوریتم که یک مرتب سازی غیرپایدار اما درجاست، در بدترین حالت دارای پیچیدگی $O(n log n) \!$ می‌باشد و پیاده سازی آن برخلاف مرتب سازی سریع به صورت بازگشتی نیست.
در مقایسه با مرتب سازی سریع، معمولاً مرتب سازی سریع، کارایی بیشتری از خود نشان می‌دهد اما بدترین حالت آن $O(n^2) \!$ می‌باشد که آن را برای تعداد زیادی داده ناکارآمد می‌کند.

گونه‌های دیگر

Introsort یک الگوریتم مرتب سازی جالب برای ترکیب مرتب سازی سریع و هرمی است، به نحوی که برتری‌های هر دو را در خود جای دهد: سرعت مرتب سازی هرمی در حالت بد و سرعت مرتب سازی سریع در حالت میانگین.
در مقایسه با مرتب سازی ادغامی، معمولاً در دستگاه‌هایی که حافظه نهان (Cache) کمتری دارند، مرتب سازی هرمی سریع تر عمل می‌کند. از طرف دیگر مرتب سازی ادغامی چندین مزیت بر مرتب سازی هرمی دارد. ازجمله این که پایدار است، موازی سازی آن بهتر صورت می‌گیرد و قابل پیاده سازی روی لیست پیوندی است. الگوریتم مرتب سازی هرمی مبنای ۳ نیز دقیقا شبیه الگوریتم مذکور است با این تفاوت که به جای یک هرم دودویی از یک هرم سه سه یی استفاده می‌کند. به این معنا که هر عنصر می‌تواند ۳ فرزند داشته باشد. پیاده سازی این الگوریتم مشکل است اما به تعداد ثابتی عمل مقایسه و جابجایی را کاهش می‌دهد. این روش حدود ۱۲% سریع تر از حالت معمولی مرتب سازی هرمی عمل می‌کند.
نوع دیگری از مرتب سازی هرمی با استفاده از درخت دکارتی انجام می‌شود که عنصر را تا زمانی که کلیدهای کوچکتر در دو طرف آن گره، درون خروجی مرتب شده قرار نگرفته باشند، درون هرم اضافه نمی‌کند. به این ترتیب اثبات می‌شود که الگوریتم برای ورودی‌هایی که از قبل تقریبا مرتب شده‌اند سریع تر از $O(n log n) \!$ عمل می‌کند.
به خاطر حدبالای ثابت اجرای آن و همچنین حافظهٔ کمکی ثابت، در سیستم‌های تعبیه شده که محدودیت زمانی دارند یا سیستم‌های امنیتی از این مرتب سازی استفاده می‌کنند.

مرتب سازی سریع

درباره

نمایش گرافیکی مرتب سازی سریع

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

مقایسه

بهترین حالت برای این الگوریتم زمانی اتفاق می‌افتد که محور در وسط واقع شود، در این صورت این الگوریتم در $O(n log n)\!$ و سریع تر از الگوریتم‌های دیگر اجرا می‌شود.
بدترین حالت زمانی است که محور پس از تقسیم در ابتدا یا انتهای آرایه قرار گیرد. که در این حالت زمان اجرای آن $O(n^2) \!$ خواهدبود.
پیاده سازی آن به صورت تصادفی، محور را در هر مرحله به شکل تصادفی انتخاب می‌کند. پیاده سازی آن برای لیست پیوندی معمولاً کارا نیست زیرا به دلیل نبود دسترسی تصادفی، محور خوبی نمی‌توان انتخاب کرد.
مرتب سازی سطلی ای که با دو سطل انجام بشود بسیار شبیه مرتب سازی سریع است. محور در این مورد، عنصر میانی کلیدهاست. این عمل، حالت میانگین را برای ورودی‌های به طور یکنواخت توزیع شده، به خوبی اصلاح می‌کند.
این الگوریتم در عمل برای مرتب سازی آرایه‌های نسبتا کوچک اصلا مناسب نیست. به علاوه بخش تقسیم بندی آرایه نیز مشکل بزرگی در زمان اجرا می‌باشد. به همین دلیل پیشنهاد می‌شود برای ۷ داده یا کمتر از انواع دیگر مرتب سازی مثل مرتب سازی درجی استفاده شود، به علاوه به جای پیاده سازی بخش تقسیم بندی برای بیش از ۴۰ داده می‌توان از میانهٔ ۹، برای کمتر از ۴۰ داده از میانهٔ ۳ و برای آرایه‌های بسیار کوچک از عضو وسط استفاده کرد.
این مرتب سازی را نیز می‌توان مثل مرتب سازی ادغامی به صورت موازی اجرا نمود. اگر n پردازنده داشته باشیم، می‌توان با $O(n) \!$، n عنصر را به p زیرلیست تقسیم نمود، سپس هر بخش را با $O(\frac{n}{p} log \frac{n}{p}) \!$ مرتب کرد. یک مزیت پیاده سازی موازی آن این است که نیازی به همگام سازی نیست و وقتی که زیرلیست‌ها آماده شد، اجرای هر بخش کاملا مستقل از بخش‌های دیگر است. این مرتب سازی، برای اجرا بر روی معماری‌های کامپیوتری امروزی بسیار مناسب است و از سلسله مراتب حافظه بهترین استفاده را می‌کند. پیاده سازی بسیار خوبی از این الگوریتم را می‌توانید در کد منبع جاوا، در کتابخانهٔ java.util.array مشاهده نمایید.

الگوریتم‌های مرتب سازی ناتطبیقی

مرتب سازی مبنایی (پایه‌ای)

درباره

الگوریتمی است که لیستی از $n \!$ داده با طول حداکثر $k \!$ را در $O(nk) \!$ مرتب می‌کند. به این صورت که ورودی را اگر رشته است به حروف سازنده اش و اگر عدد صحیح است به ارقامش شکسته و ابتدا کم ارزش‌ترین (یا پرارزش‌ترین) بخش آن‌ها را مقایسه کرده، مرتب می‌کنیم، سپس بخش بعدی را مقایسه می‌کنیم و به همین ترتیب. برای مرتب کردن هر بخش می‌توانیم از مرتب سازی شمارشی استفاده کنیم. اگر از کم ارزش‌ترین بخش شروع کنیم به آن LSD radix sort می گویند و اگر از پرارزش‌ترین قسمت شروع کنیم MSD radix sort.

مقایسه

می‌توان برای کارآمدتر کردن الگوریتم از صف به عنوان پیمانه‌ها استفاده کرد، به این ترتیب که هر بار اعداد را برحسب رقمشان درون یک صف قرار دهیم. پس از پایان مرحله، دوباره اعداد را از صف درون آرایه بریزیم و این کار را برای رقم‌های بعدی تکرار کنیم. این یک مدل ساده ولی نسبتا مناسب برای پیاده سازی الگوریتم است.
گفتیم که زمان اجرای مرتب سازی مبنایی $O(kn) \!$ می‌باشد. وقتی که $k \!$ از حدود $log n \!$ باشد، ممکن است به نظر برسد که مرتب سازی مبنایی، برتری خاصی نسبت به الگوریتم‌های تطبیقی مثل مرتب سازی ادغامی نداشته باشد. اما باید توجه داشت که پیچیدگی $O(n log n) \!$ بدست آمده برای این الگوریتم‌های تطبیقی، در واقع تعداد مقایسه‌های دو عدد کامل را می شمارد و سریع‌ترین زمان ممکن برای این مقایسه برابر است با k. بنابراین اگر ما تعداد عملیات بنیادین انجام شده را بشماریم، پیچیدگی مرتب سازی ادغامی از $O(k n log n) \!$ خواهد بود.

مرتب سازی شمارشی

درباره

یک الگوریتم ناتطبیقی است که با فرض صحیح بودن اعداد، از آرایه‌ای به طول بازهٔ اعداد ورودی، برای شمردن تعداد تکرار هر عدد استفاده می‌کند (به این آرایه، آرایه شمارش می گویند) به عنوان مثال اندیس i در آرایه شمارشی، تعداد تکرار عنصر i در آرایه ورودی را نشان می‌دهد. از اعداد داخل این آرایه برای قرار دادن عناصر آرایه وروذی در آرایه خروجی استفاده می‌شود.
این الگوریتم در سال ۱۹۵۴ توسط هارولد سوارد طراحی شد.

مقایسه

اگر کمینه آرایه ورودی صفر نبود، برای ساختن آرایه شمارشی باید اعضای آرایه ورودی را به نحوی شیفت دهیم که کوچکترین کلید آن، با اندیس اول آرایه شمارشی منطبق شود.
این مرتب سازی یک مرتب سازی پایدار، با پیچیدگی $O(n+k) \!$ است که n طول آرایه ورودی و k طول آرایه شمارش می‌باشد.
برای این که الگوریتم کارآمد باشد، لازم است k از مرتبهٔ n باشد تا پیچیدگی نهایی آن از $O(n) \!$ باشد.

انواع دیگر

یک گونه تغییریافتهٔ مرتب سازی شمارشی، Tally sort است که در آن آرایه ورودی شامل کلیدهای تکراری نیست یا انتظار ما این است که در طول مرتب سازی، تکرارهای هر کلید از آرایه حذف شوند. در این مرتب سازی آرایه شمارشی به صورت آرایه‌ای از بیت هاست و هر بیت در صورتی یک می‌شود که کلید آن در بین اعداد موجود باشد.

مرتب سازی لانه کبوتری

درباره

این الگوریتم که count sort نیز نامیده می‌شود (با counting sort اشتباه نشود) الگوریتمی است که برای مرتب سازی لیستی از عناصر که در آن تعداد عناصر (n) و تعداد کلیدهای ممکن (N) تقریبا با هم برابر باشد، بسیار مناسب است. مراحل انجام آن به این صورت است:

• 1- با گرفتن آرایه ورودی، آرایه کمکی ازلانه‌ها می‌سازیم، به طوری که هر لانه برای تعدادی از کلیدها در محدوده آرایه ورودی باشد.
• 2- با پیمایش آرایه اصلی، هر عنصر را در لانه‌ای که با کلید آن عنصر مشابهت دارد قرار می‌دهیم. بنابراین هر لانه شامل عناصری با کلیدهای یکسان می‌شود.
• 3- با گذر از لانه‌ها، عناصر خانه‌هایی که خالی نیستند را در آرایه اصلی کپی می‌کنیم.

به عنوان مثال فرض کنید می‌خواهیم عناصر زیر را بر حسب کلیدهایشان مرتب کنیم:

• (5 , “hello”)
• (3 , “pie”)
• (8 , “apple”)
• (5 , “king”)

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

• 3: (3 , “pie”)
• 4:
• 5: (5 , “hello”) , (5 , “king”)
• 6:
• 7:
• 8: (8 , “apple”)

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

• 3: 1
• 4: 0
• 5: 2
• 6: 0
• 7: 0
• 8: 1

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

مرتب سازی سطلی

درباره

عناصر درون سطل‌ها توزیع می‌شوند.

عناصر درون هر سطل مرتب می‌شوند.

Bucket sort یا Bin sort نوعی مرتب سازی ناتطبیقی است که آرایه را به تعدادی سطل تقسیم بندی می‌کند. سپس هر سطل به صورت مستقل مرتب می‌شود، یا با استفاده از الگوریتم‌های متفاوت مرتب سازی و یا با اعمال بازگشتی خود مرتب سازی سطلی.
صورتی از این مرتب سازی بر روی آرایه از اعداد در دو شکل زیر مشخص است.
این مرتب سازی در واقع از خانواده مرتب سازی مبنایی است و همچنین حالت تعمیم یافتهٔ مرتب سازی طبقه‌ای است.
شکل اصلی پیاده سازی آن به این صورت است که پس از سطل بندی، هر سطل را با مرتب سازی درجی مرتب می‌کنیم، می‌توان نشان داد که هر سطل تقریبا در زمان خطی مرتب می‌شود. اگرچه کارایی این الگوریتم به شیوه سطل بندی کردن بسیار وابسته است. اگر سطل بندی به گونه‌ای باشد که کلیدهای زیادی درون یک سطل قرار بگیرند، مرتب سازی به کندی صورت می‌گیرد.
اما یک پیاده سازی متداول و بهینه آن است که عناصر را پس از سطل بندی به همان ترتیب در آرایه اصلی قرار دهیم و سپس روی آرایه، مرتب سازی درجی را اعمال کنیم. به این خاطر که زمان اجرای این مرتب سازی وابسته به فاصله هر عنصر از مکان نهاییش می‌باشد و فاصله داده‌ها از مکان نهایی پس از سطل بندی کاهش یافته، تعداد مقایسه‌ها مقدار قابل توجهی کم می‌شود و بهره وری سلسله مراتب حافظه در مرتب سازی لیست افزایش می‌یابد.

انواع دیگر

Shuffle sort گونهٔ تغییریافته‌ای از مرتب سازی سطلی است که در آن ۱/۸ ابتدایی داده‌ها از آرایه جدا می‌شود و به طور جداگانه مرتب می‌شود. این عناصر n/8 سطل، برای ۷/۸ عنصر باقیماندهٔ آرایه ایجاد می‌کند. هر سطل مرتب می‌شود و سپس برای ساخت آرایه نهایی به هم الصاق می‌شود. این مرتب سازی به عنوان یک مرحله در J sort مورد استفاده قرار می‌گیرد.
مرتب سازی سطلی می‌تواند به عنوان نسخهٔ تغییریافتهٔ مرتب سازی شمارشی تلقی شود. اگر اندازهٔ هر سطل یک باشد، این دو مرتب سازی هم تراز هم قرار می‌گیرند. اندازهٔ متغیر سطل‌ها در مرتب سازی سطلی، به آن اجازه استفاده از حافظه $O(n) \!$ به جای $O(m) \!$ می‌دهد که m تعداد کلیدهای متمایز است. به عبارت دیگر، این مرتب سازی، رفتار مرتب سازی شمارشی را در بدترین حالت که $O(n+m) \!$ می‌باشد، بهبود می‌دهد.
مرتب سازی سطلی با دو سطل، در واقع پیاده سازی ای از مرتب سازی سریع است که محور همیشه میانهٔ داده‌ها انتخاب می‌شود. این شیوه برای داده‌هایی که به صورت یکنواخت پخش شده‌اند کارآمد است اما شیوه‌های دیگر انتخاب محور، مثل انتخاب تصادفی، مقاومت و پایداری بیشتری در برابر داده‌های مختلف ورودی، برای الگوریتم ایجاد می‌کند.
مرتب سازی ادغامی n – سویه نیز با تقسیم لیست ورودی به n زیرلیست و مرتب سازی آنها آغاز می‌شود. اگرچه در زیرلیست‌های ایجاد شده توسط مرتب سازی ادغامی، محدوده کلیدها با هم اشتراک پیدا می‌کند و این سبب می‌شود که ترکیب زیرلیست‌های آن به سادگی مرتب سازی سطلی نباشد و به جای آن از یک الگوریتم ادغام استفاده بشود، اما این هزینهٔ اضافی با آسان کردن مرحلهٔ تقسیم داده‌ها و همچنین هم اندازه کردن همهٔ زیرلیست‌ها جبران می‌شود و در نهایت حدبالای زمان مرتب سازی را (یعنی در بدترین حالت) بهبود می‌دهد.

پیاده سازی ها

• پیاده سازی مرتب سازی حبابی به ۲۶ زبان
• پیاده سازی مرتب سازی انتخابی به ۱۰ زبان
• پیاده سازی مرتب سازی درجی به ۱۷ زبان
• پیاده سازی مرتب سازی ادغامی به ۱۵ زبان
• پیاده سازی مرتب سازی هرمی به ۸ زبان
• پیاده سازی مرتب سازی سریع به ۳۳ زبان

منابع

• ویکی‌پدیای انگلیسی، الگوریتم‌های مرتب سازی
• ویکی‌پدیای انگلیسی، مرتب سازی حبابی
• ویکی‌پدیای انگلیسی، مرتب سازی انتخابی
• ویکی‌پدیای انگلیسی، مرتب سازی درجی
• ویکی‌پدیای انگلیسی، مرتب سازی ادغامی
• ویکی‌پدیای انگلیسی، مرتب سازی هرمی
• ویکی‌پدیای انگلیسی، مرتب سازی سریع
• ویکی‌پدیای انگلیسی، مرتب سازی لانه کبوتری
• ویکی‌پدیای انگلیسی، مرتب سازی سطلی
• ویکی‌پدیای انگلیسی، مرتب سازی شمارشی
• ویکی‌پدیای انگلیسی، مرتب سازی مبنایی

مطالعه بیشتر

• مرتب سازی خارجی
• شبکه‌های مرتب سازی
• الگوریتم‌های ترکیبی
• الگوریتم‌های جستجو
• الگوریتم‌های مرتب سازی ترتیبی و موازی
• دایره المعارف الگوریتم‌ها، داده ساختارها و مسائل
• انیمیشن‌های الگوریتم‌های مرتب سازی