Selection Sort(선택 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Selection Sort(선택 정렬)

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

1. 주어진 리스트 중에 최솟값 or 최대값을 찾는다.

2. 그 값을 맨 앞 or 맨 뒤에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, 

n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

                     

출처 : 위키 백과

예제

[4, 54, 2, 8, 63, 7, 55, 56]    -> initial array

[4, 54, 2, 8, 56, 7, 55, 63]     -> after 1st swap

[4, 54, 2, 8, 55, 7, 56, 63]     -> after 2st swap

[4, 54, 2, 8, 7, 55, 56, 63]     -> after 3rd swap

[4, 7, 2, 8, 54, 55, 56, 63]     -> after 4th swap

[4, 2, 7, 8, 54, 55, 56, 63]     -> after 5th swap

[2, 4, 7, 8, 54, 55, 56, 63]     -> after 6th swap

의사 코드

Selection Sort(A[], n) {    // 배열 A[1...n]을 정렬한다.
for last <- n down to 2 {    ------------------------ ①
A[1...last] 중 가장 큰 수 A[K]를 찾는다;    ----- ②
A[k] <-> A[last];    ---------------------------- ③
}
}

실행 시간 : 

① 의 for 루프는 n-1 번 반복

② 에서 가장 큰 수를 찾기 위한 비교 횟수 : n-1, n-2, ... , 2, 1

③ 의 교환은 상수시간 작업

시간 복잡도

최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교횟수를 C라고 했을때, 이를 수식으로 나타내면 다음과 같다.

수식에서 N은 테이블(또는 리스트)의 자료 수를 나타내며 는 평균, 는 최대, 는 최소를 나타낸다.

T(n) = (n-1) + (n-2) + ... + 2 + 1 =  Θ(n²)

소스 코드(Java)

	package Sort;
	//선택 정렬 알고리즘 구현
	public class select {
	int [] selectionsort(int [] data) {
	int min; //최소값을 가진 데이터의 인덱스 저장
	int temp = 0;
	for(int i=0; i<data.length-1; i++) { // data.length-1 : 마지막 요소는 자연스럽게 정렬됨
	min = i;
	for(int j=i+1; j<data.length; j++) {
	if(data[min] > data[j]) {
	min = j;
	}
	}
	temp = data[min];
	data[min] = data[i];
	data[i] = temp;
	}
	return data;
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int [] data = {4, 54, 2, 8, 63, 7, 55, 56};
	select test = new select();
	// 선택 정렬 전 출력
	System.out.println("# 선택 정렬 전");
	for(int i=0; i<data.length; i++) {
	System.out.print(data[i]+" ");
	}
	System.out.println();
	//삽입 정렬 후 출력
	System.out.println("# 선택 정렬 후");
	test.selectionsort(data);
	for(int i=0; i<data.length; i++) {
	System.out.print(data[i]+" ");
	}
	}
	}

view raw Selection Sort.java hosted with ❤ by GitHub