الإعلام الآلي — الخوارزميات: خوارزميات الفرز (الترتيب) المتقدمة — الثالثة ثانوي — المنهاج الجزائري

خوارزميات الفرز المتقدمة: الفرز السريع والدمج

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

أولا: خوارزمية الفرز السريع (Quick Sort)

مبدأها: اختيار عنصر محوري (pivot) وتقسيم المصفوفة حوله.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

التعقيد: O(n log n) في المتوسط، O(n²) في أسوأ حالة.

ثانيا: خوارزمية فرز الدمج (Merge Sort)

مبدأها: تقسيم المصفوفة إلى نصفين وفرز كل نصف ثم دمجهم.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

التعقيد: O(n log n) دائما.

تمارين

1. طبق خوارزمية الفرز السريع على المصفوفة [8, 3, 5, 1, 9, 2].
2. قارن بين التعقيد الزمني للفرز الفقاعي والفرز السريع.
3. لماذا يعتبر Merge Sort مستقرا (stable) بينما Quick Sort غير مستقر؟

للمزيد راجع خوارزمية الترتيب الفقاعي و خوارزمية البحث الثنائي.