선택 정렬(Selection sort)

목차

1. 선택 정렬이란?
2. 사용 예시
3. 장점과 단점

1. 선택 정렬이란?

정렬 알고리즘의 일종입니다. 다음과 같은 과정을 거집니다.
1) 주어진 리스트의 최우선순위값을 찾습니다.
2) 그 값을 맨 처음에 위치한 원소와 교체합니다.
3) 처음의 원소를 제외하고 나머지 리스트에 1~2번을 반복합니다. 모든 리스트가 제외될때까지 반복합니다.
이를 코드로 나타내면 다음과 같습니다. (내림차순 정렬시)

int n = v.length();
for (int i = 0; i < n; i++){
	
    int max = i;
    for (int j = i; j < n; j++){
    	
        if (v[max] < v[j]) max = j;
    }
    swap(v[max], v[i]);
}

2. 사용 예시

위 예시를 내림차순으로 정렬하겠습니다.

1. 가장 큰 값을 찾습니다.
   
   화살표 수서대로 숫자를 살펴보며 살펴본 숫자들 중 가장 큰 값을 주황색으로 표시했습니다.

2. 찾은 값을 맨 앞의 원소와 교체합니다.
   위 그림대로 99가 가장 큰 값이며 j = 3이 기 때문에 i(0)과 j(3)의 위치를 바꿉니다.
   

3. 교체된 원소를 제외한 리스트로 위 과정을 반복합니다.
   
   
   
   

바로 위 그림이 내림차순으로 정렬된 배열입니다.

3. 장점과 단점

앞서 설명했던 버블 정렬, 삽입 정렬과 유사한 모습을 보이고 있습니다.

3-1. 장점

구현 난이도가 낮습니다.

3-2. 단점

다른 알고리즘에 비해 시간 복잡도가 큽니다.
다만 앞서 설명드렸던 버블 정렬과 삽입정렬과 비교할 경우 전부 O(n ^ 2)로 이론적으로는 비슷하지만 개념 상 선택 정렬이 가장 빠른 것을 알 수 있습니다.