選択ソート

選択ソート

クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$比較、交換${\displaystyle O(n)}$
最高の パフォーマンス	${\displaystyle O(n^{2})}$比較、スワップ${\displaystyle O(1)}$
平均的 なパフォーマンス	${\displaystyle O(n^{2})}$比較、交換${\displaystyle O(n)}$
最悪の場合の 空間複雑度	${\displaystyle O(1)}$補助
最適	いいえ

コンピュータサイエンスにおいて、選択ソートはインプレース 比較 ソートアルゴリズムです。これはO ( n2 )^の時間計算量を持ち、大きなリストでは非効率的で、一般的に同様の挿入ソートよりもパフォーマンスが悪くなります。選択ソートは単純であることで知られており、特に補助メモリが限られている 場合など、特定の状況ではより複雑なアルゴリズムよりもパフォーマンス上の利点があります。

アルゴリズムは、入力リストを 2 つの部分に分割します。1 つはリストの先頭 (左側) で左から右に構築されるアイテムのソートされたサブリスト、もう 1 つはリストの残りの部分を占める残りのソートされていないアイテムのサブリストです。最初は、ソートされたサブリストは空で、ソートされていないサブリストが入力リスト全体です。アルゴリズムは、ソートされていないサブリスト内の最小 (またはソート順に応じて最大) の要素を見つけ、それを左端のソートされていない要素と交換 (スワップ) し (ソート順に配置)、サブリストの境界を 1 要素右に移動します。

選択ソートの時間効率は 2 次関数であるため、選択ソートよりも時間の計算量が少ないソート手法は数多くあります。

以下は、5 つの要素をソートするこのソート アルゴリズムの例です。

(最後の 2 行は何も変更されていないように見えます。これは、最後の 2 つの数字がすでに順番になっているためです。)

選択ソートは、リンク リストなど、追加と削除を効率的に行うリスト構造でも使用できます。この場合、リストの残りから最小の要素を削除し、それをこれまでにソートした値の末尾に挿入するのが一般的です。例:

ar[] = 64 25 12 22 11

// arr[0...4]の最小要素を見つける
// 先頭に配置します
11 25 12 22 64

// arr[1...4]の最小要素を見つける
// arr[1...4]の先頭に配置します
11 12 25 22 64

// arr[2...4]の最小要素を見つける
// arr[2...4]の先頭に配置します
11 12 22 25 64

// arr[3...4]の最小要素を見つける
// arr[3...4]の先頭に配置します
11 12 22 25 64

以下はCでの実装です。

/* a[0]からa[aLength-1]はソートする配列です */
整数i , j ; 
int aLength ; // aの長さに初期化  

/* 配列全体の位置を進める */
/* (単一要素は最小要素でもあるため、i < aLength-1 にすることができます) */
( i = 0 ; i < aLength -1 ; i ++ )の場合       
{
    /* ソートされていない a[i .. aLength-1] 内の最小要素を見つける */

    /* 最小値が最初の要素であると仮定します */
    整数jMin = i ;   
    /* i の後の要素をテストして最小値を見つける */
    ( j = i + 1 ; j < aLength ; j ++ )の場合       
    {
        /* この要素が小さい場合は、それが新しい最小値になります */
        もし( a [ j ] < a [ jMin ])   
        {
            /* 新しい最小値を発見しました。そのインデックスを記憶します */
            j最小値= j ;  
        }
    }

    ( jMin != i )の場合    
    {
        スワップ( &a a [私], &a a [ jMin ]); 
    }
}

選択ソートは、ループが配列内のデータに依存しないため、他のソートアルゴリズムと比較して分析が難しくありません。最小値を選択するには、要素をスキャンして（比較を行って）、それを最初の位置にスワップする必要があります。次に低い要素を見つけるには、残りの要素をスキャンして（比較を行って）などを行う必要があります。したがって、比較の合計数は ${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n-2}$

${\displaystyle (n-1)+(n-2)+\dots +1=\sum _{i=1}^{n-1}i}$

等差数列により、

${\displaystyle \sum _{i=1}^{n-1}i={\frac {(n-1)+1}{2}}(n-1)={\frac {1}{2}}n(n-1)={\frac {1}{2}}(n^{2}-n)}$

比較の数の点で 複雑です。${\displaystyle O(n^{2})}$

二次ソートアルゴリズム（ Θ( n2 )の単純な平均ケースを持つソートアルゴリズム）の中で、選択ソートはバブルソートやノームソートよりもほぼ常に優れています。挿入ソートは、 k回目の反復^後に配列の最初の要素がソートされた順序になるという点で非常に似ています。挿入ソートの利点は、最初の要素を配置するために必要な数の要素のみをスキャンすることです。一方、選択ソートは最初の要素を見つけるために残りのすべての要素をスキャンする必要があります。 ${\displaystyle k}$${\displaystyle k+1}$${\displaystyle k+1}$

単純な計算により、挿入ソートでは通常、選択ソートの約半分の比較が実行されますが、ソート前の配列の順序に応じて、同じかそれよりはるかに少ない比較が実行されることがわかります。選択ソートは配列の順序に関係なく同じように実行されるのに対し、挿入ソートの実行時間はかなり異なる可能性があるという点は、一部のリアルタイムアプリケーションにとって利点であると考えられます。ただし、配列がすでにソートされているか「ソートに近い」状態である場合に、挿入ソートの方がはるかに効率的に実行されるという点で、これは挿入ソートにとって利点となる場合が多いです。

書き込み回数の点では選択ソートの方が挿入ソートよりも優れていますが (スワップ回数と最大スワップ回数、各スワップは 2 回の書き込み)、これは最大でn回の書き込みを実行するサイクル ソートによって達成される理論上の最小値の約 2 倍です。これは、 EEPROMやフラッシュ メモリなど、書き込みが読み取りよりも大幅にコストがかかる場合に重要になります。書き込みのたびにメモリの寿命が短くなるためです。 ${\displaystyle n-1}$${\displaystyle n(n-1)/2}$

選択ソートは、分岐のないコードで最小値の位置を見つけ、無条件にスワップを実行することで、 CPU分岐予測子の利益のために予測不可能な分岐なしで実装できます。

最後に、選択ソートは、マージソートなどの分割統治アルゴリズムに比べて、大きな配列では大幅にパフォーマンスが劣ります。ただし、挿入ソートまたは選択ソートは、通常、小さな配列 (つまり、10 ～ 20 要素未満) ではどちらも高速です。再帰アルゴリズムの実際の便利な最適化は、「十分に小さい」サブリストに対して挿入ソートまたは選択ソートに切り替えることです。 ${\displaystyle \Theta (n\log n)}$

ヒープソートは、 「適切なデータ構造を使用した選択ソートの実装に他ならない」と説明されています。 ^{[1]ヒープソートは、通常の選択ソートの内部ループの代わりに}暗黙の ヒープデータ構造を使用して、時間内に各最下位要素を見つけて削除することで基本アルゴリズムを大幅に改善し、合計実行時間を に短縮します。 ${\displaystyle \Theta (\log n)}$${\displaystyle \Theta (n)}$${\displaystyle \Theta (n\log n)}$

選択ソートの双方向のバリエーション (カクテル シェーカー ソートに似ていることから、二重選択ソートまたはカクテル ソートと呼ばれることもあります)では、各パスでリスト内の最小値と最大値の両方が検索されます。通常の選択ソートでは項目ごとに 1 回の比較が必要ですが、この方法では 2 つの項目ごとに 3 回の比較 (要素のペアを比較し、大きい方を最大値と比較し、小さい方を最小値と比較) が必要ですが、必要なパスの数は半分で済み、実質 25% の節約になります。

選択ソートは、ステップ 2 でスワップするのではなく、最小値を最初の位置に挿入し、その間の値を上にシフトすると、安定したソートとして実装できます。ただし、この変更には、リンク リストなどの効率的な挿入または削除をサポートするデータ構造が必要になるか、書き込みの実行が必要になります。 ${\displaystyle \Theta (n^{2})}$

ビンゴソートの変形では、残っている項目を繰り返し調べて最大値を見つけ、その値を持つすべての項目を最終的な場所に移動することで、項目をソートします。 ^[2]カウンティングソートと同様に、これは重複する値が多い場合に効率的な変形です。選択ソートでは、移動した項目ごとに残りの項目を 1 回通過しますが、ビンゴソートでは値ごとに 1 回通過します。最大値を見つけるための最初のパスの後、後続のパスでは、次の疑似コードのように、次の値を見つけながら、その値を持つすべての項目を最終的な場所に移動します(配列はゼロベースで、for ループにはPascalのように上限と下限の両方が含まれます)。

ビンゴ(配列A ) 


  { この手順は、最大の項目を繰り返し末尾に移動する
ことで昇順に並べ替えます。 } begin 
last := length ( A ) - 1 ;        

    { 最初の反復は、
      後続の反復と非常によく似た外観になるように記述されていますが、スワップはありません。 } 
nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then nextMax := A [ i ] ; while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ;      
            
            
              
            
            

    while last > 0 do begin { 各メイン ループは          、prevMax に等しい項目を入れ替えながら、新しい nextMax を検索します。 } prevMax := nextMax ; nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then if A [ i ] <> prevMax then nextMax := A [ i ] ; else begin swap ( A [ i ] , A [ last ]) ; last := last - 1 ; end while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ; end ; end ;     
        

          
          
                
                 
                     
                       
                  
                      
                         
                 
                
                
    

したがって、平均して同じ値を持つ項目が 2 つ以上ある場合、ビンゴ ソートは選択ソートよりも内部ループの実行回数が少ないため、より高速になると予想されます。

• 選択アルゴリズム
• Javaでの選択ソート

Wikibookアルゴリズム実装には、選択ソートに関するページがあります。

• アニメーションソートアルゴリズム: Wayback Machineの選択ソート(2015 年 3 月 7 日アーカイブ) – グラフィカルなデモンストレーション