/*********************************/ /* ソート(並べ替え) */ /* バブルソート */ /* 選択ソート */ /* クイックソート */ /* バケツソート */ /* 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; }