Java：バブルソート

Question

バブルソートのコードなんですが、ネストされたfor文あたりがよく理解できません。
また初心者のためのこのようなコードで一般的につまずく人は少ないのでしょうか？
自分だけわけわからんじゃないかと思って不安です笑

import java.io.*;
 class practice1 {
   public static void main(String[] args) throws IOException {

     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

     int[] test = new int[5];
     System.out.println(test.length + "人の点数を入力してください");

     for(int i=0; i<test.length; i++) {
       String str = br.readLine();
       test[i] = Integer.parseInt(str);
     }

     for(int s=0; s<test.length-1; s++) {
       for(int t=s+1; t<test.length; t++) {
         if(test[t] > test[s]) {
           int tmp = test[t];
           test[t] = test[s];
           test[s] = tmp;
         }
       }
     }

     for(int j=0; j<test.length; j++) {
       System.out.println((j+1) + "番目の点数は" + test[j] + "点です");
     }
   }
 }

Answer 1

コレ、バブルソートじゃありません。選択ソートです。
バブルソートだと思い込んで読んだら理解できんだろね。

Comments

[KiyoshiMotoki]

バブルソートだと思いますが...？

https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88

[swordone]

バブルソートは「隣り合った要素」を比較します。
これは基準位置と比較して入れ替えています。
従ってバブルソートではありません。

[KiyoshiMotoki]

失礼しました。

test[t] と test[s] を比較・入れ替えしているので、確かに選択ソートですね。

[episteme]

バブルソートなら
if(test[t] > test[t+1]) { /* 隣接要素を入れ替える */ }
であるハズ。

[退会済みユーザー]

都度交換してるので、どちらでもないと思いますが。

[episteme]

いや、選択ソートですよ。

内側のloopによって
「testのs番目からそれ以降の中から最も大きいものを*選択*してs番目と交換」
を実現してますから。
※ ま、都度交換してるのは無駄ではあるけども

[退会済みユーザー]

選択なら都度交換しないのが特徴だと思っていました。ソートはそっくりさんとか派生がいくらでもあるので細かいこと言ってもどうかと思いますけど。

[knj]

ちなみにこちらのコードはやさしいJava第6版からの抜粋です。ありがとうございました。

[fuzzball]

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14137955339
これか。

Answer 2

バブルソートとはどういうことをやるのかを解説した本なりサイトなりを見たうえで、コードと見比べるのがよいかと思います。
それこそ Wikipedia でもよいので。
※できればトランプか何かを使って、実際に手を動かしてやってみると理解が深まります

バブルソートは速度こそ遅いですが、ソートの基本を押さえられることから、よく題材として出されるものです。

Comments

[knj]

ありがとうございました！先ほどまた見てみたら普通に理解できました！