差分
ナビゲーションに移動
検索に移動
ソート
,作成
'''ソート'''とは、一連の[[データ]]をある一定の[[順序]]に従って並べ替える処理である。
==主なソート[[アルゴリズム]]==
実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。
===バブルソート===
最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。
<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}}
==主なソート[[アルゴリズム]]==
実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。
===バブルソート===
最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。
<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}}
