ソート速度比較
最近C言語にあまり触っておらず、忘れそうだったのでCを使ったのと、
これから卒業研究でもおそらくCを使うので、リハビリとしていろいろなソートを実装してみました。
ついでに速度比較も。
選択ソート
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int main(){ int *array; int i,j; int tmp; int min; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } for( i=0; i<SIZE;i++){ min=i; for(j=i+1;j<SIZE;j++){ if(array[min]>array[j]){ min = j; } } tmp = array[i]; array[i] = array[min]; array[min] = tmp; } for( i=0; i < SIZE; i++) printf("%d \n",array[i]); }
バブルソート
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int main(){ int *array; int i,j; int tmp; int flag; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } for( i=0; i<SIZE;i++){ flag=0; for(j=0;j<SIZE-i-1;j++){ if(array[j]>array[j+1]){ tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flag=1; } } if(!flag) break; } for( i=0; i < SIZE; i++) printf("%d \n",array[i]); }
シェーカーソート
バブルソートを改良したようなものです。
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int main(){ int *array; int i,j; int right,left,last_swap_index; int tmp; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } right=SIZE-1; left=0; while(right>left){ for(i=left;i<right;i++){ if(array[i]>array[i+1]){ tmp = array[i]; array[i] = array[i+1]; array[i+1] = tmp; last_swap_index=i; } } right = last_swap_index; for(i=right;i>left;i--){ if(array[i]<array[i-1]){ tmp=array[i]; array[i] = array[i-1]; array[i-1] = tmp; last_swap_index=i; } } left = last_swap_index; } for( i=0; i < SIZE; i++) printf("%d \n",array[i]); }
挿入ソート
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int main(){ int *array; int i,j; int tmp; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } for( i=1; i<SIZE;i++){ tmp=array[i]; if(array[i-1]>tmp) { j=i; do{ array[j]=array[j-1]; j--; }while(j>0 && array[j-1] > tmp); array[j] = tmp; } } for( i=0; i < SIZE; i++) printf("%d \n",array[i]); }
ヒープソート
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 10 void HeapSort(int *, int); void DownHeap(int * , int , int ); int main() { int *array; int i; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for(i=0;i<SIZE;i++) array[i] = rand(); HeapSort(array,SIZE-1); for(i=0;i<SIZE;i++) printf( "%d\n",array[i]); return 0; } void HeapSort(int *array, int n){ int leaf,root; int tmp; leaf = n; root = n/2; while(root>=0){ DownHeap(array,leaf,root); root--; } while(leaf>=0){ tmp = array[0]; array[0] = array[leaf]; array[leaf] = tmp; leaf--; DownHeap(array,leaf,0); } } void DownHeap(int *array,int leaf , int root){ int i; int tmp; i = root*2+1; while(i <=leaf){ if(i<leaf && array[i+1]>array[i]) i++; if(array[root] >= array[i]) break; tmp = array[root]; array[root] = array[i]; array[i]=tmp; root = i; i=root*2+1; } }
クイックソート
最速と言われているソートです。
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 void quickSort(int* array ,int ,int ); int main(){ int *array; int i; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } quickSort(array,0,SIZE-1); for( i=0; i < SIZE; i++) printf("%d \n",array[i]); } void quickSort(int* array, int min, int max){ int mid,key,i,j,tmp; if(min<max){ mid = (min+max)/2; key = array[mid]; i = min; j = max; do{ while(array[i]<key) i++; while(array[j]>key) j--; if(i <=j){ tmp = array[i]; array[i++] = array[j]; array[j--] = tmp; } }while(i<=j); quickSort(array,min,j); quickSort(array,i,max); } }
マージソート
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int* tmp; void MergeSort(int* array ,int ,int ); int main(){ int *array; int i; array = (int*)malloc(sizeof(int)*SIZE); tmp = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } MergeSort(array,0,SIZE-1); for( i=0; i < SIZE; i++) printf("%d \n",array[i]); } void MergeSort(int* array, int left, int right){ int mid,i,j,k; if(left>=right) return; mid = (left+right)/2; MergeSort(array,left,mid); MergeSort(array,mid+1,right); for(i=left; i<=right;i++) tmp[i] = array[i]; i = left; j = mid+1; for(k=left; k<=right &&i<=mid && j <= right ;k++){ if(tmp[i] <= tmp[j]) array[k]=tmp[i++]; else array[k] = tmp[j++]; } while(i <=mid){ array[k++] = tmp[i++]; } }
シェルソート
挿入ソートを改良したアルゴリズムです。
#include <stdio.h> #include <time.h> #include <stdlib.h> #define SIZE 10 int main(){ int *array; int i,j; int h; int tmp; array = (int*)malloc(sizeof(int)*SIZE); srand((unsigned)time(NULL)); for( i=0; i < SIZE; i++){ array[i] = rand(); } while(h<SIZE) h=2.25*h+1; while(h>1){ h=h/2.25; for(i=h;i<SIZE;i++){ tmp = array[i]; if(array[i-h]>tmp){ j=i; do{ array[j] = array[j-h]; j-=h; }while(j>h && array[j-h] > tmp); array[j] = tmp; } } } for( i=0; i < SIZE; i++) printf("%d \n",array[i]); }
今日はソースだらけですね。
解説はあまり書きませんが、選択ソート、バブルソート、挿入ソート、シェーカーソートはO(N*N)です。
ヒープソート、クイックソート、マージソートはO(N*logN)
シェルソートはO(N^1.25)といわれています。
実行時間の比較のグラフを作ったので見てもらうと速さの違いがわかると思います。
やはりバブルソートが一番遅いです。
挿入ソートも割と早いですね。
同じO（n^2）のアルゴリズムでもかなり差があります。
O（nlogn）とシェルソート(O(n^1.25))のものはこの要素数ではほとんど実行時間がかかりませんでした。
O(nlogn)とO(n^1.25)のアルゴリズムについてはもっと要素数を大きくした物を別にグラフを作りました。
O(n^1.25)のシェルソートがおもったより早いです。
ヒープソートよりも早いという結果に。ヒープソートはもっといいコードの書き方があるかも。
そしてやはりクイックソートは早いですね。
そんなクイックソートも実は要素数が少ない場合は挿入ソートのほうが早いらしい。
そのためクイックソートの途中の部分配列が十分小さくなったら挿入ソートを用いて最適化することもできる。
ヒープソートは少し遅いが最悪時でも計算量はO(n logn)なので、クイックソートの最悪時であるO（n^2）を避けることができる。
ただ並び替えをするアルゴリズムだけでもいろいろな種類があり、速さに差があるのは知っていましたが、実際に書いて自分で実査に速度を測ってみてどの程度の差があるかというのを実感できました。
