DAA-選択ソート

このタイプのソートは、エレメントを繰り返しソートすることで機能するため、*選択ソート*と呼ばれます。次のように機能します。最初に配列の最小値を見つけて最初の位置の要素と交換し、次に2番目に小さい要素を見つけて2番目の位置の要素と交換し、配列全体がこのようになるまで続けますソート済み。

Algorithm: Selection-Sort (A)
fori ← 1 to n-1 do
   min j ← i;
   min x ← A[i]
   for j ←i + 1 to n do
      if A[j] < min x then
         min j ← j
         min x ← A[j]
   A[min j] ← A [i]
   A[i] ← min x

選択ソートは、最も単純なソート手法の1つであり、小さなファイルに対して非常にうまく機能します。各アイテムが実際に一度だけ移動されるため、非常に重要なアプリケーションがあります。

セクションの並べ替えは、非常に大きなオブジェクト（レコード）と小さなキーを持つファイルの並べ替えに適した方法です。配列が既に降順でソートされていて、昇順でソートしたい場合、最悪のケースが発生します。

それにもかかわらず、選択ソートアルゴリズムに必要な時間は、ソートされる配列の元の順序にあまり敏感ではありません： A [j] _ < '_min x' がすべての場合に正確に同じ回数実行されるかどうかのテスト。

選択ソートは、配列のソートされていない部分の最小要素を見つけるために、ほとんどの時間を費やします。選択ソートとバブルソートの類似性を明確に示しています。

バブルソートは、各段階で最大の残りの要素を選択しますが、配列のソートされていない部分に何らかの順序を付与するための労力を浪費します。

選択ソートは、最悪の場合と平均的な場合の両方で2次であり、追加のメモリを必要としません。

*_1_* から *_n-1_* までの各 *_i_* には、1回の交換と *_n-i_* の比較があるため、合計で *_n-1_* の交換と

*_（n − 1）+（n − 2）+ ... + 2 + 1 = n（n − 1）/2_* 比較。

これらの観察結果は、入力データが何であっても保持されます。

最悪の場合、これは2次の場合がありますが、平均的な場合、この量は O（n log n） です。これは、* Selectionソートの実行時間が入力にまったく影響されないことを意味します*。

実装

Void Selection-Sort(int numbers[], int array_size) {
   int i, j;
   int min, temp;
   for (i = 0; I < array_size-1; i++) {
      min = i;
      for (j = i+1; j < array_size; j++)
         if (numbers[j] < numbers[min])
            min = j;
      temp = numbers[i];
      numbers[i] = numbers[min];
      numbers[min] = temp;
   }
}

例

Unsorted list:

|5 |2 |1 |4 |3

1 ^ st ^反復：

最小= 5

2 <5、最小= 2

1 <2、最小= 1

4> 1、最小= 1

3> 1、最小= 1

Swap 5 and 1

|1 |2 |5 |4 |3

2 ^ nd ^反復：

最小= 2

2 <5、最小= 2

2 <4、最小= 2

2 <3、最小= 2

No Swap

|1 |2 |5 |4 |3

3 ^ rd ^反復：

最小= 5

4 <5、最小= 4

3 <4、最小= 3

Swap 5 and 3

|1 |2 |3 |4 |5

4 ^ th ^反復：

最小= 4

4 <5、最小= 4

No Swap

|1 |2 |3 |4 |5

最後に、

the sorted list is

|1 |2 |3 |4 |5

Design-and-analysis-of-algorithms-selection-sort

目次

DAA-選択ソート

実装

例

1 ^ st ^反復：

2 ^ nd ^反復：

3 ^ rd ^反復：

4 ^ th ^反復：