MonoBook

「ソート」の版間の差分

ビジュアルウィキテキスト
imported>MikeCAT
作成
 
 
(2人の利用者による、間の6版が非表示)
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] ) {
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>。
[[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
156行目: 161行目:


===基数ソート===
===基数ソート===
小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。
[[基数ソート]]は、小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。
データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。
データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。
<source lang="cpp">
<source lang="cpp">
181行目: 186行目:
}
}
</source>
</source>
=== スリープソート ===
[[スリープソート]]はソートの最終系と言われる[[アルゴリズム]]である。
詳細は「[[スリープソート]]」の項目を参照。
== 関連項目 ==
*[[アルゴリズム]]


== 参考文献 ==
== 参考文献 ==
{{reflist}}
{{reflist}}
[[category: アルゴリズム]]
「https://monobook.org/wiki/ソート」から取得