Sort a 2-dimensional array of integers whose rows and column elements are sorted

Question

I just need a little help here. I am doing the job where I need an Effective Path Sorting a two-dimensional integer array from which the row and column elements are already sorted in ascending order. (Preferred C / C ++ language).

Input:

1 5 10 15 20 2 7 12 17 22 4 9 18 25 28 11 14 21 26 31 

Exit:

 1 2 4 5 7 9 10 11 12 14 15 17 18 20 21 22 25 26 28 31 

Thanks in advance.

Answer 1

Merge columns (or rows) using a merge method similar to the method used in merge sort.

This will help exploit the fact that each column is sorted on its own.

It should be fast enough.

EDIT

And it looks like there is a merge function in the standard library. http://en.cppreference.com/w/cpp/algorithm/merge

Answer 2

I would use some sort of fill-like algorithm or path-finding algorithms like A *. Start in the upper left corner (value 1), output it and "expand" to the right and bottom - add their values ​​(2 and 5) to the list. Both of them will be greater than 1. Now print the smallest value from your list (value 2) and expand it. You will get 4 and 7 added to your list, pin 4 and “expand” it, etc.

Note that while maintaining the sorted list, you can instantly display the smallest element and even display several “runs” of consecutive values ​​at once (for example, 10,11,12). Thus, the pseudo code will be:

 // array a[y][x] // list L - ordered insertion, additionally stores matrix indices of values add a[0][0] to L loop until L is empty output first element of L remove first element of L and add its right and bottom neighbors (if any) to L loop end 

EDIT: Here's a working implementation of C.

 #include <stdio.h> #include <stdlib.h> #define COLS 5 #define ROWS 4 int matrix[ROWS][COLS] = { 1, 5, 10, 15, 20, 2, 7, 12, 17, 22, 4, 9, 18, 25, 28, 11, 14, 21, 26, 31 }; struct entry { int value; int x, y; }; entry list[ROWS+COLS]; // Not sure how big the list can get, but this should be enough int list_len = 0; void set_list_entry(int index, int value, int x, int y) { list[index].value = value; list[index].x = x; list[index].y = y; } void add_to_list(int x, int y) { int val = matrix[y][x]; int i, pos = list_len; for (i = 0; i < list_len; i++) { if (list[i].value == val) return; // Don't add value that is on the list already if (list[i].value > val) { pos = i; break; } } // Shift the elements after pos for (i = list_len + 1; i > pos; i--) { set_list_entry(i, list[i - 1].value, list[i - 1].x, list[i - 1].y); } // Insert new entry set_list_entry(pos, val, x, y); list_len++; } int main() { int iteration = 0; add_to_list(0,0); do { // output first element of list printf("%i ", list[0].value); iteration++; if ((iteration % COLS) == 0) printf("\n"); // add neighbors of first element of list to the list if (list[0].x < (COLS - 1)) add_to_list(list[0].x + 1, list[0].y); if (list[0].y < (ROWS - 1)) add_to_list(list[0].x, list[0].y + 1); // remove first element of list for (int i = 0; i < list_len; i++) { set_list_entry(i, list[i + 1].value, list[i + 1].x, list[i + 1].y); } list_len--; } while (list_len > 0); return 0; } 

Pay attention to the comment on the length of the list. I'm not sure how big the list can get, but I think COLS+ROWS should be enough to look at this worst case:

 1 3 5 7 9 .. 2 yyyy 4 yxxx 6 yxxx 8 yxxx . . 

If all border elements are less than the smallest y value, you will get a list full of y values ​​in the process, which lasts (ROWS - 1) + (COLS - 1) .

Looking at such worst cases, I think this is not the most effective solution, but I think it is elegant and concise, nonetheless.

Answer 3

why we do not consider this question as "merging N sorted list that has k elements".

creating a minimal heap of element k. putting every smallest item in a sorted list into this mini-heap. popping the root of the heap. now insert the next list item whose element was the root. Thus, we get the complexity N * k log (k).

in the following case, it will be N ^ 2log (N), where N is the number of elements in one line.

Answer 4

Here's a hint - assuming a regular 2D C array, using a bit of machine translation, you should understand it as a 1D array.