クイックソート

[piro]

C言語で表現したクイックソートに関することで質問があります。
添付したソースコードは、クイックソートのコードであるということは、理解できました。
このソースの処理内容は、配列arrayを昇順にソートするものです。

添付しましたソースコード内の（a）のsort関数の呼び出しにおいて、常にkとbが等しくなり、かつ（b）の処理が行われないようにarrayを並べかえよ、という問題です。
数日調べたのですが、どうしてもこの問題に関する解凍を導くことができませんでした。
クイックソートの処理が遅くなる場合（この課題の場合、配列arrayが最初から昇順に並んでいる）ではないかと考えていましたが、違いました。

この問題の解決方法を教えていただけるとうれしいです。
よろしくお願いします。

[イーノック]

答えはどのように確認するのでしょうか？
ソースコード眺める感じでは、こういうことかなと思いますが
20,40,60,80,10,50,30,70

[piro]

ノーイックさん＞

ノーイックさんが示してくださった順序に配列を書き直すことによって、求めている答えがでました。
どのように考えたらこのような解を導きだすことができたのでしょうか？？

[Dixq (管理人)]

クイックソートってなかなか解りにくいですよね。
昔々に作ったクイックソート解説アプリがあるのでよければ参考にどうぞっ。

http://dixq.net/sort.html

[イーノック]

非常に説明しづらいのですが、一応、大まかな私が追ったソースコードの流れを書いておきます。
管理人さんが貼られているところで、理解すればそう難しい内容ではないと思いますよ。

sort(k,b,arr);//基準値の右側をソートする-------(a)
k == bのときどうなるか？
sort関数内 if( b <= a) return; なので、この問題では(a)の行は考える必要がない。

つまり、↓これだけ考えればよい
sort(a,k-1,arr);//基準値の左側をソートする


話は戻って、（a）のsort関数の呼び出しにおいて、常にkとbが等しくなり
→ kの値を決めている個所を探す
→ k = arrange(a,b,arr); //返り値ｋとarrange呼び出し時の配列最大範囲b

→ arrange関数内を調べる必要がある
returnをみるとleftを返しているので、leftについて調べる
　プログラム内を見ると返り値leftがbに近づくのは次の２か所を通る時

while(arr[left] < bd){
left++; if(left > b) break;
}

　 } else if (left <= right){・・・・(c)
temp = arr[left];
arr[left] = arr[right]; arr[right] = temp;

left++; right--;

→ leftは常にインクリメントされなければ、b+1の値にならない為、
条件(a)を満たすのに、bdは探索配列内で最大の値が入っていることが条件となるので
bdの値を決めているところを探す。
　bd = arr[(a+b)/2]; //このarrの中身が並び替え後の配列でも、常に最大値になる必要がある。

また(c)からもわかるように、bd(arr[left] )と探索配列内のb(right)の位置と交換している、

例えば a= 0 b = 7なら、bd = arr[3];
00 01 02 03 04 05 06 07
** ** ** 80 ** ** ** **

a= 0 b = 5なら、bd = arr[2];
00 01 02 03 04 05 06 07
** ** 60 ** ** ** ||70 80 //70,80は確定済み

bdが最大　かつ　bdは探索配列の最大要素位置と交換される　
という条件が求められたので、後は手書きで導いた

(b)については、 if(right < a)　この条件が実行されなければよい
問題の性質上、上記の事柄からaは常に０であるので、rightについて考えればよい。
説明は省略しますが、ここを考える必要があるのは、bが１の時だけです。

[piro]

イーノックさん＞
先程は名前を間違えてしまいすみませんでした。
分かりやすい解説を本当にありがとうございました。
再起処理が加わると本当に混乱します。
自力でトレースする力をもっと養っていきます。


管理人さん＞
このアプリでクイックソートのおおまかな流れを理解することができました。
本当にありがとうございます。
自力でトレースする力をもっと磨きます。