最近の言語にはソートの内容知らなくても便利な関数が用意されているので、とりあえずソートできるといえばできます。
C++ならばをincludeすればsortが使えますし、pythonにもsort()ってあるらしいですし。
[card url=”https://cpprefjp.github.io/reference/algorithm/sort.html”]
[card url=”https://docs.python.jp/3/howto/sorting.html”]
しかし、C言語にはそんな便利なものはないので自分で実装しましょうという話です。
あと、なんだかんだソートって自分で実装できたほうがいいよね、というのもあります。
クイックソート
C++のsortはクイックソートの改良版であるイントロソートと言うものが使われているそうです。
クイックソートは、「ピボット(任意の数、中央値が望ましい)を決めて、それより大きいか小さいかで分ける。これを再帰的にやればソートされる」と言うものです。
wikipediaさんにソートのgif画像や例が載っててわかりやすいので、そちらをどうぞ。
[card url=”https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88″]
さて、これをC言語で実装してみましょう。
[c]
void quicksort(int *a,int left,int right) {
if(left<right){
int tmp;
int i=left;
int j=right;
int pivot=a[i];
while(1){
while(a[i]>pivot) i++;
while(pivot>a[j]) j–;
if(i>=j) break;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;
j–;
}
quicksort(a,left,i-1);
quicksort(a,j+1,right);
}
}
[/c]
再帰より前がピポッドとの大小関係を計算し、入れ替えるものです。
入れ替えるだけなら、swap関数でも作ってあげると見やすいと思います。
挿入ソート
挿入ソートは、整列済みの配列を作り出して、その後後ろの要素を整列済みの配列に対して大小を見ながら入れていくソートです。
こちらもwikipediaを見ればいいかなあと。
イメージとしては、人間が紙とペンでソートするのに似ていると思います。(個人の感想です)
[blogcard url=”https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88″]
じゃあ、C言語で実装しましょう。
[c]
void swap(int a,int *b) {
int tmp;
tmp=a;
a=b;
*b=tmp;
}
void insert_sort(int ar[],int n) {
int i,j;
for(i=1;i<n;i++){
j=i;
while((j>0)&&(ar[j-1]>ar[j])){
swap(&ar[j-1],&ar[j]);
count++;
j–;
}
}
}
[/c]
main関数内の配列を書き換えたいのでポインタ渡しです。
swap関数は、要素ふたつを入れ替える関数、その下は挿入ソート本体です。
while文の条件式はjは0より大きい(配列を飛び出さない)かつ、前の要素が今の要素より小さい、です。
ソートといえばまだまだありますが、とりあえず、sortを視覚化したもの置いてお茶を濁します。
大正義ボゴソート!!