「ソート」を編集中

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

==主なソート[[アルゴリズム]]==
実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。
===バブルソート===
最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。
<source lang="c">
void sort(int a[],int num) {
	int i,j;
	for(j=num-1;j>0;j--) {
		for(i=0;i<j;i++) {
			if(a[i]>a[i+1]) {
				int temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
		}
	}
}
</source>
[[枝刈り]]による、もう少し効率の良い実装も存在する。

===挿入ソート===
これまで並べ替えた部分に、その直後の要素を目標の順序に合う位置に挿入する。
通常はバブルソートと同じ[[計算量]]とみなされるが、ソート済みの配列をソートする場合に高速。
<source lang="c">
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;
	}
}
</source>

===ヒープソート===
要素を一旦全てヒープに放り込み、根の要素を順に取り出すことによりソートする。
実装が若干複雑な割にあまり高速ではない。
<source lang="c">
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;
			}
		}
	}
}
</source>

===シェルソート===
挿入ソートに似ているが、初めは広い間隔でソートを行い、徐々に間隔を狭くしていく。
クイックソートの登場前は最速のソートと言われていたらしい。
<source lang="c">
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;
			}
		}
	}
}
</source>

===マージソート===
配列を短く分割し、徐々に併合していくことでソートを行う。
[[キャラソート]]でも採用されているらしい<ref>http://marineturtle.sakura.ne.jp/script/sort/hpsort/mergesort_exp.html</ref>。

[[Haskell]]での記述例
<source lang="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))
</source>

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

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

[[Haskell]]での記述例
<source lang="haskell">
qsort ls = if (null ls) then [] else
    (qsort.(filter (<(head ls))) $ ls)++
    (filter (==(head ls)) ls)++
    (qsort.(filter (>(head ls))) $ ls)
</source>

===基数ソート===
小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。
データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。
<source lang="cpp">
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;
}
</source>

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

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

== 関連項目 ==
*[[アルゴリズム]]

== 参考文献 ==
{{reflist}}

{{stub}}