選択ソート

  1. 選択ソートアルゴリズム
  2. 選択ソートの例
  3. 選択ソートアルゴリズムの実装
  4. 選択ソートアルゴリズムの複雑さ

選択ソートは単純なソートアルゴリズムです。これは、配列を 2つの部分(ソートされたサブ配列とソートされていないサブ配列)に分割することによって機能します。選択ソートは、ソートされていないサブアレイ内の最小の要素を見つけ、それをソートされたサブアレイの最後のインデックスに移動します。最大で n スワップのみが必要なため、スワップ操作に非常にコストがかかる場合に使用されます。

選択ソートアルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があるとします。begend の 2つの変数を取り、開始要素と終了要素のインデックスを格納します。

  • ソートされていないサブアレイの最初の要素のインデックスを最小要素インデックス min として選択します。
  • min の値を残りの要素と比較し、小さい要素が見つかった場合はこの要素にリセットします。
  • min の要素を、ソートされたサブ配列の最後のインデックスの要素と交換します。
  • ソートされていないサブ配列の残りの要素について、上記の手順を「n-2」回繰り返します。

選択ソートの例

配列 (5,3,4,2,1,6) があるとします。選択ソートアルゴリズムを使用してソートします。

- 最初の反復

最小要素: A [4] = 1

スワップ( A [4]A [0])。配列は次のようになります: (1)(3,4,2,5,6)

- 2 回目の反復

最小要素: A [3] = 2

スワップ( A [3]A [1])。配列は次のようになります: (1,2)(4,3,5,6)

- 3 回目の反復

最小要素: A [3] = 3

スワップ( A [3]A [2])。配列は次のようになります: (1,2,3)(4,5,6)

- 4 回目の反復

最小要素: A [3] = 4

スワップ( A [3]A [3])。配列は次のようになります: (1,2,3,4)(5,6)

- 5 回目の反復

最小要素: A [4] = 5

スワップ( A [4]A [4])。配列は次のようになります: (1,2,3,4,5)(6)

最後の要素はすでにソートされています。ソートされた配列は次のようになります: (1,2,3,4,5,6)

選択ソートアルゴリズムの実装

#include<bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
 
    for (int i = 0; i < n-1; i++)  
    {  
        // Find the minimum element for index i  
        int min = i;  
        for (int j = i+1; j < n; j++)  
        if (arr[j] < arr[min])  
            min = j;
        // Put element in sorted position  
        swap(arr[min], arr[i]);  
    }  
}
int main() {

    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    selectionSort(arr, n); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

選択ソートアルゴリズムの複雑さ

時間の複雑さ

  • 平均のケース

平均して、n-i の比較は、挿入ソートの i 回目パスで行われます。したがって、n 回の反復がある場合、平均時間計算量は次のようになります。

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

したがって、時間計算量は [Big Theta]:O(n2)のオーダーです。ループの数を数えることによって計算することもできます。複雑さを増す n 反復の合計 2つのループがあります:n * n = n2

  • 最悪のケース

最悪の場合は、ピボット要素が常に配列の最大要素か最小要素のいずれかである場合です。この場合、すべての要素が 1つの部分配列に収まるため、最大の n 呼び出しを行わなければならない。最悪の場合の時間的複雑さは [Big O]:O(n2)です。

  • 最良のケース

最良の時間計算量は [BigOmega]:O(n2) です。これは、最悪の場合の時間計算量と同じです。

### 空間複雑度

一時変数以外の追加メモリは必要ないため、選択ソートアルゴリズムの空間の複雑さは O(1) です。

関連記事 - Sort Algorithm

  • 再帰的バブルソート
  • バブルソート