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

از ویکی‌پدیا، دانشنامهٔ آزاد.

فهرست مندرجات

۱ الگوریتم‌های مرتب‌سازی(Sorting algorithms)
۲ طبقه‌بندی
۳ لیست الگوریتم‌های مرتب‌سازی
۴ پاورقی

[ویرایش] الگوریتم‌های مرتب‌سازی(Sorting algorithms)

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

از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد). مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های مختلف کمک می‌‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

[ویرایش] طبقه‌بندی

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

پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین) : با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n² است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی "در جا^[1]" هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(1) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
پایداری^[2] : الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

[ویرایش] لیست الگوریتم‌های مرتب‌سازی

در این جدول، n تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است. ستون‌های بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است.

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای‌	روش	توضیحات
مرتب سازی حبابی (Bubble sort)	(O(n	—	(O(n²	(O(1	بله	بله	جابجایی	Times are for best variant
Cocktail sort	(O(n	—	(O(n²	(O(1	بله	بله	جابجایی
Comb sort	(O(n log n	—	(O(n log n	(O(1	خیر	بله	جابجایی
Gnome sort	(O(n	—	(O(n²	(O(1	بله	بله	جابجایی
Selection sort	(O(n²	(O(n²	(O(n²	(O(1	خیر	بله	گزینشی
Insertion sort	(O(n	—	(O(n²	(O(1	بله	بله	درجی
Shell sort	(O(n log n	—	(O(n log²n	(O(1	خیر	بله	درجی	Times are for best variant
Binary tree sort	(O(n log n	—	(O(n log n	(O(1	بله	بله	درجی
Library sort	(O(n	(O(n log n	(O(n²	ε+1)n)	بله	بله	درجی
Merge sort	(O(n log n	—	(O(n log n	(O(n	بله	بله	Merging
In-place merge sort	(O(n log n	—	(O(n log n	(O(1	بله	بله	Merging	Times are for best variant
Heapsort	(O(n log n	—	(O(n log n	(O(1	خیر	بله	گزینشی
Smoothsort	(O(n	—	(O(n log n	(O(1	خیر	بله	گزینشی
Quicksort	(O(n log n	(O(n log n	(O(n²	(O(n	خیر	بله	Partitioning	Naive variants use (O(n space
Introsort	(O(n log n	(O(n log n	(O(n log n	(O(n	خیر	بله	Hybrid
Pigeonhole sort	(O(n+k	—	(O(n+k	(O(k	بله	خیر	Indexing
Bucket sort	(O(n	(O(n	(O(n²	(O(k	بله	خیر	Indexing
Counting sort	(O(n+k	—	(O(n+k	(O(n+k	بله	خیر	Indexing
Radix sort	(O(nk	—	(O(nk	(O(n	بله	خیر	Indexing
Patience sorting	(O(n	—	(O(n log n	(O(n	خیر	بله	درجی	تمام زیر دنباله‌های صعودی را با (O(n log (log(n پیدا می‌کند.

این جدول الگوریتم‌هایی را توضیح می‌دهد که به علت اجرای بسیار ضعیف و یا نیاز به سخت‌افزار خاص، کاربرد زیادی ندارند.

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای	توضیحات
Bogosort	(O(n	O(n × n!)	بدون حد	(O(1	خیر	بله
Stooge sort	(O(n^2.71	—	(O(n^2.71	(O(1	خیر	بله
Bead sort	(O(n	—	(O(n	—	N/A	خیر	به سخت‌افزار مخصوص نیاز دارد.
Pancake sorting	(O(n	—	(O(n	—	خیر	بله	به سخت‌افزار مخصوص نیاز دارد.
Sorting networks	(O(log n	—	(O(log n	—	بله	بله	Requires a custom circuit of size (O(log n