Sorting a 2d array based on second row-CodePudding

I have an array of numbers, a[n], and I want to sort it very fast, but I want to save the original positions. so I think I should use a 2D array a[2][n], so a[0][n] is for the initial positions and a[1][n] for the values. so I want to sort this array based on the second row. for example, my array is

a[2][5] = [{ 0, 1, 2, 3, 4 }, { 10, 30, 40, 20, 50 }];

and after sorting I want

a[2][5] = [{ 0, 3, 1, 2, 4 }, { 10, 20, 30, 40, 50 }];

I tried to change merge sort so that it sorts the first row based on second row (and also sort second row) but there is segmentation fault in line 14, here is my code

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

void merge(int arr[][201], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l   1;
    int n2 = r - m;

    /* create temp arrays */
    int L[2][n1], R[2][n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i  )
        L[1][i] = arr[1][l   i];
        L[0][i] = arr[0][l   i];
    for (j = 0; j < n2; j  )
        R[1][j] = arr[1][m   1   j];
        R[0][j] = arr[0][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[1][i] <= R[1][j]) {
            arr[1][k] = L[1][i];
            arr[0][k] = L[0][i];
            i  ;
        } else {
            arr[1][k] = R[1][j];
            arr[0][k] = R[0][j];
            j  ;
        }
        k  ;
    }

    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        arr[0][k] = L[0][i];
        arr[1][k] = L[1][i];
        i  ;
        k  ;
    }

    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        arr[1][k] = R[1][j];
        arr[0][k] = R[0][j];
        j  ;
        k  ;
    }
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[][201], 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);
    }
}

void get_array(int length, int array[]) {
    for (int i = 0; i < length; i  ) {
        scanf("%d", &array[i]);
    }
}

int main() {
    int  n;
    scanf("%d", &n);

    int packages[2][n];
    
    for (int i = 0; i < n; i  ) {
        packages[0][i]= i;
    }
    get_array(n, packages[1]);
    mergeSort(packages, 0, n);

    return 0;
}

I just want to solve this problem, I'm OK with using another function.

CodePudding user response：

The initialization loops for the L and R arrays is incorrect: you must use {} to group multiple statements as a block in C. Unlike Python, indentation does not determine structure:

for (i = 0; i < n1; i  ) {
    L[1][i] = arr[1][l   i];
    L[0][i] = arr[0][l   i];
}
for (j = 0; j < n2; j  ) {
    R[1][j] = arr[1][m   1   j];
    R[0][j] = arr[0][m   1   j];
}

Furthermore, your sorting function expects a 2D array with a fixed number of columns of 201, so you cannot pass it an array allocated in main() with a variable number of columns. You must either use a fixed array int packages[2][201]; or pass n to your mergeSort and merge functions explicitly and defined arr consistently.

You should pass n - 1 as the offset of the last element in the initial call to mergeSort(). This convention is error prone and confusing.

Note also that merge can be simplified: only the left part needs saving and a single loop is required.

Here is a modified version:

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

void merge(int n, int arr[][n], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l;

    /* create temp array */
    int L[2][n1];

    /* Copy data to temp array L[] */
    for (i = 0; i < n1; i  ) {
        L[1][i] = arr[1][l   i];
        L[0][i] = arr[0][l   i];
    }

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = m; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1) {
        if (j == r || L[1][i] <= arr[1][j]) {
            arr[1][k] = L[1][i];
            arr[0][k] = L[0][i];
            i  ;
        } else {
            arr[1][k] = arr[1][j];
            arr[0][k] = arr[0][j];
            j  ;
        }
        k  ;
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int n, int arr[][n], int l, int r) {
    if (r - l > 1) {
        // 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(n, arr, l, m);
        mergeSort(n, arr, m, r);
        merge(n, arr, l, m, r);
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);

    int packages[2][n];

    for (int i = 0; i < n; i  ) {
        packages[0][i] = i;
        packages[1][i] = 0;
        scanf("%d", &packages[1][i]);
    }
    mergeSort(n, packages, 0, n);

    printf("a[2][%d] = [{ ", n);
    for (int i = 0; i < n; i  ) {
        printf("%d, ", packages[0][i]);
    }
    printf("}, { ");
    for (int i = 0; i < n; i  ) {
        printf("%d, ", packages[1][i]);
    }
    printf("}];\n");
    return 0;
}

Output:

5 10 30 40 20 50
a[2][5] = [{ 0, 3, 1, 2, 4, }, { 10, 20, 30, 40, 50, }];