الگوریتمهای مرتبسازی
مرتبسازی (Sorting) یکی از مسائل بنیادی در علوم کامپیوتر است که در بسیاری از برنامهها و ساختارهای داده بهعنوان زیرروال به کار میرود. هدف اصلی مرتبسازی، قرار دادن دادهها بر اساس یک معیار مشخص (مانند صعودی یا نزولی بودن) است.
الگوریتمهای مرتبسازی به سه گروه عمده تقسیم میشوند: ساده و آموزشی، پیشرفته و کارآمد و خاص و بهینهشده.
🔹 ۱. الگوریتمهای ساده و آموزشی
مرتبسازی حبابی (Bubble Sort)
ایده: عناصر مجاور با هم مقایسه و در صورت نیاز جابهجا میشوند؛ این روند آنقدر تکرار میشود تا بزرگترین عنصر به انتهای لیست "حباب" کند.
ویژگیها: ساده و برای آموزش مفید است، اما در عمل بسیار کند.
- بهترین حالت (لیست مرتب): O(n)
- میانگین: O(n²)
- بدترین حالت: O(n²)
- حافظه کمکی: O(1)
مرتبسازی انتخابی (Selection Sort)
ایده: در هر مرحله کوچکترین عنصر پیدا شده و در جایگاه درست خود قرار میگیرد.
ویژگیها: تعداد جابهجاییها کم است ولی تعداد مقایسهها زیاد میشود.
- بهترین، میانگین و بدترین حالت: O(n²)
- حافظه کمکی: O(1)
مرتبسازی درج (Insertion Sort)
ایده: هر عنصر در لیست به موقعیت مناسب خود در قسمت مرتبشده وارد میشود.
ویژگیها: برای لیستهای کوچک یا تقریباً مرتب بسیار مناسب است.
- بهترین حالت (لیست مرتب): O(n)
- میانگین: O(n²)
- بدترین حالت: O(n²)
- حافظه کمکی: O(1)
🔹 ۲. الگوریتمهای پیشرفته و کارآمد
مرتبسازی سریع (Quick Sort)
ایده: یک محور (Pivot) انتخاب شده و دادهها به دو بخش کوچکتر و بزرگتر از محور تقسیم میشوند؛ این فرآیند بازگشتی ادامه مییابد.
ویژگیها: یکی از سریعترین الگوریتمها در عمل است، اما در حالت بد ممکن است کند شود.
- بهترین حالت: O(n log n)
- میانگین: O(n log n)
- بدترین حالت: O(n²)
- حافظه کمکی: O(log n)
مرتبسازی ادغامی (Merge Sort)
ایده: لیست به بخشهای کوچکتر تقسیم میشود و سپس بخشها بهصورت مرتب با هم ادغام میشوند.
ویژگیها: پایدار (Stable) و برای دادههای حجیم و ساختارهای پیوندی بسیار مناسب.
- بهترین، میانگین و بدترین حالت: O(n log n)
- حافظه کمکی: O(n)
مرتبسازی پشتهای (Heap Sort)
ایده: ابتدا دادهها در یک Heap ذخیره شده و سپس بزرگترین یا کوچکترین عنصر یکییکی استخراج و در لیست قرار داده میشود.
ویژگیها: غیرپایدار، ولی نیاز به حافظه اضافی ندارد.
- بهترین، میانگین و بدترین حالت: O(n log n)
- حافظه کمکی: O(1)
🔹 ۳. الگوریتمهای خاص و بهینهشده
مرتبسازی شمارشی (Counting Sort)
ایده: با شمارش تعداد تکرار هر مقدار و استفاده از آن برای جایگذاری عناصر عمل میکند.
ویژگیها: فقط برای دادههای عددی با دامنه محدود کاربرد دارد.
- بهترین، میانگین و بدترین حالت: O(n + k)
- حافظه کمکی: O(n + k)
مرتبسازی پایهای (Radix Sort)
ایده: مرتبسازی بر اساس رقمها (مثلاً از کم ارزشترین رقم تا پر ارزشترین).
ویژگیها: مناسب برای مرتبسازی اعداد صحیح بزرگ در زمان خطی تقریبی.
- پیچیدگی زمانی: O(d × (n + k))
- d = تعداد رقمها
- k = دامنهی هر رقم
- حافظه کمکی: O(n + k)
مرتبسازی سطلی (Bucket Sort)
ایده: دادهها به چندین "سطل" تقسیم میشوند و هر سطل جداگانه مرتب میگردد (مثلاً با Insertion Sort).
ویژگیها: مناسب برای دادههای یکنواخت و پیوسته.
- بهترین حالت: O(n + k)
- میانگین: O(n + k)
- بدترین حالت: O(n²)
- حافظه کمکی: O(n + k)
✅ در مجموع:
- الگوریتمهای ساده برای آموزش و دادههای کوچک مناسباند.
- الگوریتمهای پیشرفته مانند Quick Sort و Merge Sort برای دادههای بزرگ کارآمدترند.
- الگوریتمهای خاص مانند Counting و Radix Sort، در شرایط خاص بهترین عملکرد را دارند.
مقایسه پیچیدگی زمانی
| الگوریتم | بهترین حالت | میانگین | بدترین حالت | حافظه کمکی |
|---|---|---|---|---|
| مرتبسازی حبابی | O(n) | O(n²) | O(n²) | O(1) |
| مرتبسازی انتخابی | O(n²) | O(n²) | O(n²) | O(1) |
| مرتبسازی درجی | O(n) | O(n²) | O(n²) | O(1) |
| مرتبسازی سریع | O(n log n) | O(n log n) | O(n²) | O(log n) |
| مرتبسازی ادغامی | O(n log n) | O(n log n) | O(n log n) | O(n) |
| مرتبسازی پشتهای | O(n log n) | O(n log n) | O(n log n) | O(1) |
| مرتبسازی شمارشی | O(n + k) | O(n + k) | ||
| مرتبسازی رادیکس | O(d × (n + k)) | O(n + k) | ||
| مرتبسازی سطلی | O(n + k) | O(n + k) | O(n²) | O(n + k) |