تعتمد كل من QuickSort وMergeSort على استراتيجية «فرّق تسد» لترتيب البيانات بكفاءة متوسطة O(n log n)، بينما يعمل البحث الثنائي (Binary Search) على تقليص نطاق البحث للنصف في كل خطوة ليصل إلى الهدف بزمن O(log n) بشرط أن تكون البيانات مرتبة مسبقاً.
آلية عمل كل خوارزمية ونقاط قوتها
رغم تشابه الفلسفة التقسيمية بين هذه الخوارزميات، فإن سلوكها في الذاكرة واستقرارها مع القيم المتطابقة يصنع فارقاً جوهرياً في الأنظمة الواقعية:
قد يعجبك ايضا
- الترتيب السريع (QuickSort): يختار عنصراً محورياً (Pivot) ويقسم العناصر حوله أصغر وأكبر، ويمتاز بأنه يرتب البيانات في مكانها (In-place) مما يوفر الذاكرة، لكنه قد يتدهور إلى O(n²) إذا أسيء اختيار المحور.
- الترتيب بالدمج (MergeSort): يقسم المصفوفة إلى نصفين حتى تصل لعنصر واحد ثم يدمجها مرتبة؛ يضمن أداءً ثابتاً O(n log n) في أسوأ الأحوال ويحافظ على ترتيب العناصر المتساوية (Stable)، لكنه يستهلك ذاكرة إضافية O(n).
- البحث الثنائي (Binary Search): يقارن القيمة المطلوبة بمنتصف المصفوفة المرتبة ويستبعد النصف غير المحتمل في كل دورة.
جدول مقارنة الخصائص والأداء
الخوارزميةمتوسط الزمنأسوأ حالةالذاكرة الإضافيةالاستقرار (Stability)QuickSortO(n log n)O(n²)O(log n) للمكدسغير مستقرة غالباًMergeSortO(n log n)O(n log n)O(n)مستقرة (Stable)Binary SearchO(log n)O(log n)O(1) تكرارياًلا ينطبق (بحث)
تطبيق البحث الثنائي بلغة بايثون
def binary_search(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # تجنب تجاوز الأعداد الصحيحة
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
تجمع لغة بايثون وجافا في دوال الترتيب المدمجة بين MergeSort وInsertion Sort عبر خوارزمية Timsort للاستفادة من استقرار الدمج وسرعة الترتيب الموضعي.
أسئلة شائعة
- السؤال: لماذا تفضل بعض قواعد البيانات MergeSort على QuickSort؟ الإجابة: لأن MergeSort يعمل بكفاءة عالية عند ترتيب ملفات ضخمة لا تتسع لها الذاكرة العشوائية (External Sorting).
- السؤال: هل يمكن استخدام Binary Search على قائمة مرتبطة؟ الإجابة: نظرياً ممكن، لكنه يفقد كفاءته لأن الوصول لمنتصف القائمة المرتبطة يستغرق O(n) وليس O(1).
- السؤال: كيف نتجنب أسوأ حالة في QuickSort؟ الإجابة: عبر اختيار العنصر المحوري عشوائياً أو استخدام وسيط الثلاثة (Median-of-Three).
التعليقات (0)
أضف تعليقك