الگوریتم‌های مرتب‌سازی: ۵ روش برتر و زمان استفاده از آنها

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

• 📊 دسته‌بندی الگوریتم‌های مرتب‌سازی

  1. مرتب‌سازی مبتنی بر مقایسه (Comparison-Based Sorting)

• الزام: مقایسه عناصر با یکدیگر (a > b).

• محدودیت نظری: بهترین حالت ممکن O(n log n) است.

• 2. مرتب‌سازی خطی (Non-Comparison Sorting)

• الزام: بدون مقایسه مستقیم (مثلاً با استفاده از کلیدهای عددی).

• مزیت: می‌تواند در O(n) اجرا شود!

• ---

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

  الگوریتم	بهترین حالت	حالت متوسط	بدترین حالت	حافظه مصرفی	پایدار؟
  Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
  Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
  Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌
  Tim Sort	O(n)	O(n log n)	O(n log n)	O(n)	✅
  Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(n + k)	✅

  (k = محدوده اعداد)

  ---

  📌 تحلیل بهترین الگوریتم‌ها

  1. Merge Sort (مرتب‌سازی ادغامی)

  ✅ مزایا:

• همیشه O(n log n) — قابل اعتماد برای داده‌های حجیم.

• پایدار (ترتیب عناصر مساوی حفظ می‌شود).

• ❌ معایب:

• نیاز به حافظه اضافی (O(n)) دارد.

• 💡 کاربرد:

• مرتب‌سازی لیست‌های پیوندی.

• در کتابخانه‌های استاندارد (مثل Collections.sort() در جاوا).

• ---

  2. Quick Sort (مرتب‌سازی سریع)

  ✅ مزایا:

• سریع‌ترین در عمل (به‌دلیل تأثیر کم ثابت‌های پنهان).

• حافظه کم (O(log n)) برای پشته بازگشتی.

• ❌ معایب:

• O(n²) در بدترین حالت (اگر محور انتخاب بدی شود).

• ناپایدار.

• 💡 کاربرد:

• پیش‌فرض در qsort() سی و Arrays.sort() برای نوع داده اولیه.

• ---

  3. Tim Sort (ترکیب Insertion + Merge Sort)

  ✅ مزایا:

• بهینه برای داده‌های تقریباً مرتب‌شده (O(n) در بهترین حالت).

• پایدار و با حافظه منطقی.

• 💡 کاربرد:

• زبان پایتون (list.sort() و sorted()).

• اندروید و جاوا (برای شیءها).

• ---

  4. Counting Sort (مرتب‌سازی شمارشی)

  ✅ مزایا:

• O(n + k) — فوق‌العاده سریع اگر k (محدوده اعداد) کوچک باشد.

• ❌ معایب:

• فقط برای اعداد صحیح کاربرد دارد.

• 💡 کاربرد:

• تحلیل داده‌های با محدوده مشخص (مثل نمرات دانشجویان 0-20).

• ---

  💻 پیاده‌سازی نمونه در پایتون

  
  # Quick Sort  
  def quick_sort(arr):  
      if len(arr) <= 1:  
          return arr  
      pivot = arr[len(arr) // 2]  
      left = [x for x in arr if x < pivot]  
      middle = [x for x in arr if x == pivot]  
      right = [x for x in arr if x > pivot]  
      return quick_sort(left) + middle + quick_sort(right)  
  
  print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # [1, 1, 2, 3, 6, 8, 10]
  
  

  ---

  🚀 نتیجه‌گیری: علم مرتب‌سازی در یک نگاه

• برای مصارف عمومی: Tim Sort یا Quick Sort انتخاب‌های بهینه‌اند.

• اگر پایداری مهم است: Merge Sort گزینه‌ای عالی است.

• داده‌های خاص: الگوریتم‌های خطی مثل Counting Sort معجزه می‌کنند!

• ---

  🎯 کدام الگوریتم بهتر است؟

  سناریو	بهترین انتخاب
  داده‌های عمومی	Quick Sort یا Tim Sort
  نیاز به پایداری	Merge Sort یا Tim Sort
  حافظه محدود	Heap Sort
  اعداد در محدوده کوچک	Counting Sort
  داده‌های تقریباً مرتب‌شده	Insertion Sort یا Tim Sort