選択ソートアルゴリズム

選択ソートとは何ですか?

選択並べ替えアルゴリズムは、配列を並べ替えられた部分と並べ替えられていない部分の 2 つの部分に分割します。最初は、ソートされた部分は空で、ソートされていない部分にはすべての要素が含まれています。このアルゴリズムは、未ソート部分から最小 (またはソート順序によっては最大) の要素を見つけて、それを未ソート部分の最初の要素と交換することによって機能します。このプロセスは、配列全体がソートされるまで続きます。

アルゴリズムのステップ

1. 配列内の最初の要素から開始し、それが最小であると仮定します。
2. この要素を配列内の他の要素と比較します。
3. より小さい要素を見つけた場合は、それを最初の要素と交換します。
4. 配列内の次の要素に移動し、ソートされていない残りの要素に対してこのプロセスを繰り返します。
5. 配列全体がソートされるまでこのプロセスを続けます。

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

パス 1:

• インデックス 0 と配列の残りの部分の間の最小要素は 11 です。
• 64 を 11 と交換します。

最初のパス後の配列: [11, 25, 12, 22, 64]

パス 2:

• 次に、インデックス 1 から始まる部分配列に注目します。25、12、22、64 の間の最小要素は 12 です。
• 25 を 12 と交換します。

2 回目のパス後の配列: [11, 12, 25, 22, 64]

パス 3:

• 25、22、64 の間の最小要素は 22 です。
• 25 と 22 を交換します。

3 回目のパス後の配列: [11, 12, 22, 25, 64]

パス 4:

• サブ配列には 25、64 が含まれています。それらはすでに順序が整っているため、交換する必要はありません。

最終的にソートされた配列: [11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

ソートされた配列: [11, 12, 22, 25, 64]

選択ソートの時間計算量:

• 最良のケース: O(n²)

• 平均ケース: O(n²)

• 最悪の場合: O(n²)

選択並べ替えは小さなデータセットに対しては良好に機能しますが、時間計算量が O(n²) であるため、大きな配列には理想的ではありません。ただし、実装は簡単で、選択並べ替えが適切に行われる (追加のメモリを必要としない) ため、メモリが懸念される場合に役立ちます。

メリットとデメリット

利点:

• 理解と実装が簡単です。

• 小さなリストでは良好なパフォーマンスを発揮します。

• 配列を適切にソートするため、追加のメモリは必要ありません。

欠点:

• 時間計算量が O(n²) であるため、大規模なデータセットの場合は非効率です。

• これは安定した並べ替えアルゴリズムではないため、等しい要素が互いに対する相対的な順序を維持できない可能性があります。

以上が選択ソートアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。