나동빈 실전 알고리즘 2강 - 선택 정렬(Selection Sort)

2. 정렬의 개요와 선택 정렬(Selection Sort)

일반적으로 알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 '정렬(Sort)' 문제입니다. 왜냐하면 정렬은 알고리즘의 효율성 차이를 확실히 보여줄 수 있기때문입니다.

 

---

<문제> 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요
1 10 5 8 7 6 4 3 2 9

---

위에서 주어진 숫자배열을 나열할 때 선택 정렬을 이용하기 위해서는 '가장 작은 것을 선택해서 앞으로 보낸다'라는 알고리즘을 이용해서 풀어볼 수 있다.

 

그러면 컴퓨터에게 이렇게 이해를 시키는 것이다.

 

1. 임의의 가장 작은 수를 지정한다.(최대한 큰 숫자로, 이것을 min이라고 정한다.)

2. 첫번째부터 min과 비교했을때 작은 수인지 확인한다.(가장 작은 숫자를 최대한 큰 숫자로 지정했기때문에 첫번째가 무조건 작은 숫자가 된다.)

3. 그리고 첫번째 숫자와 그 뒤의 숫자들을 비교하여 작은 수가 있으면 선택해서 자리를 바꿔준다.

4. 두번째부터도 위에서 이야기한 과정을 수행한다.

 

그것을 코드로 작성해보자.

package excercise;

public class algorithm {
	public static void main(String[] args) {
		int min; // 가장 작은 숫자를 일시적으로 담는다.
		int temp = 0; // 배열에서 두 숫자의 위치를 바꾸기 위해 임시적으로 사용하는 변수이다.
		int index = 0; // 최솟값이 담긴 위치의 인덱스이다.
		
		// 다음 배열을 작은 수부터 차례대로 나열하여라.
		int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		
		for(int i = 0; i < arr.length; i++) { // 1번째부터 차례대로 확인한다.
			min = 9999; // 최솟값을 아주 큰 수로 정한다.
            
            // j번째부터 끝까지 가장 작은 숫자를 찾는다.
			for(int j = i; j < arr.length; j++) {
				if(min > arr[j]) { // i번째 다음으로 있는 숫자들 중에 최솟값보다 작다면
					min = arr[j]; // 최솟값을 j번째 숫자로 정하고
					index = j; // j번째의 인덱스값을 저장한다.
				}
			}
			
			// i번째와 j번째의 위치를 바꾼다.
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
		
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}	
}

 

 

 

그러면 작은 수부터 차례대로 정렬이 된 것을 볼 수 있다.

 

위와 같은 선택정렬을 할 때는 정렬해야할 숫자가 10개라면

첫번째 숫자는 첫번째부터 마지막까지 확인해아하므로 10번을 확인해야하고,

두번째 숫자는 두번째부터 마지막까지 확인해야하므로 9번을 확인해야하고,

세번째 숫자는 세번째부터 마지막까지 확인해야하므로 8번을 확인해야하고,

.

.

.

마지막 숫자는 한 번 확인한다.

 

이러한 과정을 몇 번 거쳐가는지 횟수를 세면

10 + 9 + 8 + ... + 1 = 55번이다.

 

 

그렇다면 n개의 숫자가 있으면 어떻게 될까?

그렇게 된다면 1부터 n까지 차례대로 더해야하므로

n(n+1)/2 번을 수행해야한다.

 

그러면 결국 대략 n^2번의 활동을 해야하므로 앞으로 배울 정렬과 비교해봤을때 효율적인지 따져봐야한다.

 

blog.naver.com/ndb796/221226800661

2. 정렬의 개요와 선택 정렬(Selection Sort)