クイックソートの処理内容

Question

『プログラミングの宝箱 アルゴリズムとデータ構造 第2版』(SBクリエイティブ株式会社)の内容の
第1章、クイックソートのjava版サンプルの以下の処理内容がわかりません。
文法的にわからない箇所はないのですが、なぜこの処理で並べ替えができるのか？
どの箇所でどういう作業をしているのかがわかりません。
quickSort(int bottom, int top, int[] data)メソッドの処理内容について
具体的に何をやっているのか理解できる方がいれば、解説お願いいたします。

import java.util.Random;

class List1_3 {
// データの件数
private static final int N = 10;
private static int[] sort = new int[N];

private static void quickSort(int bottom, int top, int[] data) {
    int lower,upper;

    if (bottom >= top)
        return;
    // 先頭の値を「適当な値」とする
    int div = data[bottom];
    for (lower = bottom, upper = top; lower < upper;) {
        while (lower <= upper && data[lower] <= div)
            lower++;
        while (lower <= upper && data[upper] > div)
            upper--;
        if (lower < upper) {
            int temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
        }
    }

    // 最初に選択した値を中央に移動する
    int temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;

    quickSort(bottom, upper - 1, data);
    quickSort(upper + 1, top, data);
}

public static void main(String args[]) {
    Random random = new Random();
    System.out.println("ソート準備");
    for (int i = 0; i < N; ++i) {
        sort[i] = random.nextInt(1000);
        System.out.print(sort[i] + " ");
    }
    System.out.println("\nソート開始");
    quickSort(0, N - 1, sort);
    System.out.println("ソート終了");

    for (int i = 0; i < N; ++i) {
        System.out.print(sort[i] + " ");
    }
}

}

Answer 1

クイックソートの基本的なアルゴリズムは swordone さんのおっしゃるとおりです。このコードでは、「ある区間」のquickSort をまかされたら、「基準値以下をあつめた区間」「基準値」「基準値より大きい区間」の三つに (この順に) わけ、「基準値以下をあつめた区間」と「基準値より大きい区間」のそれぞれに再帰的に quickSort をさせて、最終的に全体がソートされる、ということです。ですので、私は『「基準値以下をあつめた区間」「基準値」「基準値より大きい区間」の三つに (この順に) わける』ことがどうやって実現されているのか、図解します。

最初 (1) は、関数 quickSort() が呼ばれたところです。長いデータ列の中の bottom (以下 b) と top (同じく t) の間の区間のソートを担当することになります。lower (l) と upper (u) は、それぞれ最初は b と t の位置から始まり、互いに近づく方にひとつずつ移動していきます。この移動を行っているのがコード中の while のところですね。

(2) は、while を抜けて u と l が止まったところを表しています。背景色が灰色のところは基準値 div との大小関係がわからないところ (最初は全部) で、この時点でわかったところが色づけしてあります。div 以下のところが黄色、div より大きいところが青になっています。while が止まった、ということで、とまったところの l のころは青、u のところが黄色になっているにご注目ください。
で、

int temp = data[lower];
data[lower] = data[upper];
data[upper] = temp;

のくだりで l と u のところの値を交換します。

交換が終わったところが (3) です。

で、まだ l が u より小さいので、また l と u を近づける作業をしていきます。(4), (5)。

l と u がぶつかったら、最初の for を抜けます。これが (6) のところです。
div と l のところの値を交換しろ、とのことなので交換したのが (7) です。これで、『「基準値以下をあつめた区間」「基準値」「基準値より大きい区間」の三つに (この順に) わける』ことができました。
できたら、「基準値以下をあつめた区間」「基準値より大きい区間」のそれぞれを quickSort させます。

こんなんでご理解いただけるでしょうか。

Comments

[m.g2017]

わざわざ図解での解説ありがとうございます。
なんとなく行ごとにどういう処理をしているのか見えてきました。

Answer 2

はっきり言ってこのコード、無駄な処理が入っていたり意図がわからないことをしていたり、
おかしなコードになっています。
クイックソートの考え方はちょっと検索すれば山ほど出てきます。
読むのが辛ければ動画になっているものもあったりします。→クイックソート(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個除外してソートしようとしています。
これがないと再帰処理が余計に乗っかることになるのでそれを避ける手立てなのですね。

Comments

[退会済みユーザー]

> これがなぜ入っているかがわかりません。コメント通りの動作もできません。
コメント内の"中央"は、そのときの位置 upper であると推測できます。
そうすると、最初に決めた適当な値 div の位置を upper (中央) に確定させ、
その左右で再帰的に quickSort を呼び出す、という風に読めます。
これはまさにクイックソートの再帰そのものだと思います。

[swordone]

これ無しで考えてみたら、2回目で下グループで先頭が下グループ末尾に移動して1つだけ分離するという、明らかな非効率であることがわかりました。

[退会済みユーザー]

> swordone さん
返信ありがとうございます。
追記と私のコメントが入れ違いで更新されていたようで、失礼しました。

> m.g2017 さん
クイックソートはピボットの選択方法や分割に至るまでの
値交換の方法にいくらかの種類があるようなので、
実装によっては理解しにくいと感じるものがあるかもしれません。
swordone さんの書かれているように、
アルゴリズムの原理を理解した上でコードを読めば、
それが多少わかりにくいと感じても読むことができると思います。
まずはアルゴリズムの原理を正しく理解することが大切です。

[m.g2017]

詳細な解説ありがとうございました。
unauさんの図解と合わせることで、行ごとの処理をイメージできるようになりました。