selection sort(선택 정렬)
선택 정렬이란?
제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n²) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
소스 코드(java)
(SelectionSort.java)
import java.util.Arrays;
public class SelectionSort {
/**
* i와 j의 위치에 있는 값을 바꾼다.
*/
public static void swapElements(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* start로부터 시작하는 최솟값의 위치를 찾고(start 포함)
* 배열의 마지막 위치로 간다.
*/
public static int indexLowest(int[] array, int start) {
int lowIndex = start;
for (int i = start; i < array.length; i++) {
if (array[i] < array[lowIndex]) {
lowIndex = i;
}
}
return lowIndex;
}
/**
* 선택 정렬을 사용하여 요소를 정렬한다.
*/
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int j = indexLowest(array, i);
swapElements(array, i, j);
}
}
public static void main(String[] args) {
int[] array = {2, 5, 6, 1, 3};
selectionSort(array);
System.out.println(Arrays.toString(array));
}
}첫 번째 메서드 swapElements는 배열에 있는 두 요소의 값을 바꾼다. 요소를 읽고 쓰는 것은 상수 시간 연산이다. 요소의 크기와 첫 번째 위치를 알고 있다면 한 번의 곱셈과 덧셈으로 어떤 요소의 위치라도 알 수 있기 때문이다. 따라서 이들은 상수 시간 연산이다. swapElements 메서드에 있는 모든 연산이 상수 시간이므로 전체 메서드는 상수 시간이 된다.
두 번째 메서드 indexLowest는 주어진 위치인 start에서 시작하여 배열에 있는 가장 작은 요소의 인덱스를 찾는다. 반복문을 돌 때마다 배열의 두 요소에 접근하고 한 번의 비교 연산을 한다. 이들은 모두 상수 시간 연산이므로 어느 것을 세든지 중요하지 않다. 간단하게 비교 횟수를 세어본다.
- start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 된다.
- start 인자가 1이면 비교 횟수는 n-1이 된다.
- 일반적으로 비교 횟수는 n-start가 되어 indexLowest 메서드는 선형이 된다.
세 번째 메서드 selectionSort는 배열을 정렬한다. 0에서 n-1까지 반복하므로 n번 반복 실행된다. 매번 indexLowest 메서드를 호출한 후 상수 시간 연산인 swqpElements 메서드를 실행한다.
indexLowst 메서드가 처음 호출되면 n번 비교 연산을 한다. 두 번째는 n-1번 비교 연산을 한다. 이렇게 하였을 때 총 비교 횟수는 n + n-1 + n-2 + … + 1 + 0이다.
이 수열의 합은 n(n+1)/2이고 n²에 비례한다. 이것은 selectionSort 메서드가 이차라는 것을 의미한다.
다른 방법으로 같은 결과를 얻으려면 indexLowest 메서드를 중첩된 반복문으로 생각할 수 있다. indexLowest 메서드를 호출할 때마다 연산 횟수는 n에 비례한다. 이를 n번 호출하므로 결과적으로 총 연산 횟수는 n²에 비례하게 된다.