ソートアルゴリズムの実装 - メモ帳ブログ @ wiki

ソートアルゴリズムの実装

このページを編集

バブルソート

もっとも直感的なソートアルゴリズム

void BubbleSort(int data[], const int len){
  for(int max = len-1; max > 0; --max){
    for(int k = 0; k < max; ++k){
      if(data[k] > data[k+1]){
        int tmp;
        tmp = data[k+1];
        data[k+1] = data[k];
        data[k] = tmp;
      }
    }
  }
} 

セレクションソート

バブルソートの改良版

void SelectionSort(int data[], const int len){
  int m, tmp;
  for(int max = len; max > 0; --max){
    m = 0;
    for(int k = 1; k < max; ++k){
      if(data[m] > data[k]){
        m = k;
      }
    }
    tmp = data[max];
    data[max] = data[m];
    data[m] = tmp;
  }
} 

クイックソート

実用上で最も早い

void QuickSort(int data[], const int low, const int high){
    if(low < high){
        // ピボットの決定
        int x = (data[low] + data[high] + data[(low+high)/2])/3;
 
        int left = low - 1, right = high + 1;
        while(left <= right){
            while(data[++left] < x);
            while(data[--right] > x);
            if(left < right) Swap(&data[left], &data[right]);
        }
        QuickSort(data, low, right);
        QuickSort(data, left, high);
    }
} 

各アルゴリズムの実行時間（実測）

以下は課題でソートにかかる時間を実測した結果である。なお、当時のCPU利用時間制限上、ソートに3分以上かかる物については-と表記した。

データ数	バブルソート	セレクションソート	クイックソート	基数ソート
10000	1.207	0.698	0.003	0.005
20000	4.830	2.790	0.006	0.011
30000	10.85	6.281	0.009	0.018
40000	19.31	11.16	0.012	0.022
50000	30.18	17.44	0.015	0.028
60000	43.49	25.18	0.018	0.034
70000	59.22	34.25	0.021	0.041
80000	77.49	44.88	0.025	0.045
90000	98.25	57.25	0.028	0.054
100000	121.3	70.22	0.031	0.057
200000	-	-	0.065	0.115
300000	-	-	0.099	0.172
400000	-	-	0.134	0.228
500000	-	-	0.169	0.290
600000	-	-	0.206	0.343
700000	-	-	0.255	0.406
800000	-	-	0.290	0.467
900000	-	-	0.347	0.541
1000000	-	-	0.358	0.649

---

カテゴリ：C/C++