選択ソート

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

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

選択ソートアルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があるとします。beg と end の 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(n²)のオーダーです。ループの数を数えることによって計算することもできます。複雑さを増す n 反復の合計 2つのループがあります：n * n = n²

• 最悪のケース

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

• 最良のケース

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

空間計算量

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