アルゴリズムとデータ構造：コームソート
コームソートは離れた要素を比較・交換して
徐々に距離（ギャップ）を縮めて行く。
荒い目から細かい目ですいていくように
髪をとかすコームが名前の由来らしい。
[計算量]
なぜか本に書いてない。
wikiには『実行速度は、ほぼO(n log n)』とありますが。。。あとで調べる。
[comb_sort.c]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int count; void CombSort(void); void output(int list[]); void CombSort(void){ int i, temp, flag, gap; gap = N; do { gap = (gap * 10) / 13; if(gap == 0){ gap = 1; } flag = 1; printf("gap:%d\n",gap); for(i = 0; i < N - gap; i++){ printf("sort[%d]:%d > sort[%d]:%d\n",i,sort[i], i+gap, sort[i+gap]); if(sort[i] > sort[i+gap]){ flag = 0; temp = sort[i]; sort[i] = sort[i+gap]; sort[i+gap] = temp; output(sort); } ++count; } } while((gap > 1) || flag != 1); } int main(void){ int i; clock_t start,end; srand((unsigned int) time(NULL)); printf("Stundy...\n"); for(i = 0; i < N; i++){ sort[i] = rand() % 10 + 1; } output(sort); printf("<< Start!! >>\n"); start = clock(); CombSort(); end = clock(); printf("<< End!! >>\n"); printf("Count:%d\n",count); printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC); return EXIT_SUCCESS; } void output(int list[]){ int i=0; printf("sort => ["); while(1){ printf("%d",list[i]); ++i; if(list[i] == '\0') break; else printf(","); } printf("]\n"); }
データ10件で実行したときのログ
[dela@www20328u sort]$ ./comb_sort Stundy... sort => [4,5,9,5,6,9,9,2,8,6] << Start!! >> gap:7 sort[0]:4 > sort[7]:2 sort => [2,5,9,5,6,9,9,4,8,6] sort[1]:5 > sort[8]:8 sort[2]:9 > sort[9]:6 sort => [2,5,6,5,6,9,9,4,8,9] gap:5 sort[0]:2 > sort[5]:9 sort[1]:5 > sort[6]:9 sort[2]:6 > sort[7]:4 sort => [2,5,4,5,6,9,9,6,8,9] sort[3]:5 > sort[8]:8 sort[4]:6 > sort[9]:9 gap:3 sort[0]:2 > sort[3]:5 sort[1]:5 > sort[4]:6 sort[2]:4 > sort[5]:9 sort[3]:5 > sort[6]:9 sort[4]:6 > sort[7]:6 sort[5]:9 > sort[8]:8 sort => [2,5,4,5,6,8,9,6,9,9] sort[6]:9 > sort[9]:9 gap:2 sort[0]:2 > sort[2]:4 sort[1]:5 > sort[3]:5 sort[2]:4 > sort[4]:6 sort[3]:5 > sort[5]:8 sort[4]:6 > sort[6]:9 sort[5]:8 > sort[7]:6 sort => [2,5,4,5,6,6,9,8,9,9] sort[6]:9 > sort[8]:9 sort[7]:8 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:5 sort[1]:5 > sort[2]:4 sort => [2,4,5,5,6,6,9,8,9,9] sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:9 sort[6]:9 > sort[7]:8 sort => [2,4,5,5,6,6,8,9,9,9] sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:4 sort[1]:4 > sort[2]:5 sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:8 sort[6]:8 > sort[7]:9 sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 << End!! >> Count:41 Time:0.00 [dela@www20328u sort]$ ./comb_sort Stundy... sort => [4,5,9,5,6,9,9,2,8,6] << Start!! >> gap:7 sort[0]:4 > sort[7]:2 sort => [2,5,9,5,6,9,9,4,8,6] sort[1]:5 > sort[8]:8 sort[2]:9 > sort[9]:6 sort => [2,5,6,5,6,9,9,4,8,9] gap:5 sort[0]:2 > sort[5]:9 sort[1]:5 > sort[6]:9 sort[2]:6 > sort[7]:4 sort => [2,5,4,5,6,9,9,6,8,9] sort[3]:5 > sort[8]:8 sort[4]:6 > sort[9]:9 gap:3 sort[0]:2 > sort[3]:5 sort[1]:5 > sort[4]:6 sort[2]:4 > sort[5]:9 sort[3]:5 > sort[6]:9 sort[4]:6 > sort[7]:6 sort[5]:9 > sort[8]:8 sort => [2,5,4,5,6,8,9,6,9,9] sort[6]:9 > sort[9]:9 gap:2 sort[0]:2 > sort[2]:4 sort[1]:5 > sort[3]:5 sort[2]:4 > sort[4]:6 sort[3]:5 > sort[5]:8 sort[4]:6 > sort[6]:9 sort[5]:8 > sort[7]:6 sort => [2,5,4,5,6,6,9,8,9,9] sort[6]:9 > sort[8]:9 sort[7]:8 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:5 sort[1]:5 > sort[2]:4 sort => [2,4,5,5,6,6,9,8,9,9] sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:9 sort[6]:9 > sort[7]:8 sort => [2,4,5,5,6,6,8,9,9,9] sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 gap:1 sort[0]:2 > sort[1]:4 sort[1]:4 > sort[2]:5 sort[2]:5 > sort[3]:5 sort[3]:5 > sort[4]:6 sort[4]:6 > sort[5]:6 sort[5]:6 > sort[6]:8 sort[6]:8 > sort[7]:9 sort[7]:9 > sort[8]:9 sort[8]:9 > sort[9]:9 << End!! >> Count:41 Time:0.00
データ1万件の結果
Stundy... << Start!! >> << End!! >> Count:286738 Time:0.00
データ100万件の結果
Stundy... << Start!! >> << End!! >> Count:46666765 Time:0.26
データ1億件の結果
Stundy... << Start!! >> << End!! >> Count:-2023267793 Time:33.89
速い。
コームソート、クイックソートは不安定ソート。
マージソートは安定ソート。
[安定ソート]
- 同等の値があった場合、それらの入れ替えが発生しない。
- 同等なデータのソート前の順序が、ソート後も保存される。
- ソート途中の各状態において、常に順位の位置関係を保っている。
[不安定ソート]
- 同等の値があった場合、それらの入れ替えが発生する可能性がある。
例は名と姓でソートする場合に、通常は姓でソートした後に名でソートする。
同じ姓があった場合、名の方でも五十音順にソートできている。不安定ソートは五十音順に並ばない。
[内部ソート]
ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソート
[外部ソート]
ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソート
