整列：ソート（sort）

　ある基準（キーという）でデータの数値の大小順や五十音順に並べ替えることをソーティング（sorting）と言い、 等のアルゴリズムがある。

バブルソート（bubble sort）

　隣接２項間を比較して交換を繰り返す 
/*
	バブル（bubble）ソート
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void swap( int *x, int *y );
void bsort( int n, int buf[] );

main()
{
	disp( num, array );
	bsort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* x と y の場所のデータを入れ替える */
void swap( int *x, int *y )
{
	int	t;

	t = *x;
	*x = *y;
	*y = t;
}

/* バブルソートする */
void bsort( int n, int buf[] )
{
	int	i, j;

	for( i = n-1; i >= 1; i-- )
	{
#ifdef	DEBUG
		disp( num, array );	/* この時点の配列データを表示する */
#endif
		for( j = 0; j < i; j++ )
		{
			if( buf[j] > buf[j+1] )
			{
				swap( &buf[j], &buf[j+1] );
			}
		}
	}
}

/* end of bsort0.c */
  1. 上のプログラムを机上でトレースし、バブルソートのアルゴリズムを理解せよ。
  2. 外側のループ変数 i の右側のデータはソート済みになっていることを確認せよ！
  3. 上のプログラムでは、既に並んでいても、律儀に２重ループを最後まで回しています。 内側のforループの中で一度も隣接２項の交換が起こらなければ、 既にソート済みであることを利用して、高速化を図ってみよ！

選択ソート（selection sort）

　最小値（最大値）を見つけて交換を繰り返す 
/*
	直接選択（straight selection）ソート
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void swap( int *x, int *y );
void ssort( int n, int buf[] );

main()
{
	disp( num, array );
	ssort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* x と y の場所のデータを入れ替える */
void swap( int *x, int *y )
{
	int	t;

	t = *x;
	*x = *y;
	*y = t;
}

/* 選択ソートする */
void ssort( int n, int buf[] )
{
	int	i, j;

	for( i = 0; i < n-1; i++ )
	{
#ifdef	DEBUG
		disp( num, array );	/* この時点の配列データを表示する */
#endif
		for( j = i + 1; j < n; j++ )
		{
			if( buf[i] > buf[j] )
			{
				swap( &buf[i], &buf[j] );
			}
		}
	}
}

/* end of ssort0.c */
  1. 上のプログラムを机上でトレースし、選択ソートのアルゴリズムを理解せよ。
  2. 外側のループ変数 i の左側のデータはソート済みになっていることを確認せよ！
  3. 上のプログラムでは、内側のループでより小さいデータが見つかる度に交換を行っています。 内側のループで最小値を見つけてからその最小値と交換するようにして、交換の回数を減らしてみよ！

挿入ソート（insertion sort）

　部分的にソート済みの中の適切な位置に挿入を繰り返す 
/*
	挿入（indertion）ソート
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void isort( int n, int buf[] );

main()
{
	disp( num, array );
	isort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* 挿入ソートする */
void isort( int n, int buf[] )
{
	int	i, j;
	int	tmp;

	for( i = 1; i < n; i++ )
	{
#ifdef	DEBUG
		disp( num, array );	/* この時点の配列データを表示する */
#endif
		for( tmp = buf[i], j = i; j > 0 && buf[j-1] >= tmp; j-- )
			buf[j] = buf[j-1];
		buf[j] = tmp;
	}
}

/* end of isort.c */
  1. 上のプログラムを机上でトレースし、挿入ソートのアルゴリズムを理解せよ。
  2. 外側のループ変数 i の左側のデータは部分的にソート済みになっていることを確認せよ！

シェルソート（shell sort）

　大きな歩幅 h で飛び飛びに挿入ソートを行う 
/*
	シェル（shell）ソート
	インターバル数列としては h = 3*h + 1 を採用している
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void shsort( int n, int buf[] );

main()
{
	disp( num, array );
	shsort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* シェルソートする */
void shsort( int n, int buf[] )
{
	int	i, j, h;
	int	tmp;

	for( h = 1; h <= n/3; h = h*3+1 );
	for( ; h > 0; h = (h-1)/3 )
	{
#ifdef	DEBUG
		printf("h = %d\n", h );
#endif
		for( i = h; i < n; i++ )
		{
#ifdef	DEBUG
			disp( num, array );	/* この時点の配列データを表示する */
#endif
			for( tmp = buf[i], j = i; j > h-1 && buf[j-h] >= tmp; j-=h )
				buf[j] = buf[j-h];
			buf[j] = tmp;
		}
	}
}
/* end of shsort.c */
  1. 上のプログラムを机上でトレースし、シェルソートのアルゴリズムを理解せよ。
  2. 大きな歩幅 h の挿入ソートがソート済みに近い状態を作り出していることを確認せよ！

クイックソート（quick sort）

　ある値（pivot value）よりも大きな値のグループと小さな値のグループに分割（partition）し、ぞれぞれをまた同様の方法でソートする。いわゆる分割統治法（divide and conquer）を用いた再帰（recursion）的（recursive）方法 
/*
	クイック（quick）ソート
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void swap( int *x, int *y );
void qsort( int n, int buf[] );

main()
{
	disp( num, array );
	qsort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* x と y の場所のデータを入れ替える */
void swap( int *x, int *y )
{
	int	t;

	t = *x;
	*x = *y;
	*y = t;
}

/* クイックソートする */
void qsort( int n, int buf[] )
{
void	qsorts( int left, int right, int buf[] );

#ifdef	DEBUG
	int	i;
	for( i = 0; i < 10; i++ )
		printf(" ");
	printf("index ->");
	for( i = 0; i < n; i++ )
		printf("%3d", i );
	printf("\n");
#endif
	qsorts( 0, n-1, buf );
}

void qsorts( int left, int right, int buf[] )
{
	int	i, j;
	int	mid;
	
	mid = buf[(left+right)/2];
#ifdef	DEBUG
	printf("l=%2d, r=%2d, m=%2d: ", left, right, mid );
	disp( num, array );
#endif
	for( i = left, j = right; i <= j; i++, j-- )
	{
		while( buf[i] < mid )
			i++;
		while( buf[j] > mid )
			j--;
		if( i > j )
			break;
		swap( &buf[i], &buf[j] );
	}
	if( left < j )
		qsorts( left, j, buf );
	if( i < right )
		qsorts( i, right, buf );
}
/* end of qsort.c */
  1. 上のプログラムを机上でトレースし、クイックソートのアルゴリズムを理解せよ。
  2. 分割値（pivot value）midの選び方について考察し、改善しなさい。

マージソート（merge sort）

　２つのソート済み配列をマージ（merge）する。いわゆる分割統治法（divide and conquer）を用いた再帰（recursion）的（recursive）方法 
/*
	マージ（merge）ソート
*/
#include <stdio.h>
#define	ASIZE	100
#define	DEBUG	1

	int	array[ASIZE] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void msort( int n, int buf[] );

main()
{
	disp( num, array );
	msort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* マージソートする */
void msort( int n, int buf[] )
{
void	msorts( int s, int t, int buf[] );
#ifdef  DEBUG
        int     i;
        for( i = 0; i < 10; i++ )
                printf(" ");
        printf("index ->");
        for( i = 0; i < n; i++ )
                printf("%3d", i );
        printf("\n");
#endif
	msorts( 0, n-1, buf );
}

void	msorts( int s, int t, int buf[] )
{
static	int	tbuf[ASIZE];
	int	i, j, m, k;

	m = (s+t+1)/2;
#ifdef	DEBUG
	printf("s=%2d, m=%2d, t=%2d; ", s, m, t );
	disp( num, array );
#endif
	if( s == t )
		return;
	else
	{
		if( s < m-1 )
			msorts( s, m-1, buf );
		if( m < t )
			msorts( m, t, buf );
	}
	for( k = i = s, j = m; i < m && j <= t; )
	{
		if( buf[i] < buf[j] )
			tbuf[k++] = buf[i++];
		else
			tbuf[k++] = buf[j++];
	}
	while( i < m )
		tbuf[k++] = buf[i++];
	while( j <= t )
		tbuf[k++] = buf[j++];
	for( k = s; k <= t; k++ )
		buf[k] = tbuf[k];
}

/* end of msort.c */
  1. 上のプログラムを机上でトレースし、マージソートのアルゴリズムを理解せよ。

ヒープソート（heap sort）

　ヒープ（整列２分木）を使う方法 
/*
	ヒープ（heap）ソート
*/
#include <stdio.h>
#define	DEBUG	1

	int	array[100] = { 18, 2, 11, 7, 19, 17, 16, 5, 13, 10, 20 };
	int	num = 11;

void disp( int n, int buf[] );
void swap( int *x, int *y );
void hsort( int n, int buf[] );

main()
{
	disp( num, array );
	hsort( num, array );
	disp( num, array );
}

/* 配列bufのn個の要素を表示する */
void disp( int n, int buf[] )
{
	int	i;

	for( i = 0; i < n; i++ )
		printf("%3d", buf[i] );
	printf("\n");
}

/* x と y の場所のデータを入れ替える */
void swap( int *x, int *y )
{
	int	t;

	t = *x;
	*x = *y;
	*y = t;
}

void pause()
{
	char	buf;

	printf("Hit Enter Key:");
	scanf("%c", &buf );
}

/* ヒープソートする */
void hsort( int n, int buf[] )
{
extern	void buildheap(int n, int buf[] );
extern	void heapify(int n, int buf[] );

	int	i;

	buildheap( n, buf );
#ifdef	DEBUG
	pause();
#endif
	for( i = n; i > 1; i-- )
	{
#ifdef	DEBUG
		disp( num, array );
#endif
		swap( &buf[(1)-1], &buf[(i)-1] );
		heapify( i-1, buf );
	}
}

void buildheap( int n, int buf[] )
{
extern	void siftdown( int i, int n, int buf[] );

	int	i, j, k;
#ifdef	DEBUG
	printf("start build\n");
#endif
	for( i = n/2; i >= 1; i-- )
	{
		siftdown( i, n, buf );
#ifdef	DEBUG
		disp( num, array );
#endif
	}
#ifdef	DEBUG
	printf("end of build\n");
#endif
}

void siftdown( int i, int n, int buf[] )
{
	int	j;

	for( ; 2*i <= n; i = j )
	{
		if( 2*i == n )
			j = 2*i;
		else /* 2*i + 1 <= n */
		{	
			if( buf[(2*i+1)-1] > buf[(2*i)-1] )
				j = 2*i + 1;
			else
				j = 2*i;
		}
		if( buf[(j)-1] > buf[(i)-1] )
			swap( &buf[(j)-1], &buf[(i)-1] );
		else
			break;	
	}
}

void heapify( int n, int buf[] )
{
extern	void siftdown( int i, int n, int buf[] );

	siftdown( 1, n, buf );
}

/* end of hsort.c */
  1. 上のプログラムを机上でトレースし、ヒープソートのアルゴリズムを理解せよ。

アルゴリズムの比較

  1. 与えられた個数の配列データを乱数で生成せよ
  2. ソーティングに要する時間を計測する工夫をせよ
  3. 100, 200, 300, 400, 500, 600, ...
    という個数のデータに対して各ソーティングの所要時間を調べ、グラフを描いてみよ
    もはやデータの表示は不要！
  4. 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, ...
    という個数のデータに対して各ソーティングの所要時間を調べ、両対数のグラフに描いてみよ
  5. 何が分かったか？