선택 정렬

선택 정렬은 간단한 정렬 알고리즘입니다. 배열을 정렬 된 부분과 정렬되지 않은 부분 배열의 두 부분으로 나누어 작동합니다. 선택 정렬은 정렬되지 않은 하위 배열 내에서 가장 작은 요소를 찾아 정렬 된 하위 배열의 마지막 인덱스로 이동합니다. 최대 n개의 스왑 만 필요하기 때문에 스왑 작업이 매우 비용이 많이 드는 경우에 사용됩니다.

선택 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

선택 정렬 예

배열이(5,3,4,2,1,6)이라고 가정합니다. 선택 정렬 알고리즘을 사용하여 정렬합니다.

• 첫 번째 반복

최소 요소 :A[4]= 1

스왑 (A[4],A[0]). 배열은(1) (3,4,2,5,6)이됩니다.

• 두 번째 반복

최소 요소 :A[3]= 2

스왑 (A[3],A[1]). 배열은(1,2) (4,3,5,6)이됩니다.

• 세 번째 반복

최소 요소 :A[3]= 3

스왑 (A[3],A[2]). 배열은(1,2,3) (4,5,6)이됩니다.

• 네 번째 반복

최소 요소 :A[3]= 4

스왑 (A[3],A[3]). 배열은(1,2,3,4) (5,6)이됩니다.

• 다섯 번째 반복

최소 요소 :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 반복의 총 두 개의 루프가 있습니다. n*n = n²

• 최악의 경우

최악의 경우 시간 복잡도는 [Big O] : O(n²)입니다.

• 베스트 케이스

최적의 시간 복잡도는 [Big Omega] : O(n²)입니다. 최악의 시간 복잡성과 동일합니다.

공간 복잡성

선택 정렬 알고리즘의 공간 복잡성은 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(1)입니다.