マージソート#
紹介#
マージソートは、マージの考え方を使用して実現されるソート方法であり、このアルゴリズムは古典的な分割統治法を採用しています。
具体的には、ソート中に配列を異なる小さな配列（境界では 1 つの要素のみ）に分割し、マージ時にソートします。
複雑度 / 安定性#
時間複雑度
上記のコードを例にすると、この時点で です。マージソートのセクションは、インデックスを 2 分割する方法を使用しています。
次の図のように、各 2 つのセクションをマージするとき、各レベルで 回比較が行われ、合計で レベルあります。したがって、時間複雑度は です。
安定性
各 2 つのセクションは隣接しているため、同じ数値をマージするとき、相対的な位置は変わりません。したがって、マージソートは安定です。
コードの実装#
以下は C++ での実装です。コメントを参照してください：
const int N = 1e4+5;
int n, tmp[N], a[N];
void fsort(int l, int r){
//まず再帰的にグループ分けを行います
if(l >= r) return ;//境界条件、分割される配列の最小値は1です
int mid = (l+r)/2; //中央値を取得します
fsort(l, mid); //左側
fsort(mid+1, r); //右側
//バックトラック時にマージしてソートします。元の配列を直接操作することはできないため、マージ結果を一時的にtmp配列に保存します
int i = l, j = mid+1, k = l;
while(i <= mid && j <= r){ //2つのシーケンスの各要素を比較し、順序に従って一時的な配列に格納します
if(a[i] <= a[j]){
tmp[k] = a[i];//左側の範囲の数値が小さいので、格納します
i++;
k++;
}
else{
tmp[k] = a[j];//右側の範囲の数値が小さいので、格納します
j++;
k++;
}
}
//余分な数値が1つの配列に残っている場合、追加して配置します
while(i<=mid){
tmp[k]=a[i];
i++;
k++;
}
while(j<=r){
tmp[k]=a[j];
j++;
k++;
}
//一時的な領域の数値を元の配列に格納します
for(int i = l; i <= r; i++)
a[i] = tmp[i];
}
signed main(){
fsort(1, n);
return 0;
}
クイックソート#
紹介#
クイックソートは、二分法を使用して配列のソートを行うアルゴリズムです。
クイックソートは、ソートする配列からピボット値を選択し、配列をピボット値の位置を境に小さい方と大きい方に調整し、再帰的に両側をソートすることでソートを完了します。
図 1 を参照してください：
具体的な操作については、以下の図 2 を参照してください：
複雑度 / 安定性の分析#
時間複雑度
最良の場合、各分割は均等になるため、マージソートと同様に各レベルで 個の要素をソートします。合計で レベルありますので、時間複雑度は です。
最悪の場合、ピボット値が最大または最小の場合、空のシーケンスが発生し、 回の分割が必要です。したがって、時間複雑度は です。
同様に、ピボット値がランダム性を失った場合、クイックソートの時間複雑度も に低下します。
安定性
クイックソートは、各ピボット値の分類時に、上記の図のように、2 つの要素の値が等しい場合、相対的な位置が変わるため、安定ではありません。
コードの実装#
以下は C++ での実装です。コメントを参照してください：
const int N = 1e4+5;
int n, a[N];
void quicksort(int l, int r){//図2を参照してください
if(l >= r) return ;//範囲外にならないようにする
int t = a[l]; //ピボット値を選択します。図のように、最初の位置を選択します
int i = l, j = r;
while(i < j){ //i != jの場合、ループに入ります
while( a[j] > t ) j--; //後ろから前に向かって、ピボット値より小さい値を順番に探します
while( a[i] <= t && i<j) i++;//前から後ろに向かって、ピボット値より大きい値を順番に探します
if(i < j) swap(a[i], a[j]);//i < jの場合にのみ交換できます。同じ位置を交換することはできません
}
swap(a[l],a[i]); //ピボット値を適切な位置に配置します。この時点でi = jです
quicksort(l,i-1);//下に分割を続けます
quicksort(i+1,r);
}
signed main(){
quicksort(1, n);
return 0;
}
ヒープソート#
ヒープソート は、ヒープというデータ構造を使用してソートを行います。選択ソートとは異なり、ツリーというデータ構造を使用して要素を検索します。
事前チーズ：ヒープ#
図を参照してください。ヒープは特殊な完全二分木であり、大きなヒープと小さなヒープの 2 種類に分かれます：
- 大きなヒープ：完全二分木の任意の非葉子ノードの値は、その子ノードの値以上です。
- 小さなヒープ：完全二分木の任意の非葉子ノードの値は、その子ノードの値以下です。
紹介#
選択ソートの原理は理解しやすいため、この部分はスキップします（類推できます）。ヒープで要素を検索する方法に重点を置きます。
配列要素を単調に減少させる場合、最終的に大きなヒープを作成する必要があります。下から上に非葉子ノード（子ノードのないノード）を逆順に走査し、交換することで親子ノードの順序を調整します。
例：次の図のような配列がある場合、この操作を行うだけで、ソートされた配列が得られます。
複雑度 / 安定性の分析#
時間複雑度
選択ソートと同様に、 個の要素を操作する必要がありますが、違いは、選択ソートでは 1 つの要素を操作するのに 回かかりますが、ヒープソートでは 1 つの要素を検索するのに 回しかかかりません。したがって、ヒープソートの時間複雑度は です。
安定性
ヒープソートは、各要素の分類時に、上記の図のように、2 つの要素の値が等しい場合、相対的な位置が変わるため、安定ではありません。
コードの実装#
以下は C++ での実装です。コメントを参照してください：
const int N = 1e4+5;
int m, a[N]
//ヒープソート
//ヒープ部分
void adjust(int i, int parent)
{
int child = parent * 2;//まず子ノードを確認します
// 範囲がiを超えないようにする
if(child + 1 <= i && a[child] < a[child + 1]){
child++;//2つの子ノードのうち、大きい方を選択して上に移動します（大きなヒープを維持する）
}
if(a[child] > a[parent]){
swap(a[child], a[parent]);//子ノードの方が大きい場合、上に交換します
if(child <= i / 2){//iの親ノードを超えないようにする
adjust(i, child);//現在のノードが更新された場合、現在のノードの子ノードも更新する必要があります
}
}
}
//メインのソート部分
void heapSort(){
for(int i = n; i > 1; i--){//右から左に維持するため、左から右にすることはできません。子ノードがすでに維持されていることを保証できません
for(int j = i / 2; j >= 1; j--){//iの親ノードから開始して維持します
adjust(i, j);//j番目のノードを根ノードとして維持します。iは境界を判断するための補助です
}
swap(a[1], a[i]);//この時点でツリーの根は[1, i]範囲内で最大の数です。現在の位置と交換します（選択ソートを参照）
}
}
signed main(){
heapSort();
return 0;
}