ページ 1 ／ 1
学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月18日(日) 13:20
by MORI
ランダムに生成されたint型のMAX×MAXの大きさ（MAXはマクロで定義）の２次元配列data[MAX][MAX]の中身をクイックソートで昇順にする課題が出ましたがわかりません。１次元の動作にから類推して２次元版を作ってみたのですが、無限ループだったり完全にソートされていなかったりと問題点がわからなくて困っています。
メイン関数は配列の中身を出力するだけで書くと冗長になってしまうと思うので、ソート用の関数だけを下に書きます。アルゴリズムに強い方、助けてください。以下の結果は無限ループでした。
コード:
void quick(int data[MAX][MAX],int first_x,int first_y,int last_x, int last_y){
int i,j,k,l;
int temp;
int x;
x = data[(first_x+last_x)/2][(first_y+last_y)/2];
i=first_x; j=first_y; k=last_x; l=last_y;
for(;;){
while(data[i][j] < x){
/*xより大きな値が見つかるまで
インデックスを左から右に一つ進める。ただし、行替えが起きるとき
jを0にし、iを進める。*/
j++;
if(j>MAX-1){
j=0; i++;
}
}
while(data[k][l] > x){
/*xより小さな値が見つかるまで
右側のインデックスを一つ左側に進める。上と逆の動作をさせる*/
l--;
if(l<0){
l=MAX-1; k--;
}
}
/*左側のインデックスが右側より大きくなったらループから抜ける*/
if((i*MAX+j) >= (k*MAX+l)) break;
/*左側と右側を入れ替える*/
temp=data[i][j]; data[i][j]=data[k][l];data[k][l]=temp;
}
/*超えちゃった分を元に戻す*/
j--;
if(j<0){
j=MAX-1; i--;
}
l++;
if(l>MAX-1){
l=0;k++;
}
/*再帰部分*/
if((first_x*MAX+first_y) <(i*MAX+j))
quick(data,first_x,first_y,i,j);
if((k*MAX+l) < (last_x*MAX+last_y))
quick(data,k,l,last_X,last_y);
}
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月18日(日) 18:37
by かずま
MORI さんが書きました:コード:
x = data[(first_x+last_x)/2][(first_y+last_y)/2];
MAX = 4 だとして、data[0][2], data[0][3], data[1][0]]
の3つをソートしようとすると、first_x = 0, first_y = 2,
last_x = 1, last_y = 0 なので、x = data[0][1] となり、
ソート対象外の値を x に設定してしまいます。
次のようにしたほうが良いでしょう。
コード:
k = ((first_x *MAX + first_y) + (last_x *MAX + last_y)) / 2;
x = data[k / MAX][k % MAX];
そこを修正した場合、data の値がすべて異なればうまくいきますが、
同じ値があると、無限ループになることがあるようです。
この問題の解決は宿題としておきます。
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月19日(月) 01:18
by MORI
解答ありがとうございます。
おっしゃる通りのコードで実行したところ上手くいきました。
無限ループについてはstatic変数で同じ引数を持つquick関数が実行されないかチェックして
goto文で無理やり処理しました。(goto文はあまり望ましくないのは聞いたことありますが。）
ちょうどまさに提出の前日だったので本当に助かりました。ありがとうございます。
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月19日(月) 09:04
by かずま
MORI さんが書きました:無限ループについてはstatic変数で同じ引数を持つquick関数が実行されないかチェックして
goto文で無理やり処理しました。(goto文はあまり望ましくないのは聞いたことありますが。）
そのコードを貼り付けてください。
望ましいコードを知りたいと思いませんか？
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月20日(火) 01:42
by MORI
ご指摘してもらえたとおり、以下のコードで全て上手くいきました。
無限ループになる可能性について言われましたが、無限ループになるかどうかを自分は検証できていないです。
というのも、もともと自分でコードを考えていたときにも無限ループに出くわしていたので、
そのときの対処法をとりあえず使って上手くいったからです。もしかしたら無限ループはそもそも起きないかもしれません。
（今忙しくて自分で検証できないのは申し訳ないです）
コード:
#define MAX 10
#define LINE MAX
#define ROW MAX
void quickSort2(int data[LINE][ROW],int first_x,int first_y,
int last_x,int last_y){
/*static宣言は再帰元の引数を保持させて、新しく関数を実行するときにその引数と呼び出し元の引数を検証することで無限ループを防ぐ*/
static int fi=0,li=0;
static int fj=0,lj=0;
static int fk=LINE;
static int lk=LINE;
static int fl=ROW;
static int ll=ROW;
int i,j,k,l;
int temp;
int x;
/*ピボットの値を次のようにしないとうまくいかない*/
i=((first_x*ROW+first_y) +(last_x*ROW+last_y))/2;
x = data[i/ROW][i%ROW];
i=first_x; j=first_y; k=last_x;l=last_y;
for(;;){
/*左側のインデックスをx以上の値が来るまで進める*/
while(data[i][j] < x){
j++;
if(j>ROW-1){
j=0;
i++;
}
}
/*右側のインデックスをx以下の値が来るまで進める*/
while(data[k][l] > x){
l--;
if(l < 0){
l=ROW-1;
k--;
}
}
/*左側のインデックスと右側のインデックスがすれ違ったら終了*/
if((i*ROW+j) >= (k*ROW+l))break;
/*値の交換*/
temp=data[i][j];
data[i][j]=data[k][l];
data[k][l] =temp;
j++;
if(j>ROW-1){
j=0;
i++;
}
l--;
if(l<0){
l=ROW-1;
k--;
}
}
/*再帰部分*/
if((first_x*ROW+first_y)<(i*ROW+j)){
/*無限ループのチェック*/
if((first_x==fi)&&(first_y==fj)&&(i==fk)&&(j==fl))goto next1;
/*引数情報の更新*/
fi=first_x; fj=first_y; fk=i; fl=j;
quickSort2(data,first_x,first_y,i,j);
}
next1:
if(l<(ROW-1)){
l++;
}else{
l=0;
k++;
}
if((k*ROW+l) < (last_x*ROW+last_y)){
/*無限ループのチェック*/
if((k==li)&&(l==lj)&&(last_x==lk)&&(last_y==ll))goto next2;
/*引数情報の更新*/
li=k; lj=l; lk=last_x; ll=last_y;
quickSort2(data,k,l,last_x,last_y);
}
next2:
printf("");
}
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月20日(火) 04:14
by かずま
私は次のように修正しました。
コード:
#include <stdio.h> // printf, putchar
#define MAX 4
int a[MAX][MAX] = { // 同じ値(17)があるテストデータ
18, 19, 14, 21,
24, 16, 11, 17,
17, 22, 20, 13,
15, 12, 26, 23,
};
void print(void)
{
for (int i = 0; i < MAX; i++, putchar('\n'))
for (int j = 0; j < MAX; j++) printf(" %3d", a[i][j]);
putchar('\n');
}
void quick(int data[][MAX], int first_x, int first_y, int last_x, int last_y)
{
int i = first_x, j = first_y, k = last_x, l = last_y;
int temp = ((i * MAX + j) + (k * MAX + l)) / 2;
int x = data[temp / MAX][temp % MAX]; // 正しいピボット
for (;;) {
while (data[i][j] < x)
if (++j > MAX - 1) j = 0, i++; // j を増やす --- (1)
while (data[k][l] > x)
if (--l < 0) l = MAX - 1, k--; // l を減らす --- (2)
if (i * MAX + j >= k * MAX + l) break;
temp = data[i][j], data[i][j] = data[k][l], data[k][l] = temp;
if (++j > MAX - 1) j = 0, i++; // j を増やす --- (3)
if (--l < 0) l = MAX - 1, k--; // l を減らす --- (4)
}
if (--j < 0) j = MAX - 1, i--; // j を減らす --- (5)
if (first_x * MAX + first_y < i * MAX + j)
quick(data, first_x, first_y, i, j);
if (++l > MAX - 1) l = 0, k++; // l を増やす --- (6)
if (k * MAX + l < last_x * MAX + last_y)
quick(data, k, l, last_x, last_y);
}
int main(void)
{
print();
quick(a, 0, 0, MAX - 1, MAX - 1);
print();
}
No.1 のプログラムは、(3)と(4)がないので、無限ループになります。
No.5 のプログラムは、(5)がないので、無限ループになります。
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月21日(水) 12:07
by MORI
前インクリメンでトだいぶ簡潔なコードになるんですね。
課題に関して他の人のコードを見る機会がなく、学べる機会もなかったのでとてもよかったです。
ありがとうございます。
Re: 学校の宿題の2次元配列のクイックソートがわかりません
Posted: 2017年6月21日(水) 16:47
by かずま
MORI さんが書きました:前インクリメンでトだいぶ簡潔なコードになるんですね。
前置増分演算子であろうが、後置増分演算子であろうが、簡潔に書けます。
元のコード
コード:
j++;
if (j > MAX - 1) {
j = 0;
i++;
}
prefix increment
コード:
if (++j > MAX - 1) j = 0, i++;
postfix increment
コード:
if (j++ >= MAX - 1) j = 0, i++;
マクロを使うと、全体が見やすくなります。
コード:
#define C(i, j) (i * MAX + j)
#define INC(i, j) (++j > MAX - 1 && (j = 0, i++))
#define DEC(i, j) (--j < 0 && (j = MAX - 1, i--))
void quick(int data[][MAX], int first_x, int first_y, int last_x, int last_y)
{
int i = first_x, j = first_y, k = last_x, l = last_y;
int temp = (C(i, j) + C(k, l)) / 2;
int x = data[temp / MAX][temp % MAX];
for (;;) {
while (data[i][j] < x) INC(i, j);
while (data[k][l] > x) DEC(k, l);
if (C(i, j) >= C(k, l)) break;
temp = data[i][j], data[i][j] = data[k][l], data[k][l] = temp;
INC(i, j);
DEC(k, l);
}
DEC(i, j);
if (C(first_x, first_y) < C(i, j))
quick(data, first_x, first_y, i, j);
INC(k, l);
if (C(k, l) < C(last_x, last_y))
quick(data, k, l, last_x, last_y);
}