선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

 : 처리되지 않은 데이터 중, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘

   = 매번 현재 범위에서 가장 작은 데이터를 골라 가장 앞쪽으로 보내는 과정을 반복

 : 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 : 과정이 반복될 수록 탐색 범위 줄어듦

 : 알고리즘이 단순하다는 장점

 : 정렬 과정에서 정렬을 위한 비교 횟수는 많지만, 실제 값이 교환되는 횟수는 적음 -> 교환이 잦은 자료 정렬에 효율적

 : 배열 안에서 교환하는 방식 -> 추가적인 메모리 공간 필요로 하지 않음 (제자리 정렬 = in-place sorting)

 : 불안정 정렬이라는 단점 존재

 

선택 정렬의 과정

1. 주어진 데이터들 중 가장 작은 데이터를 찾는다.

2. 그 값을 맨 앞에 위치하는 값과 교체

3. 아직 처리되지 않은 데이터 범위에서 1~2의 과정 반복

 

선택 정렬의 시간 복잡도와 공간 복잡도

최선/평균/최악의 시간 복잡도 : O(N^2)

공간 복잡도 : O(n)