「ソート」を編集中
ナビゲーションに移動
検索に移動
この編集を取り消せます。 下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
最新版 | 編集中の文章 | ||
1行目: | 1行目: | ||
− | '''ソート''' | + | '''ソート'''とは、一連の[[データ]]をある一定の[[順序]]に従って並べ替える処理である。 |
− | == | + | ==主なソート[[アルゴリズム]]== |
実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。 | 実装例は、[[整数]]を[[昇順]]に並べ替えるものを示す。 | ||
===バブルソート=== | ===バブルソート=== | ||
− | + | 最も単純なソートの一つ。前から順番に隣り合う要素を比較して、大小関係が目標の順序と異なったら入れ替える。 | |
<source lang="c"> | <source lang="c"> | ||
− | void sort(int a[], int num) { | + | void sort(int a[],int num) { |
− | int i, j | + | int i,j; |
− | 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]; | |
− | a[i] = a[i+1]; | + | a[i]=a[i+1]; |
− | a[i+1] = | + | a[i+1]=temp; |
− | |||
} | } | ||
} | } | ||
22行目: | 21行目: | ||
===挿入ソート=== | ===挿入ソート=== | ||
− | + | これまで並べ替えた部分に、その直後の要素を目標の順序に合う位置に挿入する。 | |
− | + | 通常はバブルソートと同じ[[計算量]]とみなされるが、ソート済みの配列をソートする場合に高速。 | |
<source lang="c"> | <source lang="c"> | ||
void sort(int a[],int num) { | void sort(int a[],int num) { | ||
37行目: | 36行目: | ||
===ヒープソート=== | ===ヒープソート=== | ||
− | + | 要素を一旦全てヒープに放り込み、根の要素を順に取り出すことによりソートする。 | |
実装が若干複雑な割にあまり高速ではない。 | 実装が若干複雑な割にあまり高速ではない。 | ||
<source lang="c"> | <source lang="c"> | ||
106行目: | 105行目: | ||
===シェルソート=== | ===シェルソート=== | ||
− | + | 挿入ソートに似ているが、初めは広い間隔でソートを行い、徐々に間隔を狭くしていく。 | |
− | + | クイックソートの登場前は最速のソートと言われていたらしい。 | |
<source lang="c"> | <source lang="c"> | ||
void sort(int a[],int num) { | void sort(int a[],int num) { | ||
129行目: | 128行目: | ||
===マージソート=== | ===マージソート=== | ||
− | + | 配列を短く分割し、徐々に併合していくことでソートを行う。 | |
[[キャラソート]]でも採用されているらしい<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>。 | ||
− | |||
− | |||
<source lang="haskell"> | <source lang="haskell"> | ||
mergeinternal [] [] = [] | mergeinternal [] [] = [] | ||
147行目: | 144行目: | ||
===クイックソート=== | ===クイックソート=== | ||
− | + | まず要素の中から適当にピポットと呼ばれる基準値を設定し、ピポット未満の要素とピポット以上の要素に分ける。 | |
分けた要素をそれぞれ同じようにソートし、ピポット未満の要素をソートしたものの後ろにピポット以上の要素をソートしたものをくっつける。 | 分けた要素をそれぞれ同じようにソートし、ピポット未満の要素をソートしたものの後ろにピポット以上の要素をソートしたものをくっつける。 | ||
− | + | データと実装によっては遅くなることがあるが、いくつかの改善法がある。 | |
− | |||
− | |||
<source lang="haskell"> | <source lang="haskell"> | ||
qsort ls = if (null ls) then [] else | qsort ls = if (null ls) then [] else | ||
161行目: | 156行目: | ||
===基数ソート=== | ===基数ソート=== | ||
− | + | 小さい桁から大きな桁の順に見ていき、それぞれについて安定なソートを行う。 | |
データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。 | データの種類が限られるが、特にデータ数が多い時に高速にソートできることがある。 | ||
<source lang="cpp"> | <source lang="cpp"> | ||
186行目: | 181行目: | ||
} | } | ||
</source> | </source> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== 参考文献 == | == 参考文献 == | ||
{{reflist}} | {{reflist}} | ||
− | |||
− |