선택정렬(Selection Sort)

5년전 대학생 때 자료구족 과목을 수강하면서 정렬기법에 대하여 공부한적이 있다. 그때 공부했던 내용을 다시 되새기며 이 블로그에 기록하고자 한다.

오늘 정리할 내요은 선택정렬이다. 선택정렬(Selection Sort)은 기준이되는 원소를 정한 후 전체 원소중 가장 작은 원소를 찾아 자리를 교환하는 방식이다.

다음은 선택 정렬을 수행하는 과정을 나타낸다.

step 1.
첫 번째 자리를 기준 위치로 정한다음, 전체 원소 값중에서 가장 작은 값을 선택하여 기준 위치에 있는 원소와 자리를 교체한다.

step 1 [ 기준(50), 20, 30, 작은원소(5), 18, 9, 35, 26 ]
step 1 [ 기준(5), 20, 30, 50, 18, 9, 35, 26 ]

step 2.
두 번째 자리를 기준 위치로 정한다음, 나머지 원소 값중에서 가장 작은 원소 값을 선택하여 기준 위치에 있는 원소와 자리를 교체한다.

step 2 [ 5, 기준(20), 30, 50, 18, 작은원소(9), 35, 26 ]
step 2 [ 5, 기준(9), 30, 50, 18, 20, 35, 26 ]

step 3.
이 방식을 마지막 원소(n-1) 까지 진행하면된다.

다음은 선택정렬을 구현한 코드이다.

public void selectionSort(int[] list, int length) {

	int temp;
	int min;
	for (int i = 0; i < length; i++) {
		min = i;
		for (int j = i + 1; j < length; j++) {
			if (list[j] < list[min]) {
				min = j;
			}
		}
		temp = list[i];
        list[i] = list[min];
        list[min] = temp;
	}
}
    
public void print(int[] list) {

	for (int element : list) {
		System.out.printf("%d ", element);
	}
}


@Test
public void should_Calculation_When_Input() {

	int[] list = {50, 20, 30, 5, 18, 9, 35, 26};
	int length = list.length;
	selectionSort(list, length);
	print(list);

}

이러한 방법으로 각 단계에서는 i 번째 원소를 기준으로 n-1 개의 원소를 비교하게 되는데 전체 비교 횟수는 다음 식으로 나타낼 수 있다.

시간복잡도 : O(N^2)