クイックソートの可視化プログラムを考えています

質問

いつもお世話になっております。
当方、理系の学部に在籍中の学生です。

OpenGLを用いてクイックソートを可視化するためのプログラムを考えております。

まず、ソーティングしたい整数配列の要素ひとつひとつを単色の四角形で表現し、数が大きいほど明るく、小さいほど暗くなるよう設定しました。

イメージとしては、Rキーを押す度にソーティングがワンステップずつ進み、徐々に綺麗なグラデーションが出来上がっていく様子を表示させたいのですが、ここが上手くいかず困っております。問題点をご指摘いただけるとありがたいです。

以下、ソースコードの一部となります。

/* ソートする配列 */
int nums[] = {94, 43, 59, 57, 23, 27, 25, 22, 55, 21,
44, 28, 65, 30, 75, 13, 23, 89, 84, 71,
45, 68, 28, 31, 75, 62, 70, 34, 87, 20,
96, 47, 80, 74, 81, 30, 22, 55, 11, 34,
85, 16, 71, 41, 28, 26, 25, 47, 14, 55};

int n = 50;
int flag = 0;

/* 表示コールバック関数の一部 */
void display(void)
{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glLineWidth(5.0);
for(int i = 0; i < n; i++) {
glColor3f(0.0, 0.0, nums[i] * 0.01);
glBegin(GL_POLYGON);
glVertex2f(0.0, 0.0 + 0.5 * i);
glVertex2f(2.0, 0.0 + 0.5 * i);
glVertex2f(2.0, 0.5 + 0.5 * i);
glVertex2f(0.0, 0.5 + 0.5 * i);
glEnd();
}

/* キーボードコールバック関数の一部 */
case 'r':
flag = 1;
break;
case 'q': /* クイックソートする */
QSort(nums, 0, n - 1);
break;

/* クイックソートを行う */
void QSort(int x[], int left, int right)
{
int i, j;
int pivot;

i = left; /* ソートする配列の一番小さい要素の添字 */
j = right; /* ソートする配列の一番大きい要素の添字 */

pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */

while (1) { /* 無限ループ */
while (x[i] < pivot) /* pivot より大きい値が */
i++; /* 出るまで i を増加させる */
while (pivot < x[j]) /* pivot より小さい値が */
j--; /* 出るまで j を減少させる */
if (i >= j) /* i >= j なら */
break; /* 無限ループから抜ける */
Swap(x, i, j); /* x[i] と x[j]を交換 */
while (flag == 0)
glutPostRedisplay();
i++; /* 次のデータ */
j--;
flag = 0; /* flag更新 */
}
if (left < i - 1) /* 基準値の左に 2 以上要素があれば */
QSort(x, left, i - 1); /* 左の配列を Q ソートする */
if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */
QSort(x, j + 1, right); /* 右の配列を Q ソートする */
}

/* 配列の要素を交換する */
void Swap(int x[ ], int i, int j)
{
int temp;

temp = x[i];
x[i] = x[j];
x[j] = temp;
}

回答No.5

Tacosan · ベストアンサー

このプログラムの構造で volatile を付けても, まあダメでしょうね (付けた方が安全ではあるんだけど).

おそらく (#4 にある)
「キーイベントをちゃんと取れて」
という前提がなりたっていないと思います.

一般的なイベントドリブンシステムでは
イベントをとってくる→適切な関数を呼び出す
という処理を繰り返します (メインループ). で, このプログラムではキーボードコールバック関数の中でソートをしているので, そのソートが終わらない限りキーボードコールバック関数からメインループに制御が戻ることはありません. 従ってイベント処理もしません. ところが, イベント処理をしないと flag の値が 1 にならないため while のところでループしてしまい, ソート処理が終わらないことになっています.

よ～するにデッドロックをおこしちゃっています.

スレッド使えばなんとかなるかもしれんけど, 保証はしない.

お礼

お礼が遅くなってしまいまして申し訳ございません。
丁寧な解説感謝いたします。
プログラムの組み方を変えることによって無事解決いたしました。
ご回答ありがとうございました。

回答No.4

ponta1971

うぉっ・・・、恥をさらしただけでしたね・・・。

>while (flag == 0)
glutPostRedisplay();

（※flagはRキーを押した場合に1となる）

というコードを付け加えた場合、1ループごとに再描画されず、表示が初期状態のまま、いつまでも動かないという状況です。

キーイベントをちゃんと取れて、flagが1になってる前提でですが、ループしまくって処理が溜まりRキーを押した処理まで行っていないなんてことはないでしょうか。
タイマーとかでウェイトをかけて1秒に4回とかループ回数を制御してみてはどうでしょうか。

お礼

お礼が遅くなってしまいまして申し訳ございません。
親身に回答してくださり感謝です。
プログラムの組み方を変えることによって無事解決いたしました。
ご回答ありがとうございました。

回答No.3

Tacosan

OpenGL は知らんけど, 一般的なイベントドリブンシステムでこんなことしたら
flag が 1 にならない
よね.

ひょっとしたら flag の定義を
volatile int flag = 0;
に変えればいいのかなぁ... でもダメだろうなぁ....

お礼

続けてのご回答ありがとうございます。
提案していただいた方法を試してみたのですが、Tacosanさんの予想通り、やはり変わらずといった感じでした。
flagをねじ込もうという方針がそもそもいけないのですね……。

回答No.2

Tacosan

えぇっと, C ではそんなことにならないんですが＞#1.

ちなみに, どう「うまくいかない」んでしょうか?

お礼

ご回答、ありがとうございます。

補足

説明不足で大変失礼いたしました。ponta1971さんの回答に捕捉させていただいたとおりの状況となっております。申し訳ございません。

回答No.1

ponta1971

ざっとしか見ていないのですが・・・。

>pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */

このぶぶんって、現在の状態だと
pivot = x[24.5];
このような状態になって値が取れないってことはないですか？
「(left + right) / 2」この値をさらに切り上げる処理が必要なのではないでしょうか。

お礼

ご回答、ありがとうございます。

補足

言葉足りずで申し訳ございません。
クイックソートの部分のみで実行すると、正常に動作することが確認できております。

しかし、上記のとおり関数QSortの途中に

while (flag == 0)
glutPostRedisplay();

（※flagはRキーを押した場合に1となる）

というコードを付け加えた場合、1ループごとに再描画されず、表示が初期状態のまま、いつまでも動かないという状況です。

再描画要求をする位置が良くないのでしょうか……。