このチュートリアルでは、Python で選択ソート アルゴリズムを実装します。これは、少ないスワップを使用する非常に単純なアルゴリズムです。
Javaリストノード
このアルゴリズムでは、各パスでソートされていない配列から最小の要素を選択し、ソートされていない配列の先頭と交換します。このプロセスは、すべての要素が正しい場所に配置されるまで続きます。これはシンプルなインプレース比較並べ替えアルゴリズムです。
選択ソートの仕組み
以下は、Python での選択ソートの動作を説明する手順です。
ソートされていない配列を選択してソート アルゴリズムを適用してみましょう。
[30、10、12、8、15、1]
完全な形式
ステップ1： 配列の長さを取得します。
長さ = len(配列) → 6
ステップ2： まず、最初の要素を最小要素として設定します。
ステップ - 3: 次に、最小値と 2 番目の要素を比較します。 2 番目の要素が最初の要素より小さい場合、それを最小値として割り当てます。
再度、2 番目の要素を 3 番目の要素と比較し、3 番目の要素が 2 番目の要素より小さい場合は、それを最小値として割り当てます。このプロセスは、最後の要素が見つかるまで続きます。
ステップ - 4: 各反復の後、最小要素がソートされていない配列の前で交換されます。
春のMVC
ステップ - 5: ソートされた配列が得られるまで、2 番目から 3 番目のステップが繰り返されます。
選択ソートアルゴリズム
選択ソートアルゴリズムは次のとおりです。
アルゴリズム
selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let's understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum> 説明 -
上記のコードを理解しましょう -
冬眠とは何ですか
- まず、 選択ソート() 引数として配列を取る関数。
- この関数では、値を比較するパスの数を決定するために使用される配列の長さを取得します。
- 見てわかるように、外側のループと内側のループという 2 つのループを使用しています。外側のループは、リストの値を反復処理するために使用されます。このループは 0 から (length-1) まで反復されます。したがって、最初の反復は (5-1) または 4 回実行されます。各反復で、変数 i の値が変数に割り当てられます。
- 内側のループは、右側の要素の各値を左端の要素の他の値と比較するために使用されます。したがって、2 番目のループは i+1 から反復を開始します。ソートされていない値のみが選択されます。
- ソートされていないリスト内の最小要素を見つけて、minIndex の位置を更新します。
- 値を配列の先頭に置きます。
- 反復が完了すると、ソートされた配列が返されます。
- 最後に、ソートされていない配列を作成し、 選択ソート() ソートされた配列を出力します。
選択ソートの時間計算量
時間計算量は、アルゴリズムがソートにどれくらいの時間を要するかという点で重要です。選択ソートには 2 つのループがあります。外側のループは n 回実行されます (n は要素の総数)。
内側のループも n 回実行されます。値の残りの部分を外側のループの値と比較します。したがって、n*n 回の実行があります。したがって、マージソートアルゴリズムの時間計算量は O(n2）。
時間計算量は 3 つのカテゴリに分類できます。