선택정렬 (selection sort) 알아보기

이번 포스팅에서는 선택정렬 (selection sort)에 관해 알아보겠습니다. 지난 버블정렬, 삽입정렬에 이어 흔히 O(n^2) 시간복잡도를 갖는 정렬 중 하나인 선택정렬은 앞서 보았던 정렬 알고리즘과 유사하게 간단한 편입니다. 이름에서 드러나듯이 선택정렬은 배열 인덱스에 들어갈 수를 선택하는 과정을 거쳐 수열을 정렬합니다.

 

교실에 10명의 학생들이 있다고 가정해봅시다. 운동장에 의자가 10개 앞뒤로 놓여있고 키 순서로 차례대로 앉히고자 합니다. 맨 앞에 있는 의자에 앉을 학생을 찾아야 합니다. 10명의 학생들이 키 순서대로 교실에 있지는 않아서 일일이 확인하는 작업을 거쳐야 합니다. 밖으로 나가는 문 앞에 서서 키가 제일 작은 학생을 찾고, 그 학생을 운동장으로 보내 맨 앞자리에 앉힙니다. 이어서 두번째로 키가 작은 학생을 찾아 운동장에 보냅니다. 이런 식으로 10번을 반복하면 운동장에는 키 순서대로 학생들이 앉아 있을 겁니다.

 

선택정렬도 이와 비슷한 과정을 거칩니다. 먼저 배열의 첫번째 인덱스에 위치할 숫자를 찾습니다. 만약 수열을 오름차순으로 정렬한다고 하면 제일 작은 숫자를 찾아야 합니다. 만약 내림차순 정렬이라면 최댓값을 찾아야 합니다. 오름차순 정렬을 목표로 한다고 했을 때, 제일 작은 숫자를 찾기 위해서는 수열을 전체 순회하면서 최솟값을 찾으면 됩니다. 값을 찾으면 해당 값을 배열의 첫번째 인덱스에 넣습니다. 두번째 인덱스에 위치할 값을 찾으려면 첫번째 인덱스에 넣은 값을 제외한 나머지 값끼리 비교하여 제일 작은 숫자를 찾으면 됩니다. 이런 식으로 수열의 크기만큼 반복하면 수열이 정렬됩니다.

 

다만 메모리를 아끼기 위해서 선택정렬에서는 정렬할 배열의 인덱스에 위치한 값과 최솟값을 swap하는 방식으로 처리합니다. 그렇지 않으면 기존 수열 크기만큼 정렬된 배열이 선언되어 있어야 하는데 이럴 경우 메모리가 낭비됩니다. 조금 더 구체적으로 예시를 들어보겠습니다.

 

배열: [4, 2, 1, 5, 3]

 

위 배열을 선택정렬을 이용해 오름차순 정렬하겠습니다. 첫 순회이기 떄문에 첫번째 인덱스부터 끝까지 값을 따져가며 제일 작은 숫자를 찾습니다. 여기서는 1이 최솟값이네요. 기존에 첫번째 인덱스에 위치한 [4]를 [1]과 swap 하게 됩니다.

 

결과: [1, 2, 4, 5, 3]

 

두번째 순회에서는 이미 정렬한 [1]을 제외하고 나머지 4개의 숫자에 대해서 최솟값을 찾으면 됩니다. 이 경우 [2]가 제일 작은 값이고 이미 두번째 인덱스에 잘 위치하고 있어서 변화가 일어나진 않습니다. 이와 같이 하나씩 숫자를 정렬시키면서 수열의 크기만큼 반복하여 순회를 돌면 모든 값이 정렬되어 배치됩니다.

 

최종 결과: [1, 2, 3, 4, 5]

 

선택정렬은 직관적이고 간단합니다. 그러나 예시에서 보셨듯이 정렬하기 위해서는 O(n^2)의 시간복잡도를 갖습니다. 그리고 눈치채셨는지 모르겠지만 이미 정렬되어 있어도 선택정렬에서는 무조건 순회를 돌아야 합니다. 따라서 최선의 경우(이미 정렬되어 있는 경우)에서도 시간복잡도는 O(n^2) 입니다. 따라서 선택정렬은 보통 크기가 작은 배열에 대해 빠르게 정렬을 해보고 싶을 때 사용하는 경우가 많습니다.