فهم الفرز السريع (Quick Sort) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
الفرز السريع هو خوارزمية فعّالة تعتمد على تقسيم المصفوفة إلى أجزاء لتتمكن من فرزها. يقوم الفرز السريع باختيار عنصر محوري (pivot) ومن ثم تقسيم العناصر إلى مجموعتين، واحدة تحتوي على العناصر الأصغر من المحور والأخرى على العناصر الأكبر. يتم تكرار هذه العملية بشكل عودي لفرز المصفوفة بالكامل.

حالة استخدام:
تخيل أنك بحاجة إلى فرز مجموعة من الأرقام الكبيرة بشكل سريع. الفرز السريع مناسب جداً لهذه الحالة بسبب كفاءته العالية، خاصةً مع المصفوفات الكبيرة.

المدخلات والمخرجات:

• المدخلات: مصفوفة غير مرتبة من العناصر (مثل الأعداد الصحيحة).
• المخرجات: مصفوفة مرتبة تصاعدياً.

2. شرح تعليمي للحل

مفهوم الفرز السريع:

• اختيار المحور: اختر عنصرًا من المصفوفة ليكون المحور.
• التقسيم: قسم المصفوفة إلى جزئين، أحدهما يحتوي على العناصر الأصغر من المحور والآخر يحتوي على العناصر الأكبر.
• الفرز العودي: كرر العملية على الجزئين بشكل عودي.

تتضمن العملية تحريك العناصر بحيث يتم وضع جميع العناصر الأصغر من المحور إلى يساره، وجميع العناصر الأكبر إلى يمينه.

تعقيد الوقت:

• أفضل حالة: O(n log n) عندما يتم تقسيم المصفوفة بشكل متساوٍ في كل مرة.
• أسوأ حالة: O(n^2) عندما تكون المصفوفة مرتبة بالفعل أو جميع العناصر متساوية.

تعقيد المساحة:

• O(log n) بسبب المكدس الناتج عن الاستدعاءات العودية.

3. الحل في Python

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less_than_pivot = [x for x in arr[1:] if x <= pivot]
        greater_than_pivot = [x for x in arr[1:] if x > pivot]
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

# استخدام المثال
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("المصفوفة المرتبة هي:", sorted_arr)

4. الحل في Java

public class QuickSort {

    // دالة التقسيم
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    // دالة الفرز السريع
    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    // دالة القيادة لاختبار ما سبق
    public static void main(String args[]) {
        int arr[] = {10, 7, 8, 9, 1, 5};
        int n = arr.length;

        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n - 1);

        System.out.println("المصفوفة المرتبة:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

5. الحل في C

#include <stdio.h>

// دالة التقسيم
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

// دالة الفرز السريع
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// دالة القيادة لاختبار ما سبق
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    
    printf("المصفوفة المرتبة:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}