ביצוע "מיון מיזוג" על מערך דו ממדי

Merge Sort על מערך דו ממדי

"Merge Sort" הוא אחד מהאלגוריתמים המפורסמים למיון מערכים.
תוכלו לקרוא עליו בהרחבה באתר של GeeksforGeeks.

נדגים עיקרון חשוב בעניין מערכים דו-ממדיים:
"מערך דו ממדי מתנהג ונשמר בזיכרון בדיוק כמו מערך חד ממדי."


לדוגמה, המערך:
[15],[22],[33]
[20],[80],[17]

נשמר בזיכרון כך:
[20],[80],[17],[15],[22],[33]

למעשה אם מערך חד ממדי לא שונה מ"מצביע", אז מערך דו ממדי לא שונה מ"מצביע למצביע".





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

הקוד:
(הקוד זמין גם כאן)

// https://www.geeksforgeeks.org/merge-sort/ 
/* C program for Merge Sort */
/* C The same function for 2D array */
 
#include<stdlib.h>
#include<stdio.h>
 
 #define HEIGHT   2
 #define WIDTH    4
 
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
 
    /* create temp arrays */
 int *L = (int *)malloc(sizeof(int) * n1);
 int *R = (int *)malloc(sizeof(int) * n2);
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
 
 free(L);
 free(R);
}
 
/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
        merge(arr, l, m, r);
    }
}
 
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
 
/* Function to print an 2D array */
void print2DArray(int A[HEIGHT][WIDTH])
{
    int i, j;
 for (i=0; i < HEIGHT; i++)
 {
  for (j=0; j < WIDTH; j++)
  {
   printf("%-5d ", A[i][j]);
  }
  printf("\n");
 }
    printf("\n");
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
 int arr2D[HEIGHT][WIDTH] = {
  { -3  , 34 , 5   , 90 },
  { -40 , 17 , 100 , 0  },
 };
 int arr_size = 0, arr2D_size = 0;
 
    arr_size = sizeof(arr)/sizeof(arr[0]);
 printf("arr_size:  %d\n\n", arr_size);
 
    printf("Given 1D array is \n");
    printArray(arr, arr_size);
 
    mergeSort(arr, 0, arr_size - 1);
 
    printf("\nSorted 1D array is \n");
    printArray(arr, arr_size);
 
 /// ******** ///
 printf("\n\n ..... \n\n\n");
 
 arr2D_size = HEIGHT * WIDTH;
 printf("arr2D_size: %d\n\n", arr2D_size);
 printf("Given 2D array is \n");
    print2DArray(arr2D);
 
    mergeSort(*arr2D, 0, arr2D_size - 1);
 
    printf("\nSorted 2D array is \n");
    print2DArray(arr2D);
}

הערה:
התחביר ;[int L[n1], R[n2 שפורסם באתר של GeeksforGeeks ליצירת המערכים L ו-R, השתמש במשתנים רגילים לקביעת גודל של מערך ולכן לא היה חוקי בשפת C (ולא ברור למה GeeksforGeeks השתמשו בו).
משום כך שיניתי את אופן יצירת המערכים להקצאה דינמית פשוטה.
עובדה זו לא משנה את תפקוד הפונקציה mergeSort או את הנקודה שרציתי להעביר.




בהצלחה!