자바 선택정렬(Selection Sort) 알고리즘 정리

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

데이터 하나를 기준으로 다른 데이터와 비교하여

가장 작거나 / 큰 데이터와 자리를 바꾸는 식으로

반복 비교하는 정렬을 수행하게 되는데

데이터의 개수가 N개라면 N-1회 회전(for문)을 하게 된다

 

먼저 반복 정렬이 어느 식으로 움직이는지 알아야 하는데

이게 가장 중요한 부분인 만큼 두 눈 크게 뜨고 잘 보자

1회차	5	3	1	2	4
2회차	1	5	3	2	4
3회차	1	2	5	3	4

5 3 1 2 4 가 들어있는 배열에서

오름차순 정렬을 할 경우에는

 

5는 3보다 크기 때문에 5와 3의 위치를 바꿔서

3 5 1 2 4 가 되고

arr[i]에 3이 들어가게 된다

(비교 대상이 5에서 3이 된다는 말)

 

이후 3은 1보다 크기 때문에 3과 1의 위치를 바꿔서

1 5 3 2 4 가 되고

arr[i]에 1이 들어가게 된다

 

마지막으로 1은 2, 4보다 크지 않기 때문에

1회차는 1 5 3 2 4 로 끝난다

 

2회차는 5부터 시작하게 되는데

5는 3보다 크기 때문에 1 3 5 2 4가 된다

이후 arr[i]는 3이 되고

 

3은 2보다 크기 때문에 1 2 5 3 4 가 된다

이후 arr[i]는 2가 된다

 

마지막으로 2는 4보다 크지 않기 때문에

3회차는 1 2 5 3 4로 끝난다

 

선택 정렬은 이런 식으로 진행되기 때문에

코드가 단순하다고 그냥 외워버릴 것이 아니라

코드가 어떻게 움직이는지 개념을 반드시 익혀야

나중에 실제 사용하는 경우가 와도 

 

복사 붙여넣기가 아닌 이해를 해서 활용이 가능하다

그냥 외워버리면 중요한 순간에 활용을 못한다

 

오름차순과 내림차순은 두번째 for 문에서

'>'면 오름차순 '<'면 내림차순으로 정렬된다

 

그리고 값 변경 시 값을 보관하는

변수가 하나 필요하다는 것만 알아두면 된다

 

마지막으로 예제에 사용한 코드는 다음과 같다

 

	public static void main(String[] args) {
		// 선택정렬 알고리즘(Selection Sort Algorithm)
		// 무작위 데이터를 오름차순/내림차순 정렬
		int[] arr = {5, 3, 1, 2, 4};
		
		for(int i = 0; i<arr.length; i++) {
			for(int j = i + 1; j < arr.length; j++) { // +1을 하는 이유는 자기와 비교할 필요가 없기 때문
				if(arr[i] > arr[j]) { // '>' 일 경우 오름차순 '<' 일 경우 내림차순
					int temp = arr[i]; // 값 변경해야 하기에 임시 저장
					arr[i] = arr[j]; // j를 i로 변경
					arr[j] = temp;  // i를 j로 변경
				}
			}
		}
		
		for(int i = 0; i<arr.length; i++) {
			System.out.print(arr[i] + " "); // 정렬 후 결과 출력
		}
	}