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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

3回答

3650閲覧

javaで10回繰り返した比較の平均値を求める

runako67

総合スコア8

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

1クリップ

投稿2018/04/27 19:19

編集2018/04/28 16:36

前提・実現したいこと

Javaで
”bubble sortを利用し、乱数100個を生成して、それらをソートする”
を10回やって、比較回数をだすことに成功しました。次にやらなくてはいけないのは10個出た比較回数の平均を求めることです。
合計の比較回数/10とおいうことはわかるのですが、どうやって比較回数を合計するのかがわかりません。

比較回数=comparisonであっているのかわかりませんが、正解はbubblesortは4950回です。

このクラスをメインメソッドのあるクラスから呼び出したいです。

java

1import java.util.Random; 2public class random{ 3 public static void main(String[] args){ 4 Random random = new Random(); //Create random object of random class that will 5 //enable input via console 6 int[] a = new int[100]; //crate array which has 100 space 7 8 for(int q=0;q<2;q++){ //repeating this action 10 times 9 System.out.println(); 10 System.out.println("\nOrginal order : "); 11 for(int i=0;i<100;i++) //specify that there is 100 numbers in array 12 { 13 a[i]=random.nextInt(100); //put ransom numbers into array list 14 } 15 for(int i =0; i<a.length;i++){ 16 System.out.print(a[i] + " "); 17 } 18 19 IntBubbleSorter.bubbleSort(a); //Pass the array to the bubbleaort 20 21 System.out.println("Sorted in bubble sort : "); //Show sorted values that are sorted by bubble 22 for(int i=0;i<a.length;i++){ 23 System.out.print(a[i] + " "); 24 } 25 } 26 27} 28

java

1public class IntBubbleSorter 2{ 3 public static void bubbleSort(int[] array) 4 { 5 int lastPos; 6 int index; 7 int temp; 8 int comp = 0; 9 10 for( lastPos = array.length -1; lastPos>=0; lastPos--) 11 { 12 for (index = 0; index<=lastPos -1; index++) 13 { 14 comp ++; 15 if(array[index] > array[index+1]) 16 { 17 temp = array[index]; 18 array[index] = array[index+1]; 19 array[index+1] = temp; 20 } 21 } 22 } System.out.println("\nnumber of comparison in bubble sort: " + comp ); 23 } 24 25 26

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2018/04/27 23:59 編集

100個をバブルソートしたなら、比較回数は必ず4950回なのでは?(99+98+97+...+2+1)
runako67

2018/04/28 16:28

そうなんですが、それを計算で証明しなくてはならないのです、、、
swordone

2018/04/28 16:40

証明も何も、バブルソートの仕組みがわかっていれば私の式で終了のはずですが?
guest

回答3

0

ベストアンサー

bubbleSort()の返り値を比較回数にして、main()で平均値を求めてはどうでしょう。

投稿2018/04/27 20:36

編集2018/04/28 00:54
hichon

総合スコア5737

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

KSwordOfHaste

2018/04/28 00:36 編集

小文字で始めてmain()と言ってあげた方が質問者さんが混乱しないかもです。
hichon

2018/04/28 00:54

訂正しました。
guest

0

java

1public class IntBubbleSorter { 2 final static int REPEAT_COUNT = 3; 3 final static int ARRAY_SIZE = 100; 4 5 public static void main(String[] args) { 6 int count = 0; 7 int[] array = new int[ARRAY_SIZE]; 8 9 for (int i = 0; i < REPEAT_COUNT; i++) { 10 int comp = bubbleSort(randum_array(array)); 11 System.out.println("number of comparison in bubble sort: " + comp); 12 count += comp; 13 } 14 System.out.println("平均比較回数:" + 1.0 * count / REPEAT_COUNT); 15 } 16 17 public static int[] randum_array(int[] array) { 18 for (int i = 0; i < array.length; i++) { 19 array[i] = (int)(Math.random() * 101); 20 } 21 return array; 22 } 23 24 public static int bubbleSort(int[] array) { 25 int lastPos; 26 int index; 27 int temp; 28 int comp = 0; 29 30 for (lastPos = array.length - 1; lastPos >= 0; lastPos--) { 31 for (index = 0; index <= lastPos - 1; index++) { 32 if (array[index] > array[index + 1]) { 33 comp++; 34 temp = array[index]; 35 array[index] = array[index + 1]; 36 array[index + 1] = temp; 37 } 38 } 39 } 40 return comp; 41 } 42} 43

実行例:
イメージ説明

投稿2018/04/28 03:42

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

こんにちは、

バブルソートにおける比較回数について

データがN個あるときの比較回数はN * (N + 1)/2です。
Javaでバブルソート

あくまでも、私の憶測にすぎませんが、おそらく求めたいのは比較回数ではなく、比較後
実際にデータを入れ替えた回数(データを入れ替えた回数)だと思いました。間違ってたらすみません。
一応、その方法を書いておきます。

(i)100個の乱数を生成し、配列に格納する。
(ii)バブルソートをする。
(iii)データの入れ替えを行った回数を数える。
(iv) (i)~(iii)を10回繰り返し、それぞれのデータの入れ替えを行った回数を配列に格納する。
(v) その合計を計算し、10.0で割る。

以下、私が書いたソースコードを載せておきます。
データのほうを表示すると見づらくなるためコメントアウトしました。
実際のデータを見るとちゃんとバブルソートされていることがわかると思います。

Java

1import java.util.Random; 2 3public class random { 4 public static void main(String[] args){ 5 Random rand = new Random(); 6 int[] data = new int[100]; 7 //int []data2 = new int[100]; 8 int []count = new int[10]; 9 int loop = 0; 10 while(loop < 10){ 11 System.out.print(loop + 1 + "回目:"); 12 for(int i = 0; i < 100; i++){ 13 data[i] = rand.nextInt(100); 14 //System.out.print(data[i] + " "); 15 } 16 for(int i = 0; i < 99; i++){ 17 for(int j = 99; j > i; j--){ 18 int tmp; 19 if(data[j - 1] > data[j]){ 20 tmp = data[j - 1]; 21 data[j - 1] = data[j]; 22 data[j] = tmp; 23 count[loop]++; 24 } 25 } 26 } 27 28 /*System.out.println(); 29 System.out.println("バブルソート完了"); 30 for(int i = 0; i < 100; i++){ 31 System.out.print(data[i] + " "); 32 }*/ 33 System.out.println("回数:" + count[loop] + "回"); 34 loop++; 35 } 36 int sum = 0; 37 for(int i = 0; i < count.length; i++){ 38 sum += count[i]; 39 } 40 double average = sum / 10.0; 41 42 System.out.println("平均:" + average + "回"); 43 44 } 45} 46

1回目:回数:2355回
2回目:回数:2433回
3回目:回数:2331回
4回目:回数:2548回
5回目:回数:2664回
6回目:回数:2448回
7回目:回数:2488回
8回目:回数:2337回
9回目:回数:2495回
10回目:回数:2398回
平均:2449.7回

投稿2018/04/28 01:34

編集2018/04/28 01:36
退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/04/28 02:16

バブルソートは内側のループで1回も交換が行われなかった場合には終了することができるので、比較回数は固定ではないです。(質問者の実装はそうなっていませんが)
退会済みユーザー

退会済みユーザー

2018/04/28 02:24

その場合は、比較回数が0なのではなく、データを入れ替えた回数が0なのではないですか?
退会済みユーザー

退会済みユーザー

2018/04/28 02:40 編集

例えば内側のループで1回も交換が行われなかった場合には終了するようにしたとして、入力データが既にソート済であったとすると、全体の交換回数は0で比較回数はn-1です。n*(n+1)/2でもn*(n-1)/2でもありません。
退会済みユーザー

退会済みユーザー

2018/04/28 02:46

>「n*(n+1)/2でもn*(n-1)/2でもありません」について 回答に書いてある通りそれは「比較回数」であり0回という言うのは「交換回数」です。 最初交換をするかどうか比較は絶対にされます。そして比較して交換をしなければいけないとき 「交換」をするのです。「比較回数」と「交換回数」は全くの別物ですよ。
swordone

2018/04/28 18:47

なんか議論がおかしくなってません?
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問