[알고리즘] 선택정렬(Selection sort)

선택정렬(Selection Sort)

- 제자리 정렬(In-placed sorting) 알고리즘

- 주어진 배열 중 최소 값을 찾아 맨 앞의 값과 위치를 바꿔가며 정렬

- 1 Cycle을 수행하고 나면 가장 작은 값의 데이터가 맨 앞에 오게 됨

- 구현이 간단

- 시간 복잡도 : O(n^2)

 

선택정렬(Selection Sort) 과정

정렬해야할 n개의 데이터가 주어졌을 때

 

최초 모든 데이터에 대해 최소값을 찾아 맨 앞의 인덱스에 위치 시킨다.

한 사이클이 돌아갔을 때, 가장 작은 값이 맨 앞의 인덱스에 위치된 것을 알 수 있다.

 

 

다시 두번째 인덱스부터 시작해 가장 작은 값을 찾아 두번째 인덱스에 위치시킨다.

이러한 과정을 n번째 인덱스까지 반복하면 정렬할 수 있다.

 

소스코드

package algorithm;

public class selectionSort {
	public static void main(String args[]) {
		int[] a = {7, 8, 1, 9, 4, 6};
		int min;
		int idx;
		
		for(int i = 0; i < a.length; i++) {
			min = 99999;
			idx = 0;
			for(int j = i; j < a.length; j++) {
				if(min > a[j]) {
					min = a[j];
					idx = j;
				}
			}
			int tmp = a[idx];
			a[idx] = a[i];
			a[i] = tmp;
		}
		
		for(int i = 0; i < a.length; i++) {
			System.out.printf("%d ", a[i]);
		}
	}
}