Saiyan - 4 months ago 129
Java Question

Sort 2D array using insertion sort

I want to sort a 2D array of integers by a certain column using insertion sort. The following code works for 1D array.

``````private static void InsertionSort(int[] a, int n) {

int key, j;
for (int i = 1; i < n; i++){
key = a[i];
j = i - 1;
while ((j >= 0) && (a[j] > key)){
a[j+1] = a[j];
j = j - 1;
}
a[j+1] = key;
}
}
``````

For 2D array, I specify an integer c for the column by which to sort the array. For example, if I sort by the first column,

``````{4, 1, 3},
{6, 0, 2},
{5, 9, 8}
``````

becomes

``````{4, 1, 3},
{5, 9, 8},
{6, 0, 2}
``````

This is what I got so far for sorting a 2D array by a specified column

``````private static void InsertionSort(int[][] a, int n, int c) {

in key, j;
for (int i = 1; i < n; i++){
key = a[i][c];
j = i - 1;
while ((j >= 0) && (a[j][c] > key)){
a[j+1][c] = a[j][c];
j = j - 1;
}
a[j+1][c] = key;
}
}
``````

but the result for sorting by the first column is

``````{4, 1, 3}
{5, 0, 2}
{6, 9, 8}
``````

It sorts the elements of the first column without keeping them together with their respective rows. How can I solve this?

You need to swap data row, not just the data element.

``````private static void sort(int[][] a, int n, int c) {
int key, j;
for (int i = 1; i < n; i++){
key = a[i][c];
int[] keyRow = a[i];
j = i - 1;
while ((j >= 0) && (a[j][c] > key)){
//a[j+1][c] = a[j][c];
a[j+1] = a[j];
j = j - 1;
}
//a[j+1][c] = key;
a[j+1] = keyRow;
}
}
``````
Source (Stackoverflow)