質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.78%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,622

m.g2017

score 19

『プログラミングの宝箱 アルゴリズムとデータ構造 第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] + " ");
}
}
}

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

クイックソートの基本的なアルゴリズムは 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 させます。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/04 23:12

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

    キャンセル

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/03 21:44

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

    キャンセル

  • 2017/09/03 21:47

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

    キャンセル

  • 2017/09/03 21:57

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

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

    キャンセル

  • 2017/09/04 23:15

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.78%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る