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

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

ただいまの
回答率

90.33%

  • Java

    14427questions

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

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 391

runako67

score 2

 前提・実現したいこと

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

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

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

import java.util.Random;
public class random{
  public static void main(String[] args){
    Random random = new Random();  //Create random object of random class that will 
    //enable input via console
    int[] a = new int[100];        //crate array which has 100 space

    for(int q=0;q<2;q++){         //repeating this action 10 times
      System.out.println();
      System.out.println("\nOrginal order : ");
      for(int i=0;i<100;i++)         //specify that there is 100 numbers in array
      {
        a[i]=random.nextInt(100);    //put ransom numbers into array list
      }
      for(int i =0; i<a.length;i++){ 
        System.out.print(a[i] + " ");
      }

      IntBubbleSorter.bubbleSort(a); //Pass the array to the bubbleaort

      System.out.println("Sorted in bubble sort : "); //Show sorted values that are sorted by bubble
      for(int i=0;i<a.length;i++){
        System.out.print(a[i] + " ");
      } 
    }

}
public class IntBubbleSorter
{
  public static void bubbleSort(int[] array)
  {
    int lastPos;
    int index;
    int temp;
    int comp = 0;

    for( lastPos = array.length -1; lastPos>=0; lastPos--)
    {
      for (index = 0; index<=lastPos -1; index++)
      {
        comp ++;
        if(array[index] > array[index+1])
        {
          temp = array[index];
          array[index] = array[index+1];
          array[index+1] = temp;
        }
      }
    }  System.out.println("\nnumber of comparison in bubble sort: " + comp );   
  }
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2018/04/28 07:49 編集

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

    キャンセル

  • runako67

    2018/04/29 01:28

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

    キャンセル

  • swordone

    2018/04/29 01:40

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

    キャンセル

回答 3

checkベストアンサー

+4

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

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/04/28 09:36 編集

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

    キャンセル

  • 2018/04/28 09:54

    訂正しました。

    キャンセル

0

こんにちは、

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

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

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

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

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

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] + "回");
            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回
平均:2449.7回

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/04/28 11:16

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

    キャンセル

  • 2018/04/28 11:24

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

    キャンセル

  • 2018/04/28 11:33 編集

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

    キャンセル

  • 2018/04/28 11:46

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

    キャンセル

  • 2018/04/29 03:47

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

    キャンセル

0

public class IntBubbleSorter {
    final static int REPEAT_COUNT = 3;
    final static int ARRAY_SIZE = 100;

    public static void main(String[] args) {
        int count = 0;
        int[] array = new int[ARRAY_SIZE];

        for (int i = 0; i < REPEAT_COUNT; i++) {
            int comp = bubbleSort(randum_array(array));
            System.out.println("number of comparison in bubble sort: " + comp);
            count += comp;
        }
        System.out.println("平均比較回数:" + 1.0 * count / REPEAT_COUNT);
    }

    public static int[] randum_array(int[] array) {
        for (int i = 0; i < array.length; i++) {
            array[i] = (int)(Math.random() * 101);
        }
        return array;
    }

    public static int bubbleSort(int[] array) {
        int lastPos;
        int index;
        int temp;
        int comp = 0;

        for (lastPos = array.length - 1; lastPos >= 0; lastPos--) {
            for (index = 0; index <= lastPos - 1; index++) {
                if (array[index] > array[index + 1]) {
                    comp++;
                    temp = array[index];
                    array[index] = array[index + 1];
                    array[index + 1] = temp;
                }
            }
        }
        return comp;
    }
}


実行例:
イメージ説明

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

  • Java

    14427questions

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