선택 정렬 알고리즘이란?
선택 정렬 알고리즘은 주어진 배열의 특정 구간에서 최대값을 찾아 해당 구간의 마지막 위치의 값과 위치 변경을 반복해 정렬을 수행하는 알고리즘이다.
이를 간단히 표현하면 다음과 같다.
1. 포인터를 배열의 마지막 위치에 위치시킨다.
2. 배열 맨 앞의 값부터 포인터의 위치까지 값 중 최대값을 찾는다.
3. 찾은 최대값을 포인터의 위치의 값과 교환한 후, 포인터를 하나 앞으로 옮긴다.
4. 1~3의 과정을 포인터가 배열의 맨 앞 원소로 이동할 때까지 반복한다.
위의 방법에서는 최대값을 찾아 마지막 위치의 값과 교환하는 방식을 사용했지만, 최소값을 찾아 맨 앞의 위치의 원소와 교환하는 방법도 선택 정렬 알고리즘이라 부른다. 이번 글에서는 최대값 방식으로 정렬을 하도록 하겠다.
선택 정렬 알고리즘 그림으로 이해하기
1. [5, 4, 6, 2, 1] 로 이루어진 배열이 있다고 하자. 포인터를 맨 마지막 원소에 위치시킨다.
2. 맨 앞에서부터 pointer 사이의 구간 중 가장 큰 값을 찾는다. 6이 가장 큰 값이다.
3. 6을 현재 포인터의 값인 1과 교환한 후, 포인터를 하나 앞으로 옮긴다.
4. 맨 앞에서부터 pointer 사이의 구간 중 가장 큰 값을 찾는다. 5가 가장 큰 값이다.
5. 5를 현재 포인터의 값인 2와 위치를 바꾼 후, 포인터를 하나 앞으로 옮긴다.
6. 맨 앞에서부터 pointer 사이의 구간에서 가장 큰 값을 찾는다. 4가 가장 큰 값이다.
7. 4를 현재 포인터의 값인 1과 위치를 바꾼 후 포인터를 하나 앞으로 옮긴다.
8. 2와 1 중 큰 값은 2이다.
9. 2를 현재 포인터의 값인 1과 위치를 바꾼 후 포인터를 하나 앞으로 옮긴다.
10. 포인터가 맨 앞에 도달했으므로 정렬을 끝내고 배열을 반환한다.
선택 정렬 알고리즘 Kotlin으로 구현하기
선택 정렬 알고리즘을 Kotlin으로 구현하면 아래와 같이 될 수 있다.
1. pointerLastIndex를 배열의 맨 끝으로 둔 후 맨 앞까지 반복하는 for 문을 만든다.
2. for 문 내부에서 처음부터 pointerLastIndex까지의 원소 중 최대값을 찾고, 해당 최대값을 pointerLastIndex 위치의 원소와 교환하는 과정을 반복한다.
fun selectionSort(array: IntArray) {
for (pointerLastIndex in array.size - 1 downTo 0) {
// Find max value
var maxValue = array[0]
var maxIndex = 0
for (pointer in 1..pointerLastIndex) {
if (array[pointer] > maxValue){
maxIndex = pointer
maxValue = array[pointer]
}
}
// Swap pointer last position with max value
val tmp = array[pointerLastIndex]
array[pointerLastIndex] = maxValue
array[maxIndex] = tmp
}
}
이를 직접 실행해보면 정상적으로 정렬이 수행되는 것을 확인할 수 있다.
