質問: 0; i < N; ++i) { System.out.print(sort[i] + " "); } } }
回答: はっきり言ってこのコード、無駄な処理が入っていたり意図がわからないことをしていたり、 おかしなコードになっています。 クイックソートの考え方はちょっと検索すれば山ほど出てきます。 読むのが辛ければ動画になっているものもあったりします。→クイックソート(YouTube) ざっくり言えば、**ある値より小さい数を左に、大きい数を右に寄せて2分割**を繰り返していくソート法です。 "ある値"は、配列内の要素であればなんでもかまいません。これを仮に基準値と呼ぶことにします。 左から基準値よりも大きな数を探し(この場所がlower)、右から基準値よりも小さな数を探します(この場所がupper)。 この場所が問題で、左に小さな数、右に大きな数を寄せたいのに、左に大きな数があるのは困ります。 もしそうなっていた場合(lowerがupperより小さいとき)、その二つを入れ替えて正しく分けられるようにします。 これを続けていくと、lowerがupperを上回ります。この時、lowerより小さいインデックスでは基準値より小さく、upperより大きいインデックスでは基準値より大きくなるようになっているはずなので、lowerとupperが交差した場所で2分割できます。 そして、2分割したそれぞれの区画で同じことを行います。これを繰り返していけば、最終的に昇順に並び替えができることになります。 ただ、冒頭でも言った通り質問のコードは意図が読めません。特に、 ``` // 最初に選択した値を中央に移動する int temp = data[bottom]; data[bottom] = data[upper]; data[upper] = temp; ``` これがなぜ入っているかがわかりません。 追記 やっと理解できました。 もともと先頭を基準値に設定していたので、ここに入る前に [b, a1, a2, a3, c1, c2, c3, c4, c5, c6] (b:基準値、an < b < cn) のような状態になります(もちろん個数などは状況によって異なる)。 で、このコードの実行によって [a3, a1, a2, b, c1, c2, c3, c4, c5, c6] のようにして、[a3, a1, a2]の組、[c1, c2, c3, c4, c5, c6]の組のように、 1個除外してソートしようとしています。 これがないと再帰処理が余計に乗っかることになるのでそれを避ける手立てなのですね。