回答編集履歴

1 説明の訂正

退会済みユーザー

退会済みユーザー

2018/04/28 10:36  投稿

こんにちは、
### バブルソートにおける比較回数について
データがN個あるときの比較回数はN * (N + 1)/2です。
[Javaでバブルソート](https://qiita.com/Liberty/items/180b686c97dc8732235a)
あくまでも、私の憶測にすぎませんが、おそらく求めたいのは比較回数ではなく、比較後
**実際にデータを入れ替えた回数**(データを入れ替えた回数)だと思いました。間違ってたらすみません。
一応、その方法を書いておきます。
(i)100個の乱数を生成し、配列に格納する。
(ii)バブルソートをする。
(iii)データの入れ替えを行った回数を数える。
(iv) (i)~(iii)を10回繰り返し、それぞれのデータの入れ替えを行った回数を配列に格納する。
(v) その合計を計算し、10.0で割る。
以下、私が書いたソースコードを載せておきます。
データのほうを表示すると見づらくなるためコメントアウトしました。
実際のデータを見るとちゃんとバブルソートされていることがわかると思います。
```Java
import java.util.Random;
public class random {
   public static void main(String[] args){
       Random rand = new Random(); 
       int[] data = new int[100]; 
       //int []data2 = new int[100];
       int []count = new int[10];
       int loop = 0;
       while(loop < 10){
           System.out.print(loop + 1 + "回目:");
           for(int i = 0; i < 100; i++){
               data[i] = rand.nextInt(100);
               //System.out.print(data[i] + " ");
           }
           for(int i = 0; i < 99; i++){
               for(int j = 99; j > i; j--){
                   int tmp;
                   if(data[j - 1] > data[j]){
                       tmp = data[j - 1];
                       data[j - 1] = data[j];
                       data[j] = tmp;
                       count[loop]++;
                   }
               }
           }
           
           /*System.out.println();
           System.out.println("バブルソート完了");
           for(int i = 0; i < 100; i++){
               System.out.print(data[i] + " ");
           }*/
           System.out.println("比較回数:" + count[loop] + "回");
           System.out.println("回数:" + count[loop] + "回");
           loop++;
       }
       int sum = 0;
       for(int i = 0; i < count.length; i++){
           sum += count[i];
       }
       double average = sum / 10.0;
       
       System.out.println("平均:" + average + "回");
       
   }
}
```
1回目:比較回数:2355回
2回目:比較回数:2433回
3回目:比較回数:2331回
4回目:比較回数:2548回
5回目:比較回数:2664回
6回目:比較回数:2448回
7回目:比較回数:2488回
8回目:比較回数:2337回
9回目:比較回数:2495回
10回目:比較回数:2398回
1回目:回数:2355回
2回目:回数:2433回
3回目:回数:2331回
4回目:回数:2548回
5回目:回数:2664回
6回目:回数:2448回
7回目:回数:2488回
8回目:回数:2337回
9回目:回数:2495回
10回目:回数:2398回
平均:2449.7回

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る