【アルゴリズム基礎】安定ソートアルゴリズムと不安定ソートアルゴリズム
文書ディレクトリ概要 安定なソートアルゴリズム 1. バブルソート 2. 挿入ソート 3. 集計ソート 4. 基数ソート 不安定なソートアルゴリズム 1. 選択ソート 2. クイックソート 3. ヒルソート 4. ヒープ順序 参照 概要
ソートは最も基礎的なアルゴリズムの一つであり,ソートアルゴリズムが安定性を持っているかどうかも考慮すべき点である.
ソートアルゴリズムの安定性の定義:
2つの同じ数値の要素は、ソート前とソート後、前後の順序が変わらなければ、アルゴリズムが安定していると考えられる.逆にアルゴリズムは不安定であると考えられる.
すなわち、元のシーケンスでは
一般的なソートアルゴリズムでは、スタックソート、高速ソート、ヒルソート、直接選択ソートは不安定なソートアルゴリズムであり、基数ソート、バブルソート、直接挿入ソート、折半挿入ソート、集計ソートは安定したソートアルゴリズムである.
注意:アルゴリズムが安定しているかどうかは、アルゴリズムが実現の詳細を具体的に考察する必要がある.
安定したソートアルゴリズム
1.泡立ちソート
バブルソートとは、小さな要素を前に調整したり、大きな要素を後ろに調整したりすることです.比較は隣接する2つの要素の比較であり、交換もこの2つの要素の間で発生する.だから、もし2つの要素が同じなら、あなたはもう退屈に彼ら二人を交換しないと思います.2つの等しい要素が隣接していない場合、前の2つの交換によって2つが隣接していても交換されないため、同じ要素の前後の順序は変わらないので、バブルソートは安定したソートアルゴリズムである.
2.ソートの挿入
挿入ソートは、順序付けされた小さなシーケンスに基づいて、要素を一度に挿入します.もちろん、この秩序化された小さなシーケンスは最初の要素である1つの要素しかありません.比較は、順序付けされたシーケンスの最後から始まります.つまり、挿入したい要素と順序付けされた最大のものから始まります.それより大きい場合は、その後ろに直接挿入します.そうしないと、挿入された位置が見つかるまで前に進みます.挿入要素と等しいものが見つかった場合、挿入要素は挿入したい要素を等しい要素の後ろに置きます.したがって,等しい要素の前後の順序は変化せず,元の無秩序配列から出た順序が順序後の順序であるため,挿入順序は安定である.
3.集計ソート
集計ソートは、シーケンスを再帰的に短いシーケンスに分割し、再帰出口は、短いシーケンスが1つの要素(直接秩序とみなされる)または2つの要素(1回の比較と交換)のみであり、その後、各秩序のセグメントシーケンスを1つの秩序の長いシーケンスに統合し、元のシーケンスがすべて整列するまで集計し続ける.1つまたは2つの元素の場合,1つの元素は交換されず,2つの元素が大きさが等しければ故意に交換する人はいないことが分かったが,これは安定性を破壊しない.では,短い秩序配列の結合過程で安定性が破壊されるかどうか.いいえ、マージ中に2つの現在の要素が等しい場合、前のシーケンスにある要素を結果シーケンスの前に保存することで、安定性が保証されます.したがって,集計ソートも安定したソートアルゴリズムである.
4.基数ソート
基数ソートは低位に従って先にソートし、収集します.さらに高位に並べて収集します.最高位まで順番に類推する.一部のプロパティには優先度順がある場合があります.まず低優先度でソートし、高優先度でソートします.最後の順序は、高優先度が前で、高優先度が同じ低優先度が前です.基数ソートは,個別ソートに基づいてそれぞれ収集されるので,安定したソートアルゴリズムである.
不安定なソートアルゴリズム
1.ソートの選択
選択ソートは、各位置に現在の要素の最小を選択します.例えば、最初の位置に最小を選択し、残りの要素の中で2番目の要素に2番目の小を選択し、n-1番目の要素まで順に類推します.n番目の要素は選択する必要はありません.最大の要素が1つしか残っていないからです.では、1つの選択では、現在の要素が1つの要素よりも小さく、その小さな要素が現在の要素と等しい要素の後ろに現れると、交換後の安定性が破壊されます.拗ねて、例を挙げると、シーケンス5 8 8 5 2 9は、最初に1番目の要素5を選択すると2と交換されることを知っているので、元のシーケンスの2つの5の相対的な前後の順序が破壊されるので、選択ソートは安定したソートアルゴリズムではありません.
2.クイックソート
クイックソートには2つの方向があり、左のiの下付き文字が右に進むと、a[i]<=a[center_index]となり、center_indexは中枢元素の配列下標であり、一般的に配列0番目の元素とされる.右側のj下の記号は、a[j]>a[center_index]のとき、ずっと左に行きます.iとjが動かなくなった場合,i<=j,a[i]とa[j]を交換し,i>jまで上記の手順を繰り返す.a[j]とa[center_index]を交換し、クイックソートを完了します.中枢元素とa[j]を交換する場合、前の元素の安定性を乱す可能性が高い.例えば、シーケンスが5 3 3 3 3 4 3 8 9 10 11である.現在、中枢元素5と3(5番目の元素、以下1から計算)を交換すると元素3の安定性が乱されるため、高速ソートは不安定なソートアルゴリズムであり、不安定は中枢元素とa[j]交換の時点で発生する.
3.ヒルソート(shell)
ヒルソートは非同期長に従って要素を挿入ソートし、最初は要素が無秩序だったとき、ステップ長が最大なので、挿入ソートの要素の個数が少なく、速度が速い.要素が基本的に秩序化されると、ステップ長が小さく、挿入ソートは秩序化されたシーケンスに対して効率的です.したがって,ヒルソートの時間的複雑さはO(n 2)O(n^2)O(n 2)よりも優れている.複数回の挿入ソートのため、1回の挿入ソートは安定であり、同じ要素の相対的な順序は変更されないことが知られているが、異なる挿入ソートの過程で、同じ要素がそれぞれの挿入ソートで移動する可能性があり、最後にその安定性が乱されるため、shellソートは不安定である.
4.ヒープのソート
スタックの構造は、ノードiの子供が
リファレンス
https://baike.baidu.com/item/ソートアルゴリズムの安定性
ソートは最も基礎的なアルゴリズムの一つであり,ソートアルゴリズムが安定性を持っているかどうかも考慮すべき点である.
ソートアルゴリズムの安定性の定義:
2つの同じ数値の要素は、ソート前とソート後、前後の順序が変わらなければ、アルゴリズムが安定していると考えられる.逆にアルゴリズムは不安定であると考えられる.
すなわち、元のシーケンスでは
r[i]=r[j]であり、r[i]がr[j]より前であり、並べ替え後のシーケンスではr[i]がr[j]より前である場合、この並べ替えアルゴリズムは安定していると称される.そうでなければ不安定と呼ばれます.一般的なソートアルゴリズムでは、スタックソート、高速ソート、ヒルソート、直接選択ソートは不安定なソートアルゴリズムであり、基数ソート、バブルソート、直接挿入ソート、折半挿入ソート、集計ソートは安定したソートアルゴリズムである.
注意:アルゴリズムが安定しているかどうかは、アルゴリズムが実現の詳細を具体的に考察する必要がある.
安定したソートアルゴリズム
1.泡立ちソート
バブルソートとは、小さな要素を前に調整したり、大きな要素を後ろに調整したりすることです.比較は隣接する2つの要素の比較であり、交換もこの2つの要素の間で発生する.だから、もし2つの要素が同じなら、あなたはもう退屈に彼ら二人を交換しないと思います.2つの等しい要素が隣接していない場合、前の2つの交換によって2つが隣接していても交換されないため、同じ要素の前後の順序は変わらないので、バブルソートは安定したソートアルゴリズムである.
2.ソートの挿入
挿入ソートは、順序付けされた小さなシーケンスに基づいて、要素を一度に挿入します.もちろん、この秩序化された小さなシーケンスは最初の要素である1つの要素しかありません.比較は、順序付けされたシーケンスの最後から始まります.つまり、挿入したい要素と順序付けされた最大のものから始まります.それより大きい場合は、その後ろに直接挿入します.そうしないと、挿入された位置が見つかるまで前に進みます.挿入要素と等しいものが見つかった場合、挿入要素は挿入したい要素を等しい要素の後ろに置きます.したがって,等しい要素の前後の順序は変化せず,元の無秩序配列から出た順序が順序後の順序であるため,挿入順序は安定である.
3.集計ソート
集計ソートは、シーケンスを再帰的に短いシーケンスに分割し、再帰出口は、短いシーケンスが1つの要素(直接秩序とみなされる)または2つの要素(1回の比較と交換)のみであり、その後、各秩序のセグメントシーケンスを1つの秩序の長いシーケンスに統合し、元のシーケンスがすべて整列するまで集計し続ける.1つまたは2つの元素の場合,1つの元素は交換されず,2つの元素が大きさが等しければ故意に交換する人はいないことが分かったが,これは安定性を破壊しない.では,短い秩序配列の結合過程で安定性が破壊されるかどうか.いいえ、マージ中に2つの現在の要素が等しい場合、前のシーケンスにある要素を結果シーケンスの前に保存することで、安定性が保証されます.したがって,集計ソートも安定したソートアルゴリズムである.
4.基数ソート
基数ソートは低位に従って先にソートし、収集します.さらに高位に並べて収集します.最高位まで順番に類推する.一部のプロパティには優先度順がある場合があります.まず低優先度でソートし、高優先度でソートします.最後の順序は、高優先度が前で、高優先度が同じ低優先度が前です.基数ソートは,個別ソートに基づいてそれぞれ収集されるので,安定したソートアルゴリズムである.
不安定なソートアルゴリズム
1.ソートの選択
選択ソートは、各位置に現在の要素の最小を選択します.例えば、最初の位置に最小を選択し、残りの要素の中で2番目の要素に2番目の小を選択し、n-1番目の要素まで順に類推します.n番目の要素は選択する必要はありません.最大の要素が1つしか残っていないからです.では、1つの選択では、現在の要素が1つの要素よりも小さく、その小さな要素が現在の要素と等しい要素の後ろに現れると、交換後の安定性が破壊されます.拗ねて、例を挙げると、シーケンス5 8 8 5 2 9は、最初に1番目の要素5を選択すると2と交換されることを知っているので、元のシーケンスの2つの5の相対的な前後の順序が破壊されるので、選択ソートは安定したソートアルゴリズムではありません.
2.クイックソート
クイックソートには2つの方向があり、左のiの下付き文字が右に進むと、a[i]<=a[center_index]となり、center_indexは中枢元素の配列下標であり、一般的に配列0番目の元素とされる.右側のj下の記号は、a[j]>a[center_index]のとき、ずっと左に行きます.iとjが動かなくなった場合,i<=j,a[i]とa[j]を交換し,i>jまで上記の手順を繰り返す.a[j]とa[center_index]を交換し、クイックソートを完了します.中枢元素とa[j]を交換する場合、前の元素の安定性を乱す可能性が高い.例えば、シーケンスが5 3 3 3 3 4 3 8 9 10 11である.現在、中枢元素5と3(5番目の元素、以下1から計算)を交換すると元素3の安定性が乱されるため、高速ソートは不安定なソートアルゴリズムであり、不安定は中枢元素とa[j]交換の時点で発生する.
3.ヒルソート(shell)
ヒルソートは非同期長に従って要素を挿入ソートし、最初は要素が無秩序だったとき、ステップ長が最大なので、挿入ソートの要素の個数が少なく、速度が速い.要素が基本的に秩序化されると、ステップ長が小さく、挿入ソートは秩序化されたシーケンスに対して効率的です.したがって,ヒルソートの時間的複雑さはO(n 2)O(n^2)O(n 2)よりも優れている.複数回の挿入ソートのため、1回の挿入ソートは安定であり、同じ要素の相対的な順序は変更されないことが知られているが、異なる挿入ソートの過程で、同じ要素がそれぞれの挿入ソートで移動する可能性があり、最後にその安定性が乱されるため、shellソートは不安定である.
4.ヒープのソート
スタックの構造は、ノードiの子供が
2*iおよび2*i+1ノードであり、大きなスタックは、親ノードがその2つのサブノード以上であることを要求し、小さなスタックは、親ノードがその2つのサブノード以下であることを要求することを知っている.長さnのシーケンスでは、スタックソートのプロセスは、n/2番目からそのサブノードとの3つの値から最大(大トップスタック)または最小(小トップスタック)を選択し、この3つの要素間の選択はもちろん安定性を破壊しない.しかし、n /2-1, n/2-2, ...1の親ノードの要素を選択すると、安定性が損なわれます.n/2番目の親ノード交換が後の要素を交換した可能性があり、n/2-1番目の親ノードが後の同じ要素を交換しなかった場合、この2つの同じ要素間の安定性が破壊されます.したがって,スタックソートは安定したソートアルゴリズムではない.リファレンス
https://baike.baidu.com/item/ソートアルゴリズムの安定性