선택 정렬(Selection Sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 선택 정렬(selection sort)는 비교적 간단한 정렬 알고리즘이다.

  ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다.

② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다.

  ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다.

③ 선택 정렬의 기본 원리는 다음과 같다.

  ㉠ 정렬된 부분 배열과 정렬되지 않은 부분 배열로 나눈다.

  ㉡ 정렬되지 않은 부분 배열에서 가장 작은(혹은 가장 큰) 요소를 찾는다.

  ㉢ 정렬되지 않은 부분의 첫 번째 인덱스(혹은 제일 뒤 인덱스)와 스왑한다.

  ㉣ ㉡과 ㉢를 반복해서 시행해서 전체 배열이 정렬될 때까지 정렬되지 않은 부분 배열의 요소를 정렬된 배열의 끝으로 옮긴다.

④ 선택 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

⑤  선택 정렬의 시간 복잡도는 O(n^2)이다.

  ㉠ 시행할 때마다, 정렬된 배열의 크기는 1 증가하고, 정렬되지 않은 배열의 크기는 1 감소하기 때문에 다음과 같다.

  ㉡ 배열의 크기가 n 일 때, n-1번을 비교해야 하기 때문에 다음과 같이 계산할 수 있다.

 

⑥ 선택 정렬의 구현 코드는 다음과 같다.