ソート - 版の履歴

Administrator: /* 参考文献 */

2025-03-25T07:40:06Z

参考文献

← 古い版		2025年3月25日 (火) 07:40時点における版
198行目:		198行目:
	{{reflist}}		{{reflist}}

	~~{{stub}}~~		[[category: アルゴリズム]]

2015年5月15日 (金) 07:12に153.174.184.145による

2015-05-15T07:12:54Z

← 古い版		2015年5月15日 (金) 07:12時点における版
1行目:		1行目:
	'''ソート'''~~（英語：sort）とは、一連の~~[[データ]]をある一定の[[順序]]に従って並べ替える処理である。		'''ソート'''（[[英語]]：sort）とは、一連の[[データ]]をある一定の[[順序]]に従って並べ替える処理である。

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

	===挿入ソート===		===挿入ソート===
	~~これまで並べ替えた部分に、その直後の要素を目標の順序に合う位置に挿入する。~~		[[挿入ソート]]は、これまで並べ替えた部分に、その直後の要素を目標の順序に合う位置に挿入する。
	~~通常はバブルソートと同じ~~[[計算量]]~~とみなされるが、ソート済みの配列をソートする場合に高速。~~		通常は[[バブルソート]]と同じ[[計算量]]とみなされるが、ソート済みの[[配列]]をソートする場合に高速。
	<source lang="c">		<source lang="c">
	void sort(int a[],int num) {		void sort(int a[],int num) {
36行目:		37行目:

	===ヒープソート===		===ヒープソート===
	~~要素を一旦全てヒープに放り込み、根の要素を順に取り出すことによりソートする。~~		[[ヒープソート]]は、要素を一旦全て[[ヒープ]]に放り込み、根の要素を順に取り出すことによりソートする。
	実装が若干複雑な割にあまり高速ではない。		実装が若干複雑な割にあまり高速ではない。
	<source lang="c">		<source lang="c">
105行目:		106行目:

	===シェルソート===		===シェルソート===
	~~挿入ソートに似ているが、初めは広い間隔でソートを行い、徐々に間隔を狭くしていく。~~		[[シェルソート]]は、[[挿入ソート]]に似ているが、初めは広い間隔でソートを行い、徐々に間隔を狭くしていく。
	~~クイックソートの登場前は最速のソートと言われていたらしい。~~		[[クイックソート]]の登場前は最速のソートと言われていたらしい。
	<source lang="c">		<source lang="c">
	void sort(int a[],int num) {		void sort(int a[],int num) {
128行目:		129行目:

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

146行目:		147行目:

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

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

	[[Haskell]]での記述例		[[Haskell]]での記述例
160行目:		161行目:

	===基数ソート===		===基数ソート===
	~~小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。~~		[[基数ソート]]は、小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。
	データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。		データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。
	<source lang="cpp">		<source lang="cpp">
187行目:		188行目:

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

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

imported>Fallout New Tokyo: /* マージソート */

2014-03-03T03:23:42Z

マージソート

← 古い版		2014年3月3日 (月) 03:23時点における版
130行目:		130行目:
	配列を短く分割し、徐々に併合していくことでソートを行う。		配列を短く分割し、徐々に併合していくことでソートを行う。
	[[キャラソート]]でも採用されているらしい<ref>http://marineturtle.sakura.ne.jp/script/sort/hpsort/mergesort_exp.html</ref>。		[[キャラソート]]でも採用されているらしい<ref>http://marineturtle.sakura.ne.jp/script/sort/hpsort/mergesort_exp.html</ref>。

			[[Haskell]]での記述例
	<source lang="haskell">		<source lang="haskell">
	mergeinternal [] [] = []		mergeinternal [] [] = []

imported>Fallout New Tokyo: /* クイックソート */

2014-03-03T03:23:11Z

クイックソート

← 古い版		2014年3月3日 (月) 03:23時点における版
149行目:		149行目:
	データと実装によっては遅くなることがあるが、いくつかの改善法がある。		データと実装によっては遅くなることがあるが、いくつかの改善法がある。

	~~Haskellでの記述例~~		[[Haskell]]での記述例
	<source lang="haskell">		<source lang="haskell">
	qsort ls = if (null ls) then [] else		qsort ls = if (null ls) then [] else

imported>Fallout New Tokyo: /* クイックソート */

2014-03-03T03:23:00Z

クイックソート

← 古い版		2014年3月3日 (月) 03:23時点における版
148行目:		148行目:

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

			Haskellでの記述例
	<source lang="haskell">		<source lang="haskell">
	qsort ls = if (null ls) then [] else		qsort ls = if (null ls) then [] else

2014年3月3日 (月) 03:21にimported>Fallout New Tokyoによる

2014-03-03T03:21:11Z

← 古い版		2014年3月3日 (月) 03:21時点における版
181行目:		181行目:
	}		}
	</source>		</source>

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

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

	== 関連項目 ==		== 関連項目 ==

2014年3月3日 (月) 03:19にimported>Fallout New Tokyoによる

2014-03-03T03:19:37Z

← 古い版		2014年3月3日 (月) 03:19時点における版
1行目:		1行目:
	'''ソート'''~~とは、一連の~~[[データ]]をある一定の[[順序]]に従って並べ替える処理である。		'''ソート'''（英語：sort）とは、一連の[[データ]]をある一定の[[順序]]に従って並べ替える処理である。

	==主なソート[[アルゴリズム]]==		==主なソート[[アルゴリズム]]==
181行目:		181行目:
	}		}
	</source>		</source>

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

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

			{{stub}}

imported>MikeCAT: 作成

2013-08-22T05:45:12Z

作成

新規ページ

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

==主なソート[[アルゴリズム]]==
実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。
===バブルソート===
最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。
<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>。
<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>

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

データと実装によっては遅くなることがあるが、いくつかの改善法がある。
<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}}