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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: ｃ言語の初歩的質問です。

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

#3

by かずま » 7年前

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

さて、i のループの回数を減らしてみました。

コード: 

#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ずつ増えるのではなく、
一度も交換が行われなかった場合、ソートはすぐに終了します。

実行結果

コード: 

 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つシフトされるだけなのが
わかります。

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

#2

by さんｂ » 7年前

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

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

#1

by さんｂ » 7年前

ｃ言語を学んでいます。バブルソートでできるだけ少ない回数でソートを終了するために(本来for (i = 0; i<n-1; i++))

コード: 

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=４; 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

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

コード: 

#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]

ページトップ