선택 정렬

Harshit Jindal 2023년10월12일
  1. 선택 정렬 알고리즘
  2. 선택 정렬 예
  3. 선택 정렬 알고리즘 구현
  4. 선택 정렬 알고리즘 복잡성
선택 정렬

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

선택 정렬 알고리즘

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

  • 정렬되지 않은 하위 배열의 첫 번째 요소 색인을 최소 요소 색인 min으로 선택합니다.
  • min의 값을 나머지 요소와 비교하고 더 작은 요소가 발견되면이 요소로 재설정합니다.
  • min에있는 요소를 정렬 된 하위 배열의 마지막 인덱스에있는 요소로 바꿉니다.
  • 정렬되지 않은 하위 배열의 나머지 요소에 대해 위의 n-2단계를 반복합니다.

선택 정렬 예

배열이(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(n2) 정도입니다. 루프 수를 세어 계산할 수도 있습니다. 복잡하게 만드는n 반복의 총 두 개의 루프가 있습니다. n*n = n2

  • 최악의 경우

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

  • 베스트 케이스

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

공간 복잡성

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

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

관련 문장 - Sort Algorithm