- なあ、再帰関数好きな人いる？ パート2 [転載禁止]©2ch.net
316 ：デフォルトの名無しさん[sage]：2015/09/12(土) 09:27:37.42 ID:96TVgXwJ - #include <stdio.h>
#define NUM_DATA 8
void ShellSort(int num[ ], int n) ;
void InsSort(int num[ ], int gap, int n);
void ShowData(int num[ ], int n);
void main(void);
/* n 個のデータのシェルソートを行う */
void ShellSort(int num[ ], int n)
{
int gap;
for (gap = n / 2; gap > 0; gap /= 2)
InsSort(num, gap, n);
}
/* n 個のデータの単純挿入ソートを行う */
void InsSort(int num[ ], int gap, int n)
{
int i, j, temp;
for (i = gap; i < n; i ++) {
for (j = i - gap; j >= 0; j -= gap) { /* このループで */
if (num[j] <= num[j + gap]) /* j 番目とj + gap 番目と比較 */
break; /* ここにbreak;を挿入。H.O.さんご指摘ありがとうございました。 */
else {
temp = num[j]; /* 要素の入れ替え */
num[j] = num[j + gap];
num[j + gap] = temp;
ShowData(num, NUM_DATA); /* 途中経過を表示 */
}
}
}
printf("\n"); /* InsSort( ) を抜ける時改行 */
}
| - なあ、再帰関数好きな人いる？ パート2 [転載禁止]©2ch.net
318 ：デフォルトの名無しさん[sage]：2015/09/12(土) 09:30:14.33 ID:96TVgXwJ - #include <stdio.h>
void RadixSort(int x[ ], int n, int r);
void ShowData(int x[ ], int n);
void main(void);
#define NUM_DATA 10
static int rad[NUM_DATA]; /* 基数をしまう配列 */
static int y[NUM_DATA]; /* 作業用配列 */
/* 基数ソートを行う */
void RadixSort(int x[ ], int n, int r) /* x[ ]：ソートするデータ */
{ /* n：データの数 */
int i, j, k; /* r：基数を取り出す最大値 */
int m = 1; /* 基数を取り出す桁 */
while (m <= r) {
for (i = 0; i < n; i++)
rad[i] = (x[i] / m) % 10; /* 基数を取り出し rad[i] に保存 */
k = 0; /* 配列の添字として使う */
for (i = 0; i <= 9; i++) /* 基数は 0 から 9 */
for (j = 0; j < n; j++)
if (rad[j] == i) /* 基数の小さいものから */
y[k++] = x[j]; /* y[ ] にコピー */
for (i = 0; i < n; i++)
x[i] = y[i]; /* x[ ] にコピーし直す */
/* 途中経過を表示 */
printf("\nソート中:\n");
ShowData(x, n);
m *= 10; /* 基数を取り出す桁を一つ上げる */
}
}
| - なあ、再帰関数好きな人いる？ パート2 [転載禁止]©2ch.net
319 ：デフォルトの名無しさん[sage]：2015/09/12(土) 09:30:27.18 ID:96TVgXwJ - /* n 個のデータを表示する */
void ShowData(int x[ ], int n)
{
int i;
for (i = 0; i < n ; i++)
printf("%d\t", x[i]);
}
void main(void)
{ /* ソートするデータ */
int x[NUM_DATA] = { 5489, 1473, 7853, 1058, 9448,
1118, 7979, 2163, 1856, 3117
};
int n = 10; /* ソートするデータ数 */
int r = 1000; /* ソートするデータから取り出す基数の上限 */
/* ソート前のデータを表示 */
printf("ソート前:\n");
ShowData(x, n);
printf("\n");
RadixSort(x, n, r);
/* ソート後のデータを表示 */
printf("\n\nソート後:\n");
ShowData(x, n);
}
| - なあ、再帰関数好きな人いる？ パート2 [転載禁止]©2ch.net
320 ：デフォルトの名無しさん[sage]：2015/09/12(土) 09:30:56.98 ID:96TVgXwJ - #include <stdio.h>
#define MAX_DATA 10
int temp[MAX_DATA]; /* 最小でも配列と同じサイズの領域が必要 */
void MergeSort(int x[ ], int left, int right);
void main(void);
/* 配列 x[ ] の left から right の要素のマージソートを行う */
void MergeSort(int x[ ], int left, int right)
{
int mid, i, j, k;
if (left >= right) /* 配列の要素がひとつなら */
return; /* 何もしないで戻る */
/* ここでは分割しているだけ */
mid = (left + right) / 2; /* 中央の値より */
MergeSort(x, left, mid); /* 左を再帰呼び出し */
MergeSort(x, mid + 1, right); /* 右を再帰呼び出し */
/* x[left] から x[mid] を作業領域にコピー */
for (i = left; i <= mid; i++)
temp[i] = x[i];
/* x[mid + 1] から x[right] は逆順にコピー */
for (i = mid + 1, j = right; i <= right; i++, j--)
temp[i] = x[j];
i = left; /* i とj は作業領域のデーターを */
j = right; /* k は配列の要素を指している */
for (k = left; k <= right; k++) /* 小さい方から配列に戻す */
if (temp[i] <= temp[j]) /* ここでソートされる */
x[k] = temp[i++];
else
x[k] = temp[j--];
}
| - なあ、再帰関数好きな人いる？ パート2 [転載禁止]©2ch.net
321 ：デフォルトの名無しさん[sage]：2015/09/12(土) 09:31:13.83 ID:96TVgXwJ - void main(void)
{
int i;
/* ソートされるデータ */
int x[ ] = {9, 4, 6, 2, 1, 8, 0, 3, 7, 5};
/* ソート前のデータを表示 */
printf("ソート前\n");
for (i = 0; i < MAX_DATA; i++)
printf("%d\t", x[i]);
MergeSort(x, 0, MAX_DATA - 1);
/* ソート後のデータを表示 */
printf("ソート後\n");
for (i = 0; i < MAX_DATA; i++)
printf("%d\t", x[i]);
}
|
|