정렬 알고리즘2 - 선택정렬(Selection Sort)

선택정렬 (Selection Sort)

출처- 위키백과

 

작동방식

• 정렬해야 하는 값에서 임시최솟값[최댓값]을 정한다(보통 첫번째 값을 할당함)
• 반복문을 돌면서 정렬되지 않은 값과 비교하면서 진짜 최솟값[최댓값]을 찾는다
• 진짜최솟값의 위치가 파악되면 임시최솟값의 위치와 맞바꾼다
• (반복) 정렬한 값을 제외하고 다시 최솟값[최댓값]의 위치를 찾는다

 

 

특징

• 정렬해야 하는 값 중에서 다음 최솟값[최댓값]을 찾아 정렬하는 방식
• 좌측[우측]부터 순서대로 정렬된다
• 버블정렬과 마찬가지로 n제곱만큼 수행된다
• 버블정렬에 비해 요소간 자리이동하는 작업이 적기 때문에 실제효율은 버블정렬보다 좋다

 

 

예시

[ 1, 14, 9, 6, 2, 19, 4, 7 ] 와 같은 숫자집합이 있을때 아래와 같은 순서로 정렬된다.

 

1 2 9 6 14 19 4 7 
1 2 4 6 14 19 9 7 
1 2 4 6 7 19 9 14 
1 2 4 6 7 9 19 14 
1 2 4 6 7 9 14 19 

 

 

구현코드 - Java

int[] intArr = {1, 14, 9, 6, 2, 19, 4, 7};
int i, j, min;
//a- 바깥쪽 반복문
for(i=0; i<intArr.length-1; i++){
	min = i;
    //b- 안쪽 반복문
	for(j=i+1; j<intArr.length; j++){
    	//c- 최솟값[최댓값] 찾기
		if(intArr[j] < intArr[min]){
			min = j;
		}
	}
    
    //d- 요소간 이동작업
	int temp = intArr[min];
	intArr[min] = intArr[i];
	intArr[i] = temp;
}

• a- 바깥쪽 반복문
• b- 안쪽 반복문
• c- 최솟값 혹은 최댓값을 찾는다.
• d- 요소간 자리를 맞바꾸어 정렬이 이루어진다. 버블정렬에 비해 불필요한 이동작업이 적다