Quick Sort

الترتيب السريع Quick Sort

Quick Sort تختار عنصرًا محوريًا (pivot)، تقسّم المصفوفة لأصغر وأكبر منه، ثم تكرّر ذلك على كل قسم — الأسرع عمليًا بمتوسط الحالات رغم أسوأ حالة نظرية أبطأ.

بعكس Merge Sort، Quick Sort ترتّب بمكانها (in-place) بلا حاجة لذاكرة إضافية كبيرة — لهذا غالبًا أسرع عمليًا رغم تعقيدها النظري بأسوأ حالة O(n²) (يحدث نادرًا مع اختيار محور جيد، مثل عنصر عشوائي).

الصياغة

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)

📄 مثال

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([5, 2, 8, 1, 9]))

أهم النقاط

النقطة	الوظيفة
التعقيد الزمني	O(n log n) بمتوسط الحالة، O(n²) بأسوأ حالة (محور سيء متكرّر)
التعقيد المكاني	O(log n) لمكدّس الاستدعاءات التعاودية (أو O(n) بالتنفيذ الساذج أعلاه)
مستقرّة؟	لا (بالتطبيق القياسي بالمكان)

💡 نصائح عملية

اختيار محور عشوائي (بدل أول/آخر عنصر دائمًا) يقلّل احتمال الوقوع بأسوأ حالة O(n²) عمليًا بشكل كبير

⚠️ أخطاء شائعة

اختيار المحور دائمًا كأول أو آخر عنصر ببيانات شبه مرتّبة سلفًا — يسبب أسوأ حالة O(n²) بالضبط

🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.