整列(1)
選択ソート（int 版）
code:selectsort1.c
#include <stdio.h>
void selectsort(int n, int a[]) /* a0..n-1 を昇順に */
{
int i, j, k, min;
for (i = 0; i < n - 1; i++) {
min = ai;
k = i;
for (j = i + 1; j < n; j++) {
if (aj < min) {
min = aj;
k = j;
}
}
ak = ai;
ai = min;
}
}
int main(void)
{
int a[] = { 9, 1, 8, 7, 2, 4, 5 };
int n = sizeof(a) / sizeof(a0);
int i;
selectsort(n, a);
for (i = 0; i < n; i++) {
printf(" %d", ai);
}
printf("\n"); /* 改行だけ出力 */
return 0;
}
選択ソート（int 版，データは乱数で生成）
code:selectsort2.c
#include <stdio.h>
#include <stdlib.h> /* rand() */
void selectsort(int n, int a[]) /* a0..n-1 を昇順に */
{
int i, j, k, min;
for (i = 0; i < n - 1; i++) {
min = ai;
k = i;
for (j = i + 1; j < n; j++) {
if (aj < min) {
min = aj;
k = j;
}
}
ak = ai;
ai = min;
}
}
#define N 20
int aN;
int main(void)
{
int i;
printf("Before:\n");
for (i = 0; i < N; i++) {
ai = rand();
printf("%d\n", ai);
}
selectsort(N, a);
printf("After:\n");
for (i = 0; i < N; i++) {
printf("%d\n", ai);
}
return 0;
}
選択ソート（double 版，データは乱数で生成，時刻で初期化）
code:selectsort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectsort(int n, double a[]) /* a0..n-1 を昇順に */
{
int i, j, k;
double min;
for (i = 0; i < n - 1; i++) {
min = ai;
k = i;
for (j = i + 1; j < n; j++) {
if (aj < min) {
min = aj;
k = j;
}
}
ak = ai;
ai = min;
}
}
#define N 20
double aN;
int main(void)
{
int i;
srand(time(NULL));
printf("Before:\n");
for (i = 0; i < N; i++) {
ai = rand() / (RAND_MAX + 1.0);
printf("%8.6f\n", ai);
}
selectsort(N, a);
printf("After:\n");
for (i = 0; i < N; i++) {
printf("%8.6f\n", ai);
}
return 0;
}
time(NULL) は1970年頭からの秒数（UNIX時刻）を返す。これをタネ（seed）として乱数を初期化している。実際の乱数は rand() で生成される。0以上 RAND_MAX 以下の整数である。
選択ソートの実行時間はほぼ $ n^2 に比例する。このことを $ O(n^2) と書く。
実際の実行時間を調べるには，N をもっと大きくして，値の書き出しをせず，time コマンドを使って測定する：
% time ./a.out
出力される3通りの時間のうち real が実際の時間である。
より正確には，プログラム内に次のように書き足す：
double t1, t2;
t1 = clock();
selectsort(N, a);
t2 = clock();
printf("時間: %g 秒\n", (t2 - t1) / CLOCKS_PER_SEC);
整列は，いちいちプログラムを書かなくても，C言語に備わっている qsort() という関数を使うのが速い。これは汎用に作られているのでちょっとややこしいが，cmp(a, b, 要素のバイト数, 比較関数) の形で呼び出す。要素のバイト数は，int 型なら sizeof(int) で求められる（通常4バイト）。比較関数は，cmp(a,b) の形で呼び出すと $ a<b なら負，$ a>b なら正の整数値を返すような関数である。a，b がもともと整数なら a - b を返せばよい。ただし，型がちょっとややこしい：
code:qsorttest1.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000000
int aN;
int cmp(const void *a, const void *b)
{
return *((int *)a) - *((int *)b);
}
int main(void)
{
double t1, t2;
int i;
srand(time(NULL));
for (i = 0; i < N; i++) {
ai = rand();
}
t1 = clock();
qsort(a, N, sizeof(int), cmp);
t2 = clock();
printf("時間: %g 秒\n", (t2 - t1) / CLOCKS_PER_SEC);
return 0;
}
double 型の場合は次のようになる：
code:qsorttest2.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000000
double aN;
int cmp(const void *a, const void *b)
{
if (*((double *)a) < *((double *)b)) {
return -1;
} else if (*((double *)a) == *((double *)b)) {
return 0;
} else {
return 1;
}
}
int main(void)
{
double t1, t2;
int i;
srand(time(NULL));
for (i = 0; i < N; i++) {
ai = rand() / (RAND_MAX + 1.0);
}
t1 = clock();
qsort(a, N, sizeof(double), cmp);
t2 = clock();
printf("時間: %g 秒\n", (t2 - t1) / CLOCKS_PER_SEC);
return 0;
}
qsort()
time()
C++ では通常の配列 a[0] から a[N-1] までを昇順（小さい順）にソートするには std::sort(a, a+N); だけでよい。降順（大きい順）にソートするには std::sort(a, a+N, std::greater<int>()); とする（int 型の場合）。このあたりは C より C++ のほうが簡単である。#include <iostream> を付ければ，この部分だけCで使うこともできる（gcc ではなく g++ でコンパイルする）。拡張子は .c でもよいが g++ でコンパイルすることを明示するため .cpp とした。
code:qsorttest3.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#define N 1000000
double aN;
int main(void)
{
double t1, t2;
int i;
srand(time(NULL));
for (i = 0; i < N; i++) {
ai = rand() / (RAND_MAX + 1.0);
}
t1 = clock();
std::sort(a, a+N);
t2 = clock();
printf("時間: %g 秒\n", (t2 - t1) / CLOCKS_PER_SEC);
return 0;
}