정렬 (Sorting) (1) - 선택 정렬 (Selection Sort)

먼저 코딩 테스트의 중요 알고리즘 중 하나인 정렬에 대해서 알아보자. 정렬이란 말 그대로 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 주어진 데이터를 정렬하고 사용하는 경우가 많기 때문에 프로그램을 작성할 때 자주 사용되는 알고리즘 중 하나이다. 또한 정렬 알고리즘이 중요한 이유 중 하나는 이진 탐색의 전처리 과정이기 때문이다.

선택 정렬 (Selection Sort) 란 데이터가 무작위로 나열되어 있을 때, 이 중에서 가장 작은(혹은 가장 큰) 데이터를 가장 앞의 데이터와 바꾸고, 두 번째로 작은 데이터를 두 번째에 위치한 데이터와 계속 바꾸는 방법으로 데이터를 정렬하는 알고리즘이다. 선택 정렬은 가장 원시적인 방법으로 매번 '가장 작은 데이터를 선택한다'는 의미에서 이름이 붙여졌다. 무작위로 나열된 숫자들을 선택 정렬(오름차순) 하는 과정을 보자.

7 5 9 0 3 1 6 2 4 8

처음으로 가장 작은 데이터를 선택하면 0이 선택될 것이다. 선택된 0을 가장 처음의 데이터인 7과 위치를 바꾼다.

0 5 9 7 3 1 6 2 4 8

0과 7의 위치를 바꾼 모습이다. 다음으로는 두 번째 작은 데이터를 선택한다. 두 번째 작은 데이터인 1이 선택되고 이를 두 번째 자리에 위치한 5와 위치를 바꾸면 아래와 같아진다.

0 1 9 7 3 5 6 2 4 8

이러한 일련의 과정들을 거치는 것을 선택 정렬이라고 하며 모든 정렬이 끝나면 아래와 같은 오름차순의 정렬된 데이터를 얻을 것이다.

0 1 2 3 4 5 6 7 8 9

이와 같이 선택 정렬은 N개의 데이터가 주어졌을 때, 가장 작은 데이터를 앞으로 보내는 과정을 N-1 번 반복하면 완료할 수 있다. 

---

파이썬으로 구현한 선택 정렬 소스코드는 아래와 같다.

---

다음으로 선택 정렬의 시간 복잡도를 계산해보자. 선택 정렬은 N-1 번 만큼 가장 작은 수를 찾아서 앞으로 보내는 과정을 거쳐야 한다. 또한 이 과정에서 매번 가장 작은 수를 찾는 비교 연산이 필요하다. 따라서 연산횟수는 근사치로 N x (N+1) / 2 로 구해진다. 이를 빅오 표기법을 사용하여 나타내면 O(N^2) 이 된다.

따라서 선택 정렬은 데이터의 개수가 많아지면 수행 시간이 급격하게 늘어나는 것을 알 수 있다. 뒤에 다룰 다른 정렬 알고리즘과 비교하면 시간 복잡도 측면에서 매우 비효율적임을 알 수 있는 것이다. 그러나 이 선택 정렬은 특정 리스트에서 가장 작은 데이터를 찾는 알고리즘을 포함하고 있으므로 이 소스코드에 익숙해질 필요가 있다.