ソート(並べ替え)

  各ソートを行う関数は通常の関数として書いてあります.配列の引き渡し方法に注意して下さい.
/*********************************/
/* ソート(並べ替え)            */
/*      バブルソート             */
/*      選択ソート               */
/*      クイックソート           */
/*      バケツソート             */
/*           coded by Y.Suganuma */
/*********************************/
#include <stdio.h>

/************************/
/* データの比較(昇順) */
/* a > bの場合に真      */
/************************/
bool ascend(int a, int b)
{
	return a > b;
}

/************************/
/* データの比較(降順) */
/* a < bの場合に真      */
/************************/
bool descend(int a, int b)
{
	return a < b;
}

/*************************************/
/* 2つのデータを交換する            */
/*      a,b : 2つのデータのアドレス */
/*************************************/
void swap(int *a, int *b)
{
	int temp = *a;
	*a       = *b;
	*b       = temp;
}

/*****************************************************************/
/* バブルソート                                                  */
/*      n : データの数                                           */
/*      data : データ                                            */
/*      cmp : ソート方向(0:昇順,1:降順)                       */
/* バブルソートの手順                                            */
/*     1)配列data[i]にn個のデータが入っているものとする.   */
/*        i=0,1,・・・,n-1                                  */
/*     2)i番目のデータとi+1番目のデータを比較し,もし,     */
/*        data[i+1] < data[i] (昇順の場合)            */
/*      であればそれらのデータを交換する. i=0,1,・・・,n-2  */
/*        →この結果,data[n-1]に最も大きなデータが入る  */
/*              ことになる                                       */
/*     3)次に,n-1個のデータに対し上の処理を繰り返す.      */
/*     4)同様に,n-2,n-3,・・・個のデータに対して同じ処理 */
/*        を繰り返す                                             */
/*****************************************************************/
void bubble(int n, int *data, int cmp)
{
	int sw = 0;
	if (n > 1) {
		for (int i1 = 0; i1 < n-1; i1++) {
			bool bl = (cmp == 0) ? ascend(data[i1], data[i1+1]) :
                                   descend(data[i1], data[i1+1]);
			if (bl) {
				sw = 1;
				swap(&data[i1], &data[i1+1]);
			}
		}
	}

	if (sw > 0)
		bubble(n-1, data, cmp);
}

/************************************************************/
/* 選択ソート                                               */
/*      n : データの数                                      */
/*      data : データ                                       */
/*      cmp : ソート方向(0:昇順,1:降順)                  */
/* 選択ソートの手順                                         */
/* (昇順の場合).まず配列を走査して,最も小さな要素を見つ */
/* けだす.見つけたら,それを配列の先頭要素と交換する.この */
/* 操作を配列の2番目の要素から始まるサブ配列について繰り返す*/
/************************************************************/
void select(int n, int *data, int cmp)
{
	if (n > 1) {

		int m = 0;
		for (int i1 = 1; i1 < n; i1++) {
			bool bl = (cmp == 0) ? ascend(data[m], data[i1]) :
                                   descend(data[m], data[i1]);
			if (bl)
				m = i1;
		}

		if (m != 0)
			swap(&data[0], &data[m]);

		select(n-1, &data[1], cmp);
	}
}

/*****************************************************************/
/* クイックソート                                                */
/*      n : データの数                                           */
/*      data : データ                                            */
/*      cmp : ソート方向(0:昇順,1:降順)                       */
/* クイックソートの手順                                          */
/*      次のようなデータが与えられたとする.このとき,左端 */
/*        のデータ( 37 )を枢軸要素と呼び,個の要素がソート     */
/*        後の正しい位置にくるように以下の処理を行う(昇順の     */
/*        場合).                                               */
/*       37  2  6  4  89  8  10  12  68  45               */
/*     1)配列の右端の要素から順に枢軸要素(37)と比較していき */
/*        37より小さな要素があれば,その要素を37と交換する.     */
/*       12  2  6  4  89  8  10  37  68  45               */
/*     2)配列の左端(正確には,12の直後の要素)から順に枢軸 */
/*        要素(37)と比較していき,37より大きな要素があれば,     */
/*        その要素を37と交換する.                               */
/*       12  2  6  4  37  8  10  89  68  45               */
/*     3)配列の右端(正確には,89の直前の要素)から順に枢軸 */
/*        要素(37)と比較していき,37より小さな要素があれば,     */
/*        その要素を37と交換する.                               */
/*       12  2  6  4  10  8  37  89  68  45               */
/*     4)以上の結果,37の左には37より大きな要素はなく,また */
/*        その右側には37より小さな要素は無い状態となる.つま     */
/*        り,37は,ソート後の正しい位置にあることがわかる.     */
/*     5)37の左側の配列(12  2  6  4  10  8),及び,右側の */
/*        配列(89  68  45)に対して以上の処理を再帰的に繰り     */
/*        返す.                                                 */
/*****************************************************************/
void quick(int n, int *data, int cmp)
{
	int left = 1, right = n-1, pos = 0, sw1 = 1, sw2;
/*
          枢軸要素を正しい位置に置く
*/
	while (sw1 > 0) {

		sw1 = 0;

		if (right-pos > 0) {
			sw2 = 0;
			for (int i1 = right; i1 > pos && sw2 == 0; i1--) {
				bool bl = (cmp == 0) ? ascend(data[pos], data[i1]) :
    	                               descend(data[pos], data[i1]);
				if (bl) {
					swap(&data[pos], &data[i1]);
					sw1   = 1;
					sw2   = 1;
					pos   = i1;
					right = i1 - 1;
				}
			}
		}

		if (pos-left > 0) {
			sw2 = 0;
			for (int i1 = left; i1 < pos && sw2 == 0; i1++) {
				bool bl = (cmp == 0) ? ascend(data[i1], data[pos]) :
    	                               descend(data[i1], data[pos]);
				if (bl) {
					swap(&data[pos], &data[i1]);
					sw1   = 1;
					sw2  = 1;
					pos  = i1;
					left = i1 + 1;
				}
			}
		}

		if (right-pos <= 0)
			sw1 = 0;
	}
/*
          サブ配列の処理
*/
	if (pos > 1)
		quick(pos, data, cmp);
	if (pos < n-2)
		quick(n-1-pos, &data[pos+1], cmp);
}

/*****************************************************************/
/* バケツソート                                                  */
/*      n : データの数                                           */
/*      data : データ                                            */
/*      cmp : ソート方向(0:昇順,1:降順)                       */
/*      k : 桁                                                   */
/*      bu : バケツ                                              */
/*      num : 各バケツに入っているデータ数                       */
/* バケツソートとは,一次元配列に入っているn個の正の整数を      */
/* バケツ配列と呼ばれる10×(n-1)の二次元配列を使用してソート     */
/* する方法であり,以下に示すような手続きに従う.                */
/*     1)一次元配列の各数値を一の位に基づいてバケツ配列の対 */
/*        応する各行に格納する.たとえば,一次元配列の中に数     */
/*        値97,3,100がこの順序で入っていたとすると,97は行     */
/*        7,3は行3,100は行0に格納される.これを「分配パス      */
/*        」と呼ぶ.                                             */
/*     2)バケツ配列の各行に格納されている値を行0から順番に  */
/*        元の一次元配列の戻す.これを「収集パス」という.こ     */
/*        の時点で,一次元配列の中の値は100,3,97の順序にな     */
/*        る.                                                   */
/*     3)以上の処理を数値の各位について繰り返す.           */
/*****************************************************************/
void bucket(int n, int *data, int cmp, int k, int **bu, int *num)
{
/*
     準備
*/
	int kk = 1;
	for (int i1 = 0; i1 < k-1; i1++)
		kk *= 10;
	for (int i1 = 0; i1 < 10; i1++)
		num[i1] = 0;
/*
     分配パス
*/
	int sw1 = 1, sw2 = 0;
	for (int i1 = 0; i1 < n; i1++) {
		if (data[i1] >= 10*kk)
			sw2 = 1;
		int k1 = (data[i1] / kk) % 10;
		if (num[k1] >= n-1)
			sw1 = 0;
		else {
			bu[k1][num[k1]] = data[i1];
			num[k1]++;
		}
	}
/*
     収集パス
*/
	if (sw1 > 0) {
		int k1 = 0;
		if (cmp == 0) {
			for (int i1 = 0; i1 < 10; i1++) {
				for (int i2 = 0; i2 < num[i1]; i2++) {
					data[k1] = bu[i1][i2];
					k1++;
				}
			}
		}
		else {
			for (int i1 = 9; i1 >= 0; i1--) {
				for (int i2 = 0; i2 < num[i1]; i2++) {
					data[k1] = bu[i1][i2];
					k1++;
				}
			}
		}
	}
/*
     次の桁
*/
	if (sw2 > 0)
		bucket(n, data, cmp, k+1, bu, num);
}

/*******************/
/* main プログラム */
/*******************/
int main()
{
	int i1, n, *data, sw;
					// データの入力
	printf("方法は(0:バブル, 1:選択, 2:クイック, 3: バケツ)? ");
	scanf("%d", &sw);
	printf("データの数は? ");
	scanf("%d", &n);

	data = new int [n];

	for (i1 = 0; i1 < n; i1++) {
		printf("   %d 番目のデータは? ", i1+1);
		scanf("%d", &data[i1]);
	}

					// ソートの実行
	int *num  = new int [10];
	int **bu   = new int * [10];
	for (int i1 = 0; i1 < 10; i1++)
		bu[i1] = new int [n-1];

	switch (sw) {
		case 0:      // バブルソート
			bubble(n, data, 0);
			printf("昇順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			bubble(n, data, 1);
			printf("降順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			break;
		case 1:      // 選択ソート
			select(n, data, 0);
			printf("昇順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			select(n, data, 1);
			printf("降順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			break;
		case 2:      // クイックソート
			quick(n, data, 0);
			printf("昇順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			quick(n, data, 1);
			printf("降順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			break;
		case 3:      // バケツソート
			bucket(n, data, 0, 1, bu, num);
			printf("昇順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			bucket(n, data, 1, 1, bu, num);
			printf("降順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			break;
		default:
			bubble(n, data, 0);
			printf("昇順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			bubble(n, data, 1);
			printf("降順\n  ");
			for (int i1 = 0; i1 < n; i1++)
				printf(" %d", data[i1]);
			printf("\n");
			break;
	}

	delete [] num;
	for (int i1 = 0; i1 < 10; i1++)
		delete [] bu[i1];
	delete [] bu;

	return 0;
}