二次元配列（正方行列）の斜め方向のソート

N×Nの正方行列を斜め方向に昇順で並び替えるプログラムを作成したいです。
例えば
１　３　５
４　６　１
５　７　４
という正方行列があった時
１　１　５
４　４　３
５　７　６
というように右下がり対角線方向に向かって昇順に並び替えるプログラムを作成したいです

発生している問題・エラーメッセージ

実行結果
--------------------------------------
./a.out

正方行列の列の数を入力してください。
3
3×3行列A(i,j)の要素を入力してください。
A( 1,  1) = 1
A( 1,  2) = 5
A( 1,  3) = 3
A( 2,  1) = 4
A( 2,  2) = 6
A( 2,  3) = 2
A( 3,  1) = 4
A( 3,  2) = 8
A( 3,  3) = 2
before sort:
   1   5   3
   4   6   2
   4   8   2
ans
   0   0   3
   5   6   2
   6   4   2
-----------------------------

このようにソート前の配列を出力するところまではうまくいってるのですがそのあとの並び替えた後の配列を出力するときに
よくわからない値が出てきてしまいます。おそらく斜め方向にソートする部分が間違っていると思いますが自分では解決できませんでした。

該当のソースコード

C
1#include <stdio.h>
2
3#define min 0
4#define max 100
5void Bsort(int data[], int size){//バブルソート
6	int i, j,tmp;
7    for(i=0;i<size;i++){
8        for(j=i+1;j<size;j++){
9            if(data[i]<data[j]){
10                tmp=data[i];
11                data[i]=data[j];
12                data[j]=tmp;
13            }
14        }
15    }
16}
17void printArray(int n,int a[n][n]){//配列を出力する関数
18    int i,j;
19    for(i=0;i<n;i++){
20        for(j=0;j<n;j++)printf("%4d",a[i][j]); 
21        printf("\n");
22    }
23}
24
25int input(int mi, int ma){//値をインプットする関数
26    int result;
27    while(1){
28        scanf("%d",&result);
29        if(mi<=result&&result<=ma) break;
30        printf("入力された値は無効です\n");
31    }
32    return result;
33}
34
35int main (void){
36    int i,j,n,m;
37    printf("正方行列の列の数を入力してください。\n");
38    n=input(min,max);
39    int before[n][n],ans[n][n];
40    
41    printf("%d×%d行列A(i,j)の要素を入力してください。\n",n,n);
42    for(int i=0; i<n; i++){
43        for(int j=0; j<n; j++){
44            printf("A(%2d, %2d) = ",i+1,j+1);
45            scanf("%d",&before[i][j]);
46        }
47    }
48    printf("before sort:\n");//ソート前の行列を出力
49    printArray(n,before);
50    
51    for(i=1;i<=n;i++){//斜め方向に並び替え
52        int temper[i];//要素を一時的に格納する配列
53        for(j=0;j<i;j++){
54            temper[j]=before[n-i+j][j];
55            }
56        Bsort(temper,i);//行列の要素をソート
57        for(int k=0;k<i;k++){
58            ans[i-k+1][k]=temper[k];//斜め方向に格納
59        }
60    }
61    for(i=1;i<=n;i++){
62        int temper2[i];
63        for(j=0;j<i;j++){
64            temper2[j]=before[j][n-i+j];
65            }
66        Bsort(temper2,i);
67        for(int k=0;k<i;k++){
68            ans[k][i-k+1]=temper2[k];
69        }
70    }
71    printf("ans\n");
72    printArray(n,ans);//ソート後の行列を出力
73    return 0;
74}

試したこと

斜めソートについて具体例を考えforループの中身をよく見なおしたり、何回も実行してどのような処理がされているのか考えました。
しかしどこで間違えているのかわかりませんでした。
どなたかご教授いただければ助かります。よろしくお願いします。

補足情報（FW/ツールのバージョンなど）

Visual sutdio code
Ubunts 20.0.4.LTS

行動規範の内容に同意します

回答2件

ベストアンサー

折角(?)ソートも書かれているので、行列内を斜めにアクセスできるアクセサを作れば、メインのループは一本で済むのではないでしょうか。

c
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MIN 0
5#define MAX 100
6
7typedef struct {
8  int n;
9  int a[0];
10} Matrix;
11
12Matrix *allocMatrix(int n) {
13  Matrix *m=malloc(sizeof(Matrix)+sizeof(int)*n*n);
14  m->n=n;
15  return m;
16}
17void freeMatrix(Matrix *m) {
18  free(m);
19}
20int getMatrix(Matrix *m, int c, int r) {
21  return m->a[m->n*r+c];
22}
23void setMatrix(Matrix *m, int c, int r, int v) {
24  m->a[m->n*r+c]=v;
25}
26
27typedef struct {
28  Matrix *m;
29  int oc,or; //開始位置オフセット(どちらかは0)
30} Diagonal;
31
32int getDiagonal(Diagonal *d, int i) {
33  return getMatrix(d->m,d->oc+i,d->or+i);
34}
35void setDiagonal(Diagonal *d, int i, int v) {
36  setMatrix(d->m,d->oc+i,d->or+i,v);
37}
38int getDiagonalLength(Diagonal *d) {
39  return d->m->n-(d->oc+d->or);
40}
41void swapDiagonal(Diagonal *d, int i, int j) {
42  int t=getDiagonal(d,i);
43  setDiagonal(d,i,getDiagonal(d,j));
44  setDiagonal(d,j,t);
45}
46
47//ソート
48void sortDiagonal(Diagonal *d){
49  int size=getDiagonalLength(d);
50  for(int i=0;i<size;i++){
51    for(int j=i+1;j<size;j++){
52      if(getDiagonal(d,i)>getDiagonal(d,j)){
53        swapDiagonal(d,i,j);
54      }
55    }
56  }
57}
58
59//配列を出力する関数
60void printMatrix(Matrix *m, char *header){
61  if(header!=NULL)printf(header);
62  for(int r=0;r<m->n;r++){
63    for(int c=0;c<m->n;c++)printf("%4d",getMatrix(m,c,r));
64    printf("\n");
65  }
66}
67
68//値をインプットする関数
69int input(int min, int max){
70  int result;
71  while(1){
72    scanf("%d",&result);
73    if(min<=result&&result<=max) break;
74    printf("入力された値は無効です\n");
75  }
76  return result;
77}
78
79Matrix *inputMatrix() {
80  printf("正方行列の列の数を入力してください。\n"); fflush(stdout);
81  int n=input(MIN,MAX);
82
83  Matrix *m=allocMatrix(n);
84
85  printf("%d×%d行列A(i,j)の要素を入力してください。\n",n,n); fflush(stdout);
86  for(int i=0;i<n*n;i++){
87    printf("A(%2d, %2d) = ",i/n+1,i%n+1); fflush(stdout);
88    scanf("%d",&m->a[i]);
89  }
90
91  return m;
92}
93Matrix *testMatrix() {
94  int n=3;
95  Matrix *m=allocMatrix(n);
96
97  int sample[]={1,5,3,4,6,2,4,8,2};
98  for(int i=0;i<n*n;i++)m->a[i]=sample[i];
99
100  return m;
101}
102
103int main (void){
104  Matrix *m=inputMatrix();
105  //Matrix *m=testMatrix();
106
107  printMatrix(m,"before sort:\n");//ソート前の行列を出力
108
109  Diagonal d;
110  d.m=m;
111
112  d.oc=0;
113  d.or=0;
114  sortDiagonal(&d);
115
116  for(int i=1;i<m->n-1;i++){
117    d.oc=i;
118    d.or=0;
119    sortDiagonal(&d);
120
121    d.oc=0;
122    d.or=i;
123    sortDiagonal(&d);
124  }
125
126  printMatrix(m,"ans\n");//ソート後の行列を出力
127
128  freeMatrix(m);
129
130  return 0;
131}

実行結果

plain
1正方行列の列の数を入力してください。
23
33×3行列A(i,j)の要素を入力してください。
4A( 1,  1) = 9
5A( 1,  2) = 8
6A( 1,  3) = 7
7A( 2,  1) = 6
8A( 2,  2) = 5
9A( 2,  3) = 4
10A( 3,  1) = 3
11A( 3,  2) = 2
12A( 3,  3) = 1
13before sort:
14   9   8   7
15   6   5   4
16   3   2   1
17ans
18   1   4   7
19   2   5   8
20   3   6   9

投稿2021/12/07 08:15

編集2021/12/07 11:31

jimbe

総合スコア13219

diff
1-            if(data[i]<data[j]){
2+            if(data[i]>data[j]){
3
4-        for(int k=0;k<i;k++){
5-            ans[i-k+1][k]=temper[k];//斜め方向に格納
6+        for(j=0;j<i;j++) {
7+            ans[n-i+j][j]=temper[j];
8
9-        for(int k=0;k<i;k++){
10-            ans[k][i-k+1]=temper2[k];
11+        for(j=0;j<i;j++){
12+            ans[j][n-i+j]=temper2[j];

追記
上記の修正でもよいのですが、Bsort を次のようにすると、
main で Bsort を呼び出す2つの for文が簡単になります。

c
1void Bsort(int data[], int size, int d)
2{
3	for (int i = 0; i < size; i += d) {
4		for (int j = i + d; j < size; j += d) {
5			if (data[i] > data[j]) {
6				int tmp = data[i];
7				data[i] = data[j];
8				data[j] = tmp;
9			}
10		}
11	}
12}
13			scanf("%d", &before[i][j]);
14			ans[i][j] = before[i][j];  // 入力時に ans にコピー
15
16	for (i = 1; i <= n; i++) Bsort(&ans[n-i][0], i*(n+1), n+1);
17	for (i = 1; i < n; i++) Bsort(&ans[0][i], (n-i)*(n+1), n+1);