質問<1764>2004/6/28
この問題をどのようにプログラムを組めばよいのかわかりません。 どうか教えてください。 <問題> n個の値a[0]、a[1]、…、a[n-1]が与えられている時、配列a[ ]を大きさの順 に並び替えたb[ ]を作り出すプログラムをかけ。ただし、プログラムはCまたは BASICのいずれかで書き、プログラム中に使用する名前の型、属性、意味内容を 明示し、用いたアルゴリズムを詳細に説明すること。また、可能な限り実際の 実行例をつけること。
お便り2004/6/30
from=wakky
basicの文法・構文は、しばらくやっていませんので、間違いが多いかと 思いますが、考え方だけで勘弁してください。 まず、a(0)とa(1)~a(n-1)の大小比較をします。 もし、a(k)がa(0)より大きければ、a(k)とa(0)を入れ替えます。 それを繰り返すと、a(0)が最大値になります。 ここで、b(0)=a(0)とすればいいのです。 次に、a(1)とa(2)~a(n-1)の大小比較をします。 もし、a(k)がa(1)より大きければ、a(k)とa(1)を入れ替えます。 b(1)=a(1) これを繰り返すと最終的にb(0)~b(n-1)は大きい順に並べ替えたものになる のだと思います。 他に、配列の中間あたりから、左右に(上下に)比較していく、 クイックソートというアルゴリズムもあるようです。 それで、BASICぽく書くと、 FOR J=0 TO N-2 FOR K=J+1 TO N-1 IF A(K)>=A(J) THEN SWAP(A(K),A(J))) NEXT K B(J)=A(J) NEXT J こんな感じだと思います。
お便り2004/6/30
from=jjon.com
キーワード「整列 プログラム例 C言語」でGoogle検索すると 見つかるでしょう。
お便り2004/6/30
from=naoya
/* bubblesort.c */ /* * 並び替えをしたい型をここで typedef (type) MYKEY と定義する。 */ typedef int MYKEY; /* * 並び替えを行う関数 * sort * 戻り値なし(void) * 引数 b (MYKEY型配列の先頭ポインタ) * ここに並び替え終了後の配列が格納される。 * a (MYKEY型配列の先頭ポインタ) * 並べ替えをしたいキーの格納された配列を指定する。 * n (int型) * 並べ替えを実行する要素の数を指定する。 * アルゴリズム:バブルソート O(n)=n^2 */ void sort(MYKEY b[], MYKEY a[], int n) { int i, j; /* i, jともにループカウンタ */ MYKEY t; /* 要素の交換の時に必要な一時変数 */ for (i = 0; i < n; i++) b[i]=a[i]; for (i = 0; i < n-1; i++) for (j = n-1; j > i; j--) if (b[j-1] < b[j]) { t = b[j]; b[j] = b[j-1]; b[j-1] = t; } } /* * sort関数の実行例 * MYKEY = intの時を仮定 */ #include <stdio.h> int main(void) { MYKEY a[10] = { 5, 8, 4, 2, 9, -5, 1, -1, 0, 7 }, b[10]; int i; sort(b, a, 10); printf(" a b\n"); for (i = 0; i < 10; i++) printf("%-2d:%5d%5d\n", i+1, a[i], b[i]); return 0; } /* * [バブルソートのアルゴリズム] * 配列の後ろから先頭に向かって隣り合う二つずつの大きさを比較 * しながらスキャンし、隣り合う二つの要素の大小関係があるべき * ものと逆である場合に入れ替えを行う。 * k(1<=k<=n-1)回目のスキャンでは、n-1番目の要素からk-1番目 * までの要素をスキャンして、隣り合う二つに対して前述の比較を * 行い、要素の交換を行う。これはつまり、k-1~n-1番目までにあ * る要素の中の最小値あるいは最大値をk-1番目に浮かび上がらせる * 操作である。n-1回のスキャンで操作は全て終了。 */ /* * コメントは面倒なのでつけませんでした。上の解説でわかると思います。 * 整列アルゴリズムはいくつか知っていないと基本的には書けません。 * しかしバブルソートぐらいなら自力で考え出すことが出来ると思います。 * 頑張ってください。 */ (武田談:<と>は全角を使っています。半角だとタグと勘違いして HTML言語が働かないためです。)