אלגוריתם Quick Sort בשפת C


אלגוריתם Quick Sort הוא אלגוריתם מיון מבוסס על עקרון "חלק ו conquer" (Divide and Conquer). הוא פועל על ידי בחירת אלמנט פיבוט, מיון האלמנטים סביב הפיבוט, וחזרה על התהליך עבור תתי-החלקים של המערך.


מימוש אלגוריתם Quick Sort:


הנה דוגמה לקוד המיישמת את אלגוריתם Quick Sort בשפת C:


קוד:
c
#include <stdio.h>


// פונקציה להחלפת מקומות בין שני אלמנטים במערך
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}


// פונקציה לבחור פיבוט ולמיין את האלמנטים סביבו
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++; // מגדיל את האינדקס של האלמנט הקטן ביותר
            swap(&arr[i], &arr[j]); // מחליף את האלמנט הנוכחי עם האלמנט הקטן ביותר
        }
    }
    swap(&arr[i + 1], &arr[high]); // מחליף את הפיבוט עם האלמנט הקטן ביותר
    return (i + 1);
}


// פונקציה למיין את המערך בעזרת Quick Sort
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);
    }
}


// פונקציה להדפסת מערך
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);


    printf("Array before sorting:\n");
    printArray(arr, n);


    quickSort(arr, 0, n - 1);


    printf("Array after sorting:\n");
    printArray(arr, n);


    return 0;
}

הסבר על הקוד:


1. **פונקציה `swap`**:
- מחליפה בין שני אלמנטים במערך.


2. **פונקציה `partition`**:
- בוחרת את הפיבוט (האלמנט האחרון במערך הנוכחי) ומעבירה את האלמנטים הקטנים ממנו לצד אחד ואלמנטים הגדולים ממנו לצד השני.
- מחזירה את המיקום החדש של הפיבוט.


3. **פונקציה `quickSort`**:
- מקבלת את המערך ואת הגבולות התחתון והעליון למיון.
- קוראת לפונקציה `partition` כדי למיין את האלמנטים סביב הפיבוט ואז קוראת לפונקציה `quickSort` על החצאים שנוצרו.


4. **פונקציה `printArray`**:
- מדפיסה את האלמנטים של המערך.


5. **פונקציה `main`**:
- יוצרת מערך לדוגמה ומדפיסה אותו לפני ואחרי המיון.


סיכום:


אלגוריתם Quick Sort הוא אלגוריתם מיון יעיל ומפורסם עם מורכבות זמן ממוצעת של O(n log n). הוא מבצע מיון על ידי חלוקה של המערך סביב פיבוט ומיון החצאים שנוצרים. אלגוריתם זה מתאים במיוחד למערכים גדולים ומשתמש בזיכרון בצורה חסכונית.


אם יש לכם שאלות נוספות או אתם זקוקים לעזרה נוספת, אתם מוזמנים לשאול!