정렬 / 선택 정렬 / 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

이 글에서는 정렬 알고리즘 중 가장 직관적인 선택 정렬(Selection Sort)에 대해서 알아보겠습니다.

 

 

선택 정렬(Selection Sort)

 

대상 범위에서 최솟값을 찾아 그 값과 범위의 맨 앞에 있는 값을 서로 바꾸는 과정을 반복하는 정렬 기법.

 

(해당 과정이 한 번 끝날 때마다 범위 안의 맨 앞에 있는 값은 정렬이 끝났으므로 정렬 대상 범위에서 제외합니다.)

 

이해를 돕기 위해 아래의 예시를 통해 설명해보겠습니다. 

이 때 굵게 표시 된 부분은 이미 정렬이 끝난 것을 의미합니다.

1 10 5 8 7 6 4 3 2 9

 

1 10 5 8 7 6 4 3 2 9

 

1 2 5 8 7 6 4 3 10 9

 

1 2 3 8 7 6 4 5 10 9

 

1 2 3 4 7 6 8 5 10 9

 

1 2 3 4 5 6 8 7 10 9

 

1 2 3 4 5 6 8 7 10 9

 

1 2 3 4 5 6 7 8 10 9

 

1 2 3 4 5 6 7 8 9 10

 

1 2 3 4 5 6 7 8 9 10

 

1 2 3 4 5 6 7 8 9 10

 

시간 복잡도

 

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
• ...
• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

 

공간 복잡도

 

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

 

특징

 

장점

• 알고리즘이 단순하다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. -> 제자리 정렬(in-place sorting)
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• 불안정 정렬(Unstable Sort) 이다.

 

 

* 안정 정렬 

- 안정 정렬이란 정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 되는 정렬 알고리즘

 

ex)

[3, 2, 1, 5, 7, 5] 라는 배열을 오름차순 정렬할 때, 

 

[1, 2, 3, 5, 5, 7]이 된다면 안정 정렬

[1, 2, 3, 5, 5, 7]이 될 수 있다면 불안정 정렬

 

아래의 글을 참고하여 작성하였습니다.

 

https://coding-factory.tistory.com/615

[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도

 

https://riverblue.tistory.com/39#:~:text=%EC%95%88%EC%A0%95%20%EC%A0%95%EB%A0%AC%EC%9D%B4%EB%9E%80%20%EC%A0%95%EB%A0%AC%20%EC%A0%84,%EC%9D%84%20%EC%95%88%EC%A0%95%20%EC%A0%95%EB%A0%AC%EC%9D%B4%EB%9D%BC%EA%B3%A0%20%ED%95%9C%EB%8B%A4.

[알고리즘] 안정 정렬 (Stable Sort)

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

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