selection sort(선택 정렬)

>>>>>>> 소스코드.git

선택 정렬이란?

제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, 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에서 시작하여 배열에 있는 가장 작은 요소의 인덱스를 찾는다. 반복문을 돌 때마다 배열의 두 요소에 접근하고 한 번의 비교 연산을 한다. 이들은 모두 상수 시간 연산이므로 어느 것을 세든지 중요하지 않다. 간단하게 비교 횟수를 세어본다.

1. start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 된다.
2. start 인자가 1이면 비교 횟수는 n-1이 된다.
3. 일반적으로 비교 횟수는 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²에 비례하게 된다.