SelectionSort

public class SelectionSort {

	/**
	 * Swaps the elements at indexes i and j.
	 */
	public static void swapElements(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * Finds the index of the lowest value
	 * between indices low and high (inclusive).
	 */
	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;
	}

	/**
	 * Sorts the cards (in place) using selection sort.
	 */
	public static void selectionSort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			int j = indexLowest(array, i);
			swapElements(array, i, j);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = {2, 5, 6, 1, 3};
		selectionSort(array);
		System.out.println(Arrays.toString(array));
	}

}

 

첫 번째 메서드 swapElements는 배열에 있는 두 요소의 값을 바꿉니다. 요소를 읽고 쓰는 것은 상수 시간 연산입니다.

 

요소의 크기와 첫 번째 위치를 알고 있다면 한 번의 곱셈과 덧셈으로 어떤 요소의 위치라도 알 수 있기 때문입니다. 따라서 이들은 시간 복잡도 O(1) 입니다.

 

swapElements 메서드에 있는 모든 연산이 상수 시간이므로 전체 메서드는 상수 시간이 됩니다,

 

• 두번째 메서드 indexLowest는 주어진 위치인 start에서 시작하여 배열에 있는 가장 작은 요소의 인덱스를 찾습니다
• 반복문이 돌 때마다 배열의 두 요소에 접근하고 한번의 비교 연산을 합니다. 이들은 모두 상수 시간 연산이므로 어느 것을 세든지 중요하지 않습니다. 간단하게 비교 횟수를 세겠습니다.

1.  start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 됩니다.
2.  start 인자가 1이면 비교횟수는 n - 1이 됩니다.
3. 일반적으로 비교 횟수는 n - start가 되어 indexLowest 메서드는 선형이 됩니다.

 

세번째 메서드 selectionSort는 배열을 정렬합니다. 0에서 n - 1 까지 반복하므로 n번 반복 실행됩니다. 매번 indexLowest 메서드를 호출한 후 상수 시간 연산인 swapElements 메서드를 실행합니다.

 

결국 for 문 안에서 indexLowest가 실행되면 2중 for문이므로 연산횟수는 n**2이 되게 되고 시간 복잡도는 

O(N**2) 이 됩니다.