■ ソートのアルゴリズム（平成17年秋午後1問5）
/*
* ソフトウェア開発 平成17年秋午後1問5
* ソートのアルゴリズム
*/
#include <stdio.h>
#define PROGRAM 0
struct {
int point;
char *name;
} d[6] = {
{ 500, "佐藤"},
{ 400, "鈴木"},
{ 450, "高橋"},
{ 450, "田中"},
{ 500, "渡辺"},
{ 450, "伊藤"},
};
int main()
{
const int n = 6;
int i, j, f[801], p[7];
#if PROGRAM == 1
int s[801];
#endif
/* 累積度数を求める処理 */
for (i = 0; i <= 800; i++)
f[i] = 0;
for (j = 0; j < n; j++) {
i = d[j].point;
f[i]++;
}
for (i = 1; i <= 800; i++)
f[i] += f[i-1];
#if PROGRAM == 1
puts("*** プログラム 1 ***");
/* 先頭の位置を決める処理 */
s[0] = 1;
for (i = 1; i <= 800; i++)
s[i] = f[i-1] + 1;
/* データの位置を決める処理 */
for (j = 0; j < n; j++) {
i = d[j].point;
p[s[i]] = j;
s[i]++;
}
#elif PROGRAM == 2
puts("*** プログラム 2 ***");
/* データの位置を決める処理 */
for (j = 0; j < n; j++) {
i = d[j].point;
p[f[i]] = j;
f[i]--;
}
#else
puts("*** プログラム 2 修正 ***");
/* データの位置を決める処理 */
for (j = n - 1; j >= 0; j--) {
i = d[j].point;
p[f[i]] = j;
f[i]--;
}
#endif
/* データを書き出す処理 */
for (j = 1; j <= n; j++)
printf("%d %s\n", d[p[j]].point, d[p[j]].name);
return 0;
}