Sắp xếp mảng 2 chiều theo hình xoán ốc

[dieuyen]

Đề: Sắp xếp mảng 2 chiều theo hình xoán ốc( ko dùng mảng phụ)
Ai có thuật toán hay code thì cho em xin. Thanks

View more random threads:

• Tìm hiểu dữ liệu cấu trúc
• Lỗi Undefined symbol 'bool'
• Đếm số lượng các số nguyên tố khác nhau trong dãy
• Gán chuỗi trong c++ như thế nào?
• Giúp mình tính 2^n (2 mũ n) mà không cần dùng pow hoặc for với
• Mọi người làm giúp mình bài này với
• giúp mình hiểu thế nào là xài con trỏ thê nào là xài mảng trong bài tập này(mai nộp mất rồi)
• Đọc file.
• Bài tập Cấu trúc dữ liệu và giải thuật [Help Me]
• trình biên dịch làm sai kết quả???

[thedattm]

Đề: Sắp xếp mảng 2 chiều theo hình xoán ốc( ko dùng mảng phụ)
Ai có thuật toán hay code thì cho em xin. Thanks

Mình chỉ biết sắp xếp bằng cách dùng mảng phụ thôi, mà mình nghĩ bạn đăng như vậy có lẻ không cần đâu nhỉ. [IMG]images/smilies/thinking.gif[/IMG]

[nhatlinhit88]

Mình chỉ biết sắp xếp bằng cách dùng mảng phụ thôi, mà mình nghĩ bạn đăng như vậy có lẻ không cần đâu nhỉ. [IMG]images/smilies/thinking.gif[/IMG]

Bạn có thể thử ánh xạ chỉ số 1 chiều sang tọa độ 2 chiều [IMG]images/smilies/smile.png[/IMG]
Gợi ý: Hãy "cắt lớp" ma trận.

p/s: thực ra bước ánh xạ này cũng tốn kha khá chi phí (+sx) + non-locality > sx trên mảng phụ rồi đưa vào theo xoắn ốc.

[seoer]

void spiralSort(IntArr2d& a, size_t layer){    if (layer >= a.size()/2 || layer >= a[0].size()/2) return;    size_t i = layer, j = layer;    size_t min_i, min_j;    while (true) {        findMinIndex(a, i, j, layer, min_i, min_j);        exch(a, i, j, min_i, min_j);        cwIncrement(a, i, j, layer);        if (i == layer && j == layer) break; //avoid loop second time    }    spiralSort(a, ++layer);}

vd với mảng a

{ 5, 8, 3, 6,15},{20,17, 2, 9,14},{ 4,18,11, 7,12},{10, 1,16,19,13}

thì hàm cwIncrement có tác dụng tăng i, j xoắn ốc theo chiều kim đồng hồ, với layer cho trước

size_t layer = 0;size_t i = layer, j = layer;while (true) {    std::cout << a[i][j] << " ";    cwIncrement(a, i, j, layer);    if (i == layer && j == layer) break; //avoid loop second time}

nếu thay layer = 0 sẽ in ra kết quả 5 8 3 6 15 14 12 13 19 16 1 10 4 20
nếu thay layer = 1 thì sẽ ra kết quả 17 2 9 7 11 18
nếu thay layer = 1 và j = layer + 2 thì sẽ in ra 9 7 11 18
nếu thay layer = 0 và i = layer + 3 thì sẽ in ra 10 4 20

còn hàm findMinIndex thì sẽ tìm index min_i, min_j của phần tử nhỏ nhất trong mảng, tìm theo kiểu tìm trên đường viền xoắn ốc trước, rồi tìm bên trong đường viền (nếu có phần tử bên trong)
vd findMinIndex(a, 0, 0, 0, min_i, min_j) sẽ cho a[min_i][min_j] = 1
vd findMinIndex(a, 1, 1, 1, min_i, min_j) sẽ cho a[min_i][min_j] = 2
vd findMinIndex(a, 1, 3, 1, min_i, min_j) sẽ cho a[min_i][min_j] = 7
vd findMinIndex(a, 3, 0, 0, min_i, min_j) sẽ cho a[min_i][min_j] = 2

hàm exch thì hoán đổi giá trị của a[i][j] và a[min_i][min_j]


(sắp xếp theo selection sort)

[bacsiquaidi1]

cảm ơn mọi người, bài này em đã làm đc rồi ạ.