合計 昨日 今日

バブルソートについて

[このトピックは解決済みです]

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: さんb
[URL]
Date: 2017年12月03日(日) 16:34
No: 1
(OFFLINE)

 バブルソートについて

バブルソートのプログラムです。
条件として
・ランダムな数字を100個生成して、昇順にバブルソート
・ソート前、ソート後の数字を見やすいように10個ずつ並べて改行する
・普通のバブルソートは並び替えが終了しているのに"データ数-1"繰り返されますが、"データ数-1"行う前に昇順になっていることもあるのでそれを判定してできるだけ少ない回数でバブルソートをする
というのがあります。
質問は
・できるだけ少ない回数でバブルソートをするという条件にwhileを使ってみたがコンパイルできない
・乱数を生成させているが、実行しても同じ数字が表示される
という点です。
宜しくお願いします。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#define NUM_DATA 100
 
void BubSort(int num[], int n);
void datasee(int num[], int n);
int main(void);
 
 
/* バブルソートを行う */
void BubSort(int num[], int n)
{
    int i, j, temp;
    while (num[j] > num[j - 1]) {
        for (j = n - 1; j > i; j--) {
            if (num[j] > num[j - 1]) {  /* 前の要素の方が大きかったら */
                temp = num[j];        /* 交換する */
                num[j] = num[j - 1];
                num[j - 1] = temp;
            }
       
        }
        //datasee(num, NUM_DATA);
    }
}
 
 
 
void datasee(int num[], int n)
{
    int i = 1;
    while (n--) {
        printf("%3d  ", *num++);
        i++;
        if (n % 10 == 0) {
            printf("\n");
        }
    }
    printf("\n");
}
 
int main(void)
{
    int num[100], i;
 
    for (i = 0; i < NUM_DATA; i++) {
        num[i] = rand();
    }
 
    printf("(Before)\n");
    datasee(num, NUM_DATA);
    printf("\n");
 
 
    BubSort(num, NUM_DATA);
    printf("\n");
 
 
    printf("(After)\n");
    datasee(num, NUM_DATA);
    printf("\n");
}

Name: みけCAT
[URL]
伝説なるハッカー(683,566 ポイント)
Date: 2017年12月03日(日) 17:27
No: 2
(OFFLINE)

 Re: バブルソートについて

さんb さんが書きました:・できるだけ少ない回数でバブルソートをするという条件にwhileを使ってみたがコンパイルできない

Wandboxではコンパイルが通りましたが、BubSort関数内で初期化されていない変数iが使用されているという警告が出ました。
未初期化の自動変数の値(不定)が使用されているので、未定義動作になります。
警告もエラーとして扱う環境では、コンパイルできないかもしれません。

さんb さんが書きました:・乱数を生成させているが、実行しても同じ数字が表示される

time.hをincludeし、main関数の最初でsrand((unsigned int)time(NULL));を呼び出すというのが、毎回違う乱数を出させるための入門書的な方法です。
(time関数の性質上、多くの環境では1秒以内に再実行すると同じ乱数になってしまうことがあります)
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: さんb
[URL]
Date: 2017年12月03日(日) 22:26
No: 3
(OFFLINE)

 Re: バブルソートについて

解答の方ありがとうございます。
あと追加で質問があるのですが
バブルソートの初歩的な質問なのですが
2個目のforのfor( j = n-1; j > i; j-- )のj > iなのですがj はj:n-1~j>iの間でj-- jの変化で動作すると認識しているのですが
j > iの間ということは下記のようにn=5とするとi=2,j=2でj > iを満たさずforの繰り返しが終了しn[1]とi[0]の交換が実行されないのでという疑問です。よろしくお願いします。

i j
0 4
1 3
2 2
3 1
4 0

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort( int dt[], int n )
{
    int i, j, temp;
 
    for( i = 0; i < n-1; i++ ) {
        for( j = n-1; j > i; j-- ) {
            if( dt[j-1] > dt[j] ) {
                printf( "i:%d) %d と %d を交換", i, dt[j-1], dt[j] );
                temp = dt[j];
                dt[j] = dt[j-1];
                dt[j-1] = temp;
                printf( " --> " ); prtData( dt, n );
            }
        }
    printf( "%d回目 比較交換終了時 ", i+1 ); prtData( dt, n );
    }
}

Name: さんb
[URL]
Date: 2017年12月03日(日) 22:43
No: 4
(OFFLINE)

 Re: バブルソートについて

[解決!]

解決しました。
ありがとうございます。

Name: さんb
[URL]
Date: 2017年12月04日(月) 00:25
No: 5
(OFFLINE)

 Re: バブルソートについて

c言語を学んでいます。バブルソートでできるだけ少ない回数でソートを終了するために(本来for (i = 0; i<n-1; i++))
コード[C++]: 全て選択
1
2
3
4
l = 0;
        for (k = n - 1; k = 1; k--) {
            if (dt[k - 1] < dt[k]) {
                l++;

という、昇順になっていたらソート終了するプログラムを付け加えました。
54-3,3-2,2-1,1-0とデータの大きさを比べていき昇順となっていればl=4となりfor (i = 0; l=4; i++) {が終了しソート完了という意味で付け加えました。
実行しても

ソート前 5 4 1 6 2
i:0) 6 と 2 を交換 --> 5 4 1 2 6
i:0) 4 と 1 を交換 --> 5 1 4 2 6
i:0) 5 と 1 を交換 --> 1 5 4 2 6

となります。解決方法を教えてください。よろしくお願いします。

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
 
void prtData(int data[], int n)
{
    int i;
 
    for (i = 0; i < n; i++) printf("%d ", data[i]);
    printf("\n");
}
 
void bubbleSort(int dt[], int n)
{
    int i, j, temp, k, l;
 
    for (i = 0; l=; i++) {
        for (j = n - 1; j > i; j--) {
            if (dt[j - 1] > dt[j]) {
                printf("i:%d) %d と %d を交換", i, dt[j - 1], dt[j]);
                temp = dt[j];
                dt[j] = dt[j - 1];
                dt[j - 1] = temp;
                printf(" --> "); prtData(dt, n);
            }//if
        }//for2
       
        l = 0;
        for (k = n - 1; k = 1; k--) {
            if (dt[k - 1] < dt[k]) {
                l++;
            }
 
        }
 
        printf("%d回目 比較交換終了時 ", i + 1); prtData(dt, n);
    }//for1
}//全体
 
int main()
{
    int data[] = { 5, 4, 1, 6, 2 };
 
    printf("ソート前 "); prtData(data, 5);
    bubbleSort(data, 5);
    printf("ソート後 "); prtData(data, 5);
}

Name: かずま
[URL]
Date: 2017年12月04日(月) 00:30
No: 6
(OFFLINE)

 Re: バブルソートについて


追加の質問の回答は何ですか?
説明をよろしくお願いします。

それから、解決したコード全体を
貼り付けてもらえませんか?

「できるだけ少ない回数でソート」という
条件は実現されていますか?


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[11人]