اشرح فرز الفقاعة والإدراج والاختيار

Question

Accepted Answer

هذه ثلاث فرز مقارنة بسيطة **O(n²)**. إنها بطيئة على المدخلات الكبيرة لكن سهلة الفهم ومفيدة لتعليم آليات الفرز.

## كيف يعمل كل منها

- **فرز الفقاعة:** تبديل متكرر للأزواج المجاورة غير المرتبة؛ القيم الكبيرة "تطفو" إلى النهاية في كل تمرير.
- **فرز الاختيار:** العثور على الحد الأدنى من الجزء غير المرتب وتبديله في مكانه.
- **فرز الإدراج:** نمو بادئة مرتبة بإدراج كل عنصر جديد في مكانه الصحيح.

## مثال (فرز الإدراج)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## المقارنة

| الفرز | الأفضل | الأسوأ | مستقر | في المكان |
|------|--------|--------|--------|----------|
| الفقاعة | O(n) | O(n²) | نعم | نعم |
| الاختيار | O(n²) | O(n²) | لا | نعم |
| الإدراج | O(n) | O(n²) | نعم | نعم |

## متى يتم الاستخدام / المخاطر

فرز الإدراج سريع حقًا للمصفوفات **الصغيرة أو المرتبة جزئيًا** ويُستخدم داخل الفرز الهجين. تجنب جميع الأنواع الثلاثة على البيانات الكبيرة غير المرتبة — استخدم فرز O(n log n) بدلاً من ذلك.

## لماذا يهم

تبني هذه الفرز الحدس حول الثوابت والتبديلات والاستقرار قبل أن تتعامل مع الخوارزميات المتقدمة.

فرز الإدراج بشكل خاص يظهر داخل فرز الإنتاج (مثل Timsort) للمصفوفات الصغيرة جدًا.

معرفة السبب في أنها O(n²) تجعل الانتقال إلى فرز O(n log n) ذا معنى.

الفرز	الأفضل	الأسوأ	مستقر	في المكان
الفقاعة	O(n)	O(n²)	نعم	نعم
الاختيار	O(n²)	O(n²)	لا	نعم
الإدراج	O(n)	O(n²)	نعم	نعم