Ordinamento di una matrice 2-D di intero di cui righe ed elementi di colonna sono ordinati

Question

Ho solo bisogno di un piccolo aiuto qui. Sto facendo un incarico in cui ho bisogno di un efficiente modo Per ordinare un 2-D intero array di cui elementi di riga e colonna sono già ordinati in ordine crescente. (Preferibile linguaggio C/C++).

ingresso:

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

uscita:

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

Grazie in anticipo.

Answer 1

Ecco un suggerimento: supponendo che si tratti di un normale array 2D C, utilizzando un po 'di typecasting, dovresti essere in grado di interpretarlo come un array 1D.

Answer 2

Unire le colonne (o le righe) utilizzando un metodo di fusione simile a quello utilizzato nell'ordinamento di unione.

Ciò trarrebbe vantaggio dal fatto che ogni colonna è ordinata da sola.

Questo dovrebbe essere abbastanza veloce.

EDIT

e sembra che ci sia una funzione di fusione già nella libreria standard. http://en.cppreference.com/w/cpp/algorithm/merge

Answer 3

Io userei un qualche tipo di algoritmo simile a "flood fill" o algoritmi di ricerca del percorso come A *. Inizia nell'angolo in alto a sinistra (valore 1), emettilo e "espandi" a destra e in fondo, quindi aggiungi i loro valori (2 e 5) a un elenco. Entrambi saranno più grandi di 1. Ora emetti il ​​valore più piccolo dalla tua lista (valore 2) e "espandi" anch'esso. Otterrai 4 e 7 aggiunti alla tua lista, l'output 4 e "espandi", e così via.

Si noti che mantenendo la lista ordinata, è possibile emettere immediatamente l'elemento più piccolo e potrebbe anche essere in grado di generare più "analisi" di valori consecutivi contemporaneamente (per esempio 10,11,12). Quindi lo pseudocodice sarebbe:

// 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 

MODIFICA: questa è un'implementazione C funzionante.

#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; 
} 

Nota il commento relativo alla lunghezza dell'elenco. Non sono sicuro di quanto grande sia l'elenco può ottenere, ma penso che dovrebbe essere abbastanza COLS+ROWS guardando questo caso peggiore:

1 3 5 7 9 .. 
2 y y y y 
4 y x x x 
6 y x x x 
8 y x x x 
. 
. 

Se tutti gli elementi di "frontiera" sono inferiori al valore minimo y, si otterrà un elenco completo dei valori y nel processo, che è lungo (ROWS - 1) + (COLS - 1) elementi.

Guardando a questi casi peggiori, credo che questa non sia la soluzione più efficiente, ma penso che sia comunque elegante e concisa.

Answer 4

perché non consideriamo questa domanda come "unire N elenco ordinato ha ciascuno k elementi".

creazione di un min-heap di k elemento. mettendo ogni minimo elemento della lista ordinata in quel min-heap. radice popping dell'heap. ora inserisci il prossimo elemento di lista il cui elemento era la radice. In questo modo otteniamo la complessità di N * k log (k).

nel caso precedente sarà N^2log (N), dove N è il numero di elementi in una riga.