Sắp xếp Mảng 2-D của các hàng và các yếu tố cột của số nguyên được sắp xếp

Question

Tôi chỉ cần một chút trợ giúp ở đây. Tôi đang làm một bài tập mà tôi cần một hiệu quả Way Để sắp xếp 2-D số nguyên Mảng trong đó hàng và cột yếu tố được đã được sắp xếp tăng dần theo thứ tự. (Ưu tiên ngôn ngữ C/C++).

Input:

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

Output:

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

Thanks Trong Advance.

Answer 1

Dưới đây là gợi ý - giả sử đó là một mảng 2D C thông thường, sử dụng một chút typecasting, bạn sẽ có thể diễn giải nó dưới dạng mảng 1D.

Answer 2

Hợp nhất các cột (hoặc hàng) bằng cách sử dụng phương thức hợp nhất tương tự với một phương pháp được sử dụng trong sắp xếp hợp nhất.

Điều đó sẽ tận dụng lợi thế của thực tế là mỗi cột được sắp xếp theo chính nó.

Điều này sẽ đủ nhanh.

EDIT

Và có vẻ như rằng có một chức năng hợp nhất đã có trong thư viện chuẩn. http://en.cppreference.com/w/cpp/algorithm/merge

Answer 3

Tôi muốn sử dụng một số loại thuật toán tương tự như thuật toán "lấp đầy lũ" hoặc tìm đường dẫn như A *. Bắt đầu ở góc trên bên trái (giá trị 1), xuất nó và "mở rộng" ở bên phải và phía dưới - để thêm giá trị của chúng (2 và 5) vào danh sách. Cả hai giá trị này sẽ lớn hơn 1. Bây giờ, đầu ra giá trị nhỏ nhất từ ​​danh sách của bạn (giá trị 2) và "mở rộng" nó. Bạn sẽ nhận được 4 và 7 được thêm vào danh sách của bạn, đầu ra 4 và "mở rộng" nó, và như vậy. Lưu ý rằng bằng cách giữ danh sách được sắp xếp, bạn có thể xuất ra phần tử nhỏ nhất ngay lập tức và thậm chí có thể xuất nhiều "lần chạy" của các giá trị liên tiếp cùng một lúc (f.e. 10,11,12). Vì vậy, mã giả sẽ là:

// 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: Đây là triển khai C đang hoạt động.

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

Lưu ý nhận xét về độ dài danh sách. Tôi không chắc chắn lớn như thế nào trong danh sách có thể nhận được, nhưng tôi nghĩ COLS+ROWS nên đủ nhìn vào trường hợp xấu nhất này:

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

Nếu tất cả "border" yếu tố này là thấp hơn giá trị nhỏ nhất y, bạn sẽ nhận được một danh sách có đầy đủ các giá trị y trong quá trình, dài (ROWS - 1) + (COLS - 1) phần tử.

Nhìn vào những trường hợp xấu nhất như vậy, tôi đoán đây không phải là giải pháp hiệu quả nhất, nhưng tôi nghĩ đó là một giải pháp thanh lịch và súc tích.

Answer 4

lý do tại sao chúng tôi không xem xét câu hỏi này là "hợp nhất danh sách được sắp xếp N mỗi phần tử có phần tử k".

tạo tối thiểu phần tử k. đưa từng phần tử nhỏ nhất của danh sách được sắp xếp vào trong vùng tối thiểu đó. popping root của heap. bây giờ chèn phần tử tiếp theo của danh sách có phần tử là phần tử gốc. Bằng cách này, chúng tôi nhận được sự phức tạp của N * k log (k).

trong trường hợp trên nó sẽ là N^2log (N), trong đó N là số phần tử trong một hàng.