선택 정렬 (Selection Sort)

 

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

주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체한다.

맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

 

시간 복잡도

 

(n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2만큼의 비교가 일어나기 때문에 n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다.

 

최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)로 동일하다.

 

 

공간 복잡도

 

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)

 

 

장점

 

• 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
• In-place sort

 

 

단점

 

• 시간 복잡도가 O(n^2)이므로 비효율적이다.
• Unstable Sort (동일한 key값을 정렬했을 때 순서가 바뀐다)

 

 

Reference

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview