選択ソート：アルゴリズムの説明 Python コードの例
サラ・チェン
選択ソートとは何ですか?
選択ソート 項目のランダムなリストを昇順に並べ替えるのに使用される比較並べ替えアルゴリズムです。 比較には多くの追加スペースは必要ありません。 一時変数用に追加のメモリ空間が XNUMX つだけ必要になります。
これはとして知られています 所定の位置に ソート。選択ソートはO(n2) ここで、n はリスト内のアイテムの合計数です。時間計算量は、リストをソートするために必要な反復回数を測定します。リストは 2 つのパーティションに分割されます。最初のリストにはソートされたアイテムが含まれ、2 番目のリストにはソートされていないアイテムが含まれます。
デフォルトでは、並べ替えられたリストは空で、並べ替えられていないリストにはすべての要素が含まれます。 次に、ソートされていないリストで最小値がスキャンされ、その最小値がソートされたリストに入れられます。 このプロセスは、すべての値が比較および並べ替えられるまで繰り返されます。
選択の並べ替えはどのように機能しますか?
未ソートのパーティションの最初の項目が右側のすべての値と比較され、それが最小値であるかどうかが確認されます。 最小値でない場合は、その位置が最小値と交換されます。
例:
- たとえば、最小値のインデックスが 3 の場合、インデックス 3 の要素の値はインデックス 0 に配置され、インデックス 0 にあった値はインデックス 3 に配置されます。最小値の場合は、その位置を返します。
- 最小値として決定された要素は、ソートされたリストである左側のパーティションに移動されます。
- パーティション化された側には 1 つの要素があり、パーティション化されていない側には (n – XNUMX) 個の要素があります。n はリスト内の要素の総数です。 このプロセスは、すべての項目が比較され、その値に基づいて並べ替えられるまで何度も繰り返されます。
問題の定義
ランダムな順序の要素のリストは昇順で並べ替える必要があります。次のリストを例として考えてみましょう。
【21,6,9,33,3]
上記のリストを並べ替えると、次の結果が得られます。
【3,6,9,21,33]
解決策（アルゴリズム）
ステップ1） 配列の合計サイズである n の値を取得します。
ステップ2） リストをソートされたセクションとソートされていないセクションに分割します。 ソートされたセクションは最初は空ですが、ソートされていないセクションにはリスト全体が含まれています
ステップ3） 分割されていないセクションから最小値を選択し、それを並べ替えられたセクションに配置します。
ステップ4） リスト内のすべての要素が並べ替えられるまで、このプロセスを (n – 1) 回繰り返します。
視覚的表現
次の画像は、5 つの要素のリストが与えられた場合に、選択ソート アルゴリズムが値をソートするときに値をどのように反復処理するかを示しています。
次の画像はソートされていないリストを示しています
ステップ1）
最初の値 21 が残りの値と比較され、それが最小値であるかどうかがチェックされます。
3 は最小値なので、21 と 3 の位置が入れ替わります。 背景が緑色の値は、リストのソートされたパーティションを表します。
ステップ2）
未ソートのパーティションの最初の要素である値 6 が残りの値と比較され、より低い値が存在するかどうかが確認されます。
値 6 は最小値であるため、その位置を維持します。
ステップ3）
ソートされていないリストの値 9 を持つ最初の要素が残りの値と比較され、それが最小値であるかどうかがチェックされます。
値 9 は最小値であるため、ソートされたパーティション内での位置が維持されます。
ステップ4）
値 33 が残りの値と比較されます。
値 21 は 33 より小さいため、位置が交換されて上記の新しいリストが作成されます。
ステップ5）
分割されていないリストには値が XNUMX つだけ残っています。 したがって、すでに並べ替えられています。
最終的なリストは上の画像のようになります。
選択ソートプログラムの使用 Python 3
次のコードは、選択ソートの実装を示しています。 Python 3
def selectionSort( itemsList ):
n = len( itemsList )
for i in range( n - 1 ):
minValueIndex = i
for j in range( i + 1, n ):
if itemsList[j] < itemsList[minValueIndex] :
minValueIndex = j
if minValueIndex != i :
temp = itemsList[i]
itemsList[i] = itemsList[minValueIndex]
itemsList[minValueIndex] = temp
return itemsList
el = [21,6,9,33,3]
print(selectionSort(el))
上記のコードを実行すると、次の結果が生成されます。
[3, 6, 9, 21, 33]
コードの説明
コードの説明は次のとおりです
コードの説明は次のとおりです。
- selectionSort という名前の関数を定義します
- リスト内の要素の総数を取得します。 これは、値を比較するときに実行されるパスの数を決定するために必要です。
- 外側のループ。 ループを使用してリストの値を反復処理します。 反復回数は (n – 1) です。 n の値は 5 なので、(5 – 1) は 4 になります。これは、外側の反復が 4 回実行されることを意味します。 各反復で、変数 i の値が変数 minValueIndex に割り当てられます。
- 内側のループ。 ループを使用して、左端の値を右側の他の値と比較します。 ただし、j の値はインデックス 0 から始まりません。(i + 1) から始まります。 これにより、すでに並べ替えられた値が除外されるため、まだ並べ替えられていない項目に焦点が当てられます。
- ソートされていないリストから最小値を見つけて、それを適切な位置に配置します。
- スワップ条件が true の場合、minValueIndex の値を更新します。
- インデックス番号 minValueIndex と i の値を比較して、等しくないかどうかを確認します。
- 左端の値は一時変数に格納されます
- 右側から低い値が最初の位置になります。
- 一時値に格納された値は、以前に最小値が保持されていた位置に格納されます
- ソートされたリストを関数の結果として返します。
- ランダムな数字を含むリストelを作成します
- パラメータとして el を渡して選択ソート関数を呼び出した後、ソートされたリストを出力します。
選択ソートの時間計算量
ソートの複雑さは、リストをソートするのにかかる実行回数を表すために使用されます。実装には 2 つのループがあります。
リストから値を XNUMX つずつ選択する外側のループは n 回実行されます。n はリスト内の値の総数です。
外側のループの値を残りの値と比較する内側のループも、リスト内の要素の合計数 n の場合、n 回実行されます。
したがって、実行回数は (n * n) となり、O(n2).
選択ソートには複雑さの 3 つのカテゴリがあります。
- 最悪の場合 – ここでは、提供されたリストが降順で表示されます。 このアルゴリズムは、[Big-O] O(n として表される最大実行数を実行します)2)
- 最良の場合 – これは、提供されたリストがすでにソートされている場合に発生します。アルゴリズムは、[Big-Omega] ?(nで表される最小実行回数を実行します。2)
- 平均的なケース – これはリストがランダムな順序になっている場合に発生します。平均複雑度は [Big-theta] ?(n として表されます。2)
選択ソートでは、値の交換に使用される 1 つの一時変数が必要なため、空間計算量は O(XNUMX) になります。
選択ソートをいつ使用するか?
選択並べ替えは、次の場合に最適に使用されます。
- 項目の小さなリストを昇順に並べ替える必要があります
- 値を交換するコストがわずかな場合
- リスト内のすべての値がチェックされていることを確認する必要がある場合にも使用されます。
選択ソートの利点
選択ソートの利点は次のとおりです。
- 小さなリストでは非常にうまく機能します
- これはインプレースアルゴリズムです。 仕分けに多くのスペースを必要としません。 一時変数を保持するために必要な追加のスペースは XNUMX つだけです。
- すでに並べ替えられているアイテムに対して適切に機能します。
選択ソートの欠点
選択ソートの欠点は次のとおりです。
- 巨大なリストを操作する場合、パフォーマンスが低下します。
- 並べ替え中に行われる反復回数は n の XNUMX 乗であり、n はリスト内の要素の総数です。
- クイックソートなどの他のアルゴリズムは、選択ソートに比べてパフォーマンスが優れています。
製品概要
- 選択ソートは、ランダムなリストを順序付きリストにソートするために使用されるインプレース比較アルゴリズムです。これは、O(n2)
- リストは、ソートされたセクションとソートされていないセクションの XNUMX つのセクションに分かれています。 最小値が未ソートのセクションから選択され、ソートされたセクションに配置されます。
- すべてのアイテムが並べ替えられるまで、この作業が繰り返されます。
- 擬似コードを実装する Python 3は、XNUMXつのforループとif文を使用して、スワップが必要かどうかを確認します。
- 時間の複雑さは、リストをソートするために必要なステップの数を測定します。
- 最悪の場合の時間計算量は、リストが降順の場合に発生します。その時間計算量は[Big-O] O(n2)
- 最も時間の計算量が多いのは、リストがすでに昇順になっているときです。その場合の時間計算量は [Big-Omega] ?(n2)
- 平均ケースの時間計算量は、リストがランダムな順序になっている場合に発生します。その時間計算量は [Big-theta] ?(n2)
- 選択ソートは、ソートする項目のリストが少なく、値を交換するコストが重要ではなく、すべての値のチェックが必須である場合に最適です。
- 選択ソートは巨大なリストではうまく機能しません
- クイックソートなどの他のソートアルゴリズムは、選択ソートと比較するとパフォーマンスが優れています。
