ソート

ソート（英語：sort）とは、一連のデータをある一定の順序に従って並べ替える処理である。

主なソートアルゴリズム

実装例は、整数を昇順に並べ替えるものを示す。

バブルソート

バブルソートは最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。

void sort(int a[], int num) {
	int i, j, t;
	for ( j = num - 1; j > 0; j-- ) {
		for ( i = 0; i < j; i++ ) {
			if ( a[i] > a[i+1] ) {
				t = a[i];
				a[i] = a[i+1];
				a[i+1] = t;
		        }
		}
	}
}

枝刈りによる、もう少し効率の良い実装も存在する。

挿入ソート

挿入ソートは、これまで並べ替えた部分に、その直後の要素を目標の順序に合う位置に挿入する。 通常はバブルソートと同じ計算量とみなされるが、ソート済みの配列をソートする場合に高速。

void sort(int a[],int num) {
	int i,j,pos,temp;
	for(i=1;i<num;i++) {
		for(pos=i;pos>0 && a[pos-1]>a[i];pos--);
		temp=a[i];
		for(j=i-1;j>=pos;j--)a[j+1]=a[j];
		a[pos]=temp;
	}
}

ヒープソート

ヒープソートは、要素を一旦全てヒープに放り込み、根の要素を順に取り出すことによりソートする。 実装が若干複雑な割にあまり高速ではない。

void sort(int a[],int num) {
	int i,pos;
	int left,right;
	int temp;
	for(i=1;i<num;i++) {
		pos=i;
		while(1) {
			left=pos*2+1;
			if(left<=i) {
				right=(left<i)?left+1:left;
				if(a[left]>a[right]) {
					if(a[pos]<a[left]) {
						temp=a[left];
						a[left]=a[pos];
						a[pos]=temp;
						pos=left;
					} else {
						if(pos==0)break;
						pos=(pos-1)/2;
					}
				} else {
					if(a[pos]<a[right]) {
						temp=a[right];
						a[right]=a[pos];
						a[pos]=temp;
						pos=right;
					} else {
						if(pos==0)break;
						pos=(pos-1)/2;
					}
				}
			} else {
				if(pos==0)break;
				pos=(pos-1)/2;
			}
		}
	}
	for(i=num-1;i>0;i--) {
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		pos=0;
		while(pos*2+1<i) {
			left=pos*2+1;
			right=(left+1<i)?left+1:left;
			if(a[left]>a[right]) {
				if(a[pos]<a[left]) {
					temp=a[left];
					a[left]=a[pos];
					a[pos]=temp;
					pos=left;
				} else break;
			} else {
				if(a[pos]<a[right]) {
					temp=a[right];
					a[right]=a[pos];
					a[pos]=temp;
					pos=right;
				} else break;
			}
		}
	}
}

シェルソート

シェルソートは、挿入ソートに似ているが、初めは広い間隔でソートを行い、徐々に間隔を狭くしていく。 クイックソートの登場前は最速のソートと言われていたらしい。

void sort(int a[],int num) {
	int width;
	int i,j,k;
	int temp;
	for(width=1;width*3+1<num;width=width*3+1);
	for(;width>0;width/=3) {
		for(i=0;i<width;i++) {
			for(j=i;j<num;j+=width) {
				temp=a[j];
				for(k=j-width;k>=i && a[k]>temp;k-=width) {
					a[k+width]=a[k];
				}
				a[k+width]=temp;
			}
		}
	}
}

マージソート

マージソートは、配列を短く分割し、徐々に併合していくことでソートを行う。 キャラソートでも採用されているらしい。

Haskellでの記述例

mergeinternal [] [] = []
mergeinternal a [] = a
mergeinternal [] b = b
mergeinternal a b =if (head a)<=(head b) then (head a):(mergeinternal (drop 1 a) b)
                                         else (head b):(mergeinternal a (drop 1 b))

mergesort [] = []
mergesort [a] = [a]
mergesort l = mergeinternal
    (mergesort (take (div (length l) 2) l)) (mergesort (drop (div (length l) 2) l))

クイックソート

クイックソートは、まず要素の中から適当にピポットと呼ばれる基準値を設定し、ピポット未満の要素とピポット以上の要素に分ける。 分けた要素をそれぞれ同じようにソートし、ピポット未満の要素をソートしたものの後ろにピポット以上の要素をソートしたものをくっつける。

データと実装によっては遅くなることがあるが、いくつかの改善法がある。

Haskellでの記述例

qsort ls = if (null ls) then [] else
    (qsort.(filter (<(head ls))) $ ls)++
    (filter (==(head ls)) ls)++
    (qsort.(filter (>(head ls))) $ ls)

基数ソート

基数ソートは、小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。 データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。

void sort(unsigned int a[],int num) {
	unsigned int* internal_buffer=new unsigned int[num];
	int counter[256];
	unsigned int *src,*dest,*temp;
	int i,j;
	src=a;dest=&internal_buffer[0];
	for(i=0;i<32;i+=8) {
		std::fill(&counter[0],&counter[256],0);
		for(j=0;j<num;j++) {
			counter[(src[j]>>i)&0xFF]++;
		}
		for(j=1;j<256;j++) {
			counter[j]+=counter[j-1];
		}
		for(j=num-1;j>=0;j--) {
			dest[--counter[(src[j]>>i)&0xFF]]=src[j];
		}
		temp=src;src=dest;dest=temp;
	}
	delete[] internal_buffer;
}

スリープソート

スリープソートはソートの最終系と言われるアルゴリズムである。

詳細は「スリープソート」の項目を参照。

関連項目

• アルゴリズム