[알고리즘 개념] 선택정렬

개념

https://rcsole.gitbooks.io/apprenticeship/year-one/data-structures-and-algorithms/02-sorting-algorithms.html

 "최솟값을 선택"하는 알고리즘이다. 버블정렬은 좌우-좌우를 순차적으로 비교하면서 각 턴마다 최대값을 맨 오른쪽으로 보내는 것이라면, 선택알고리즘은 각 턴마다 최소값을 찾은 후 맨 왼쪽으로 보내는 알고리즘이다. 

 

구현

 7 5 6 9 2 를 예로 들어보자. 

 첫번째 순회에서는 인덱스 0에 넣을 최솟값을 찾는다. 7 5 6 9 2 중 최솟값은 2 이므로 인덱스 0에 있는 7과 자리를 바꾼다. 첫번째 순회의 결과는 2 5 6 9 7이 된다. 첫번째 순회에서 인덱스 0은 최소값으로 정렬되었다. 

 

 두번째 순회에서는 인덱스 1에 넣을 최솟값을 찾는다. (2) 5 6 9 7에서 최솟값은 5 이므로 인덱스 1에 5를 넣는다. 두번째 순회의 결과는 2 5 6 9 7 이되고 인덱스 0,1은 크기순으로 정렬되어 있다. 

 

 이런식으로 인덱스가 배열길이 -1 일때까지 반복한다. 이를 표로 나타내면 아래와 같다. 

 

7 5 6 9 2
반복	정렬할 인덱스	최솟값	결과
1	0	2	2 5 6 9 7
2	1	5	2 5 6 9 7
3	2	6	2 5 6 9 7
4	3	7	2 5 6 7 9

코드 

public static void selectionSort(int[] list) {
		for(int stand = 0;stand<list.length;stand++) {
			int minIndex = stand;
			for(int index = stand+1;index<list.length;index++) {
				if(list[index]<list[minIndex]) {
					minIndex = index;
				}
			}
			if(minIndex!=stand) {
				int temp = list[minIndex];
				list[minIndex]=list[stand];
				list[stand]=temp;
			
			}
		}
	}

 

 

시간복잡도

 총 n-1번 순회하면서 각 n-1번 비교를 한다. 따라서 1+2+3+4+ ...+(n-1) = n(n-1)/2회 단계가 필하므로 시간복잡도는 O(n^2) 이다.