선택 정렬(Selection Sort)에 대해 알아보자

선택 정렬은 버블 정렬과 비슷하지만 약간 다른 정렬 방법이다. 버블 정렬과 마찬가지로 O(n^2)의 시간복잡도를 가지며 실제로 사용하는 일은 별로 없다. 하지만 이전 포스팅에서도 말했듯이 원리를 이해해야만 해결할 수 있는 문제가 나올 수 있으니 반드시 알아두어야 한다.

 

선택 정렬

선택 정렬은 정렬되지 않은 곳을 전부 조사하여 가장 작은 값을 찾은 후, 정렬되지 않은 곳의 맨 앞과 swap 하는 방법이다. 그림을 보자.

형광펜이 칠해진 곳은 정렬이 끝난 곳이다.

버블 정렬과 같은 예제이다. 다만 이번에는 먼저 배열 전체를 검사한 후, 가장 작은 값을 체크하였다. 그리고 정렬되지 않은 곳의 맨 앞과 swap 해주면 맨 앞에서부터 정렬이 이루어지는 모양이 된다. 첫 번째에서 1이 가장 작은 값이므로 원래 1의 index인 2와 맨 앞의 index인 0을 swap 해 주었다. 따라서 원래 index 0에 있었던 2가 index 2로 바뀐 것을 볼 수 있다. 이것을 계속 반복하면 된다. 코드로 구현하려면 반복문을 이용하고, 가장 작은 값의 index를 저장하는 변수를 만들어(가장 작은 숫자 자체를 저장하게 되면 전부 비교가 끝난 후 그 숫자의 index를 다시 찾아야 하므로 비효율적이다!) 처음과 swap 해주면 된다. 물론 이때는 실제 숫자를 swap 해야 한다. 이때 index 0부터 비교를 시작하게 하고 반복문 변수를 ++ 해주면서 반복문을 돌리면 더 간편하게 swap 할 위치를 알 수 있다. 반복문 변수를 index로 쓰면 되니까 말이다.

 

많이 사용하지 않는 정렬 방법이지만 원리만 잘 이해하고 넘어가면 좋을 것 같다. 백준 문제중에 정렬임에도 시간제한이 넉넉한 문제가 있으므로 직접 코딩을 해보고 실행해 보자. 백준 2750번이 수의 범위도 작고 시간도 넉넉해 테스트해 보기는 좋다. 다음 포스팅에서는 삽입 정렬에 대해서 알아보도록 하자.

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기