「ソート」の版間の差分
imported>Fallout New Tokyo |
|||
(他の1人の利用者による、間の2版が非表示) | |||
1行目: | 1行目: | ||
− | '''ソート''' | + | '''ソート'''([[英語]]: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] ) { |
− | + | t = a[i]; | |
− | a[i]=a[i+1]; | + | a[i] = a[i+1]; |
− | a[i+1]= | + | 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>。 | ||
+ | |||
+ | [[Haskell]]での記述例 | ||
<source lang="haskell"> | <source lang="haskell"> | ||
mergeinternal [] [] = [] | mergeinternal [] [] = [] | ||
144行目: | 147行目: | ||
===クイックソート=== | ===クイックソート=== | ||
− | + | [[クイックソート]]は、まず要素の中から適当に[[ピポット]]と呼ばれる基準値を設定し、ピポット未満の要素とピポット以上の要素に分ける。 | |
分けた要素をそれぞれ同じようにソートし、ピポット未満の要素をソートしたものの後ろにピポット以上の要素をソートしたものをくっつける。 | 分けた要素をそれぞれ同じようにソートし、ピポット未満の要素をソートしたものの後ろにピポット以上の要素をソートしたものをくっつける。 | ||
− | + | [[データ]]と実装によっては遅くなることがあるが、いくつかの改善法がある。 | |
− | + | [[Haskell]]での記述例 | |
<source lang="haskell"> | <source lang="haskell"> | ||
qsort ls = if (null ls) then [] else | qsort ls = if (null ls) then [] else | ||
158行目: | 161行目: | ||
===基数ソート=== | ===基数ソート=== | ||
− | + | [[基数ソート]]は、小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。 | |
データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。 | データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。 | ||
<source lang="cpp"> | <source lang="cpp"> | ||
185行目: | 188行目: | ||
=== スリープソート === | === スリープソート === | ||
− | + | [[スリープソート]]はソートの最終系と言われる[[アルゴリズム]]である。 | |
詳細は「[[スリープソート]]」の項目を参照。 | 詳細は「[[スリープソート]]」の項目を参照。 |
2015年5月15日 (金) 07:12時点における最新版
ソート(英語: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;
}
}
}
}
マージソート[編集 | ソースを編集]
マージソートは、配列を短く分割し、徐々に併合していくことでソートを行う。 キャラソートでも採用されているらしい[1]。
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;
}
スリープソート[編集 | ソースを編集]
スリープソートはソートの最終系と言われるアルゴリズムである。
詳細は「スリープソート」の項目を参照。