up:: Programming
比較ベースと非比較ベースの二つがある。
ほとんどは比較ベース。
安定か不安定かという視点もある。この場合は同じ値を持つ場合の要素の総体的順序を保持するかどうか。
こっちは結構ばらける。
説明は小さい順で並べる前提。
基本的なソートアルゴリズム11個まとめ | Shino’s Mind Archive
バブルソート
比較ベース、安定。
一方向から隣接する要素を比較し、順序が逆になっている場合は交換する。要素の最後まで行ったらもう一度最初から。
これを逆になっている要素が無くなるまで繰り返すだけ。
最悪計算量は。全ての要素が逆順な時。n-1回のループ(以後、パスとする)で、それぞれn-1回の比較と交換が行われる。交換は定数倍なので計算量では無視するが、比較は結局n-1回やる。
つまり計算量は
となる。計算量では足し算引き算の場合大きい方を優先するので、計算量はとなる。
ちなみにどっちがでかいんだというときに備え、こんなのが用意されてる。左の方がでかい。
平均計算量は。各パスで半分の要素が交換されると仮定できる。すると計算はまんまこうなる。同じように計算してとなる。
単純なソートアルゴリズム「バブルソート」を解説！ | Shino’s Mind Archive
計算量とは？プログラムの性能を計ってみよう | Shino’s Mind Archive
選択ソート
比較ベース、不安定。
未ソート部分から最小値を発見し、それを未ソート部分の先頭に投げる。
これを繰り返すだけ。
計算量は計算法まで含めてバブルソートと同じく。
挿入ソート
比較ベース、安定。
未ソート部分から先頭要素を取り出し、ソート部分の適切な位置に入れる。この時先頭一個目はソート済みとみなす。
これを繰り返す。
計算量は計算法まで含めてバブルソートと同じく。
クイックソート
比較ベース、不安定。
まずはピボットと呼ばれる要素を選択。他の要素をピボットより大きいか小さいかで分割する。
そして分割された二つの部分に対し、それぞれ再帰的に同じ操作を行う。
これを繰り返す。
最悪はバブルソートと同じく。
一方、平均はと上回る。分割操作はピボットを各要素と比較するので。分割された部分に対して再帰的にその操作を繰り返す。これは配列がになるまで続けられる。よってこのように計算できる。
えっ、どのように計算式が出来たか？
漸化式とΣと調和級数と積分の話が始まるけど良ければ。
こっからは実用的なのでコードを貼っておく。
function QuickSort(data, left, right){
console.log("left:right = " + left + ":" + right + " , " + data);
if(left >= right){
return;
}
let v = partition(data, left, right);
QuickSort(data, left, v - 1);
QuickSort(data, v + 1, right);
}
function partition(data, left, right){
let i = left;
let j = right - 1;
let pivot = data[right];
while(true){
while(data[i] < pivot){
i++;
}
while(i < j && pivot < data[j]){
j--;
}
if(i >= j){
break;
}
let tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
let tmp = data[i];
data[i] = data[right];
data[right] = tmp;
return i;
}
ちなみに適当だからと言って1つ目から選ぶと、整列済みデータの際に分割できなくなり詰む。
その対処として、複数個所のデータからその中央値を取る、というものがある。
マージソート
比較ベース、安定。
まず配列を二分。一個になるまで二分する。
その後、小さい数字が左に来るように比較並べ替えしながらマージしていく。
これを繰り返す。
最悪はバブルソートと同じく。
平均はでクイックソートと同じだが、無視されてる定数分が結構大きいので基本はクイックソート。
また、普通の配列だとマージのたびに配列が必要になり、その分メモリを食う。
その上配列の強みである任意位置にで到達できるという要素が生かされない。
この場合は、一つ一つの要素が数値とその次の要素へのポインタを持つリンクリスト、あるいは連結リストと呼ばれる形式にすることでデメリットを回避できる。ポインタ書き換えればいいだけだし。
function MergeSort(data, low, high){
if(low >= high){
return;
}
let mid = Math.floor((low + high) / 2);
MergeSort(data, low, mid);
MergeSort(data, mid + 1, high);
let tmp = [];
for(let i = low; i <= mid; i++){
tmp[i] = data[i];
}
for(let i = mid + 1, j = high; i <= high; i++, j--){
tmp[i] = data[j];
}
let i = low;
let j = high;
for(let k = low; k <= high; k++){
if(tmp[i] <= tmp[j]){
data[k] = tmp[i];
i++;
}else{
data[k] = tmp[j];
j--;
}
}
}
ヒープソート
比較ベース。不安定。
ヒープを上から取り出す。終了。
各ステップで最大値を取り出すのに、ステップ自体にかかるので、実行時間はになる。実行方法がこれ一個なので平均も最悪も同じ固定量。