合計 昨日 今日

c言語の初歩的質問です。

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

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

 c言語の初歩的質問です。

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);
}
[/quote]

Name: さんb
[URL]
Date: 2017年12月04日(月) 01:34
No: 2
(OFFLINE)

 Re: c言語の初歩的質問です。

[解決!]

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

Name: かずま
[URL]
Date: 2017年12月04日(月) 08:33
No: 3
(OFFLINE)

 Re: c言語の初歩的質問です。

何が悪かったのか?
どのようにして解決したのかを書いてください。
フォーラムルールに従ってください。

さて、i のループの回数を減らしてみました。
コード[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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 10
 
void print(int a[], int n)
{
    for (int i = 0; i < n; i++) printf(" %d", a[i]);
    putchar('\n');
}
 
void sort(int a[], int n)
{
    int i, j, k, temp;
    for (i = 0; i < n - 1; i = k) {
        k = n - 1;
        for (j = n - 1; j > i; j--) {
            if (a[j-1] > a[j]) {
                temp = a[j-1], a[j-1] = a[j], a[j] = temp;
                k = j;
            }
        }
        printf("[i=%d, k=%d]", i, k), print(a, n); 
    }
}
 
int main(void)
{
    int a[N] = { 1, 2, 4, 6, 4, 7, 9, 8, 7, 9 };
    int b[N] = { 9, 8, 7, 4, 5, 6, 3, 2, 1, 0 };
 
    print(a, N);   
    sort(a, N);
    print(a, N);   
    sort(a, N);
    print(a, N);   
    print(b, N);
    sort(b, N);
    print(b, N);
}

内側のループで最後に交換の起こった場所を憶えておくと、
それ以前はソート済みなので、次回は後ろからそこまでを
スキャンすれば良いことになり、i が 1ずつ増えるのではなく、
一度も交換が行われなかった場合、ソートはすぐに終了します。

実行結果
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 1 2 4 6 4 7 9 8 7 9
[i=0, k=4] 1 2 4 4 6 7 7 9 8 9
[i=4, k=8] 1 2 4 4 6 7 7 8 9 9
[i=8, k=9] 1 2 4 4 6 7 7 8 9 9
 1 2 4 4 6 7 7 8 9 9
[i=0, k=9] 1 2 4 4 6 7 7 8 9 9
 1 2 4 4 6 7 7 8 9 9
 9 8 7 4 5 6 3 2 1 0
[i=0, k=1] 0 9 8 7 4 5 6 3 2 1
[i=1, k=2] 0 1 9 8 7 4 5 6 3 2
[i=2, k=3] 0 1 2 9 8 7 4 5 6 3
[i=3, k=4] 0 1 2 3 9 8 7 4 5 6
[i=4, k=5] 0 1 2 3 4 9 8 7 5 6
[i=5, k=6] 0 1 2 3 4 5 9 8 7 6
[i=6, k=7] 0 1 2 3 4 5 6 9 8 7
[i=7, k=8] 0 1 2 3 4 5 6 7 9 8
[i=8, k=9] 0 1 2 3 4 5 6 7 8 9
 0 1 2 3 4 5 6 7 8 9

後ろからスキャンするので、1回のスキャンで、
一番小さいものは先頭に出ますが、
一番大きいものは 1つシフトされるだけなのが
わかります。


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

オンラインデータ

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