אלגוריתם Merge sort בשפת C

[Tamir]

אלגוריתם מיון מיזוג (Merge Sort) בשפת C


אלגוריתם Merge Sort הוא אלגוריתם מיון מבוסס על עקרון "חלק ו conquering" (Divide and Conquer). האלגוריתם מבצע מיון על ידי חלוקת המערך לחצאים, מיון כל חצי בנפרד, ולבסוף מיזוג התוצאות הממויינות לתוך מערך אחד ממויין.


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


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



c
#include <stdio.h>
#include <stdlib.h>


// פונקציה למיזוג של שני חצאים של מערך
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;


// יצירת מערכים זמניים
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));


// העתקת נתונים למערכים זמניים
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];


// מיזוג החלקים בחזרה למערך המקורי
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}


// העתקת האלמנטים הנותרים אם ישנם
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}


// שחרור זיכרון
free(L);
free(R);
}


// פונקציה למיון מערך בעזרת Merge Sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;


// מיון חצי שמאלי
mergeSort(arr, l, m);


// מיון חצי ימני
mergeSort(arr, m + 1, r);


// מיזוג החצאים הממויינים
merge(arr, l, m, r);
}
}


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


int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);


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


mergeSort(arr, 0, n - 1);


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


return 0;
}



הסבר על הקוד:


1. **פונקציה `merge`**:
- הפונקציה מקבלת את המערך ואת האינדקסים של החלקים שצריך למזג.
- יוצרת שני מערכים זמניים, אחד לכל חצי.
- מעתיקה את הנתונים מהמערך הראשי למערכים הזמניים ומבצעת את המיזוג.
- מחזירה את התוצאה למערך המקורי.


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


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


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


סיכום:


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


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