선택 정렬 알고리즘이란?

오늘은 삽입 정렬, 버블 정렬과 같은 기본적인 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보려고 한다

참고로 선택 정렬은 이름에서 알 수 있듯이 가장 작은 원소를 선택하여 앞쪽부터 채워 나가는 방식의 정렬 알고리즘이다

선택 정렬이란?

선택 정렬은 주어진 리스트 내에서 최소값(또는 최대값)을 찾아서 맨 앞의 값과 교환하는 방식으로 정렬하는 알고리즘으로

한 번의 교환으로 원소가 최종적으로 위치하는 것을 특징을 가졌다

선택 정렬의 작동 방식

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 오름차순으로 선택 정렬 알고리즘을 사용한다고 했을 때

정렬해야 하는 리스트: [9, 7, 5, 11, 12, 2]

첫 번째 진행:

[9, 7, 5, 11, 12, 2] -> [2, 7, 5, 11, 12, 9]

전체 리스트 중에서 가장 작은 원소 2를 선택하고 맨 앞의 9와 교환한다

두 번째 진행:

[2, 7, 5, 11, 12, 9] -> [2, 5, 7, 11, 12, 9]

남은 리스트 [7, 5, 11, 12, 9]에서 가장 작은 원소 5를 선택하고 7과 교환한다

이와 같은 과정을 반복하면 리스트에 전체 원소가 오름차순으로 정렬된다

선택 정렬의 장단점

마지막으로 선택 정렬 알고리즘에 장단점을 알아보자

장점:

1. 정렬 과정 중에 데이터의 이동 횟수가 미리 결정되므로 다른 기본 정렬 알고리즘에 비해 상대적으로 빠르다
2. 추가 메모리를 사용하지 않는다 (인플레이스 정렬)

단점:

1. 최악의 경우, 평균의 경우, 최선의 경우 모두 시간 복잡도가 O(n^2)로 항상 일정하다
2. 비교 횟수가 많기 때문에 데이터의 양이 많을 경우 다른 알고리즘에 비해 비효율적이다