Selection sort

1. Problem

- n개의 정수가 담긴 배열을 오름차순으로 정렬해보자.

- 선택 정렬은 가장 작은 요소를 찾아 자리를 바꾸면서 정렬한다.

- 맨 끝까지의 비교가 1번씩 일어날 때마다 가장 작은 요소가 앞으로 간다.

 

2. Input

1) int[] arr

 

3. Output

1) 오름차순으로 정렬된 배열

 

4. Example

// 예시: (2 3 6 1 5 4)
// 가장 작은 수: 1 -> 1과 2를 바꾼다. -> 1 (3 6 2 5 4)
// 가장 작은 수: 2 -> 2와 3을 바꾼다. -> 1 2 (3 6 5 4)
// 가장 작은 수: 3 -> 바꾸지 않는다.  -> 1 2 3 (6 5 4)
// 가장 작은 수: 4 -> 4와 6을 바꾼다. -> 1 2 3 4 (5 6)
// 가장 작은 수: 5 -> 바꾸지 않는다.  -> 1 2 3 4 5 6

 

5. Code

int[] arr = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8};  // 10개의 요소
int min, minIndex = 0, temp = 0;
for(int i=0 ; i<arr.length ; i++) { // 앞에서부터 가장 작은 값을 위치시키려 한다.
    min  = Integer.MAX_VALUE;       // min값은 가장 큰 수로 정의해놓는다.
    for(int j=i ; j<arr.length ; j++) // i번째부터 탐색하면서
        if(arr[j]<min) {            // j번째 요소가 min보다 작다면
            min = arr[j];           // min 값을 j번째 요소로 바꾸고
            minIndex = j;           // 가장 작은 값의 위치를 minIndex에 저장한다.
        }
    temp = arr[i];                  // i번째 값을 임시로 저장한 뒤
    arr[i] = arr[minIndex];         // 가장 작은 값을 i번째로 옮기고
    arr[minIndex] = temp;           // 가장 작은 값이 위치하던 곳에 i번째 값을 옮긴다.
}
// 정렬 확인
for(int i : arr)
    System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 10개의 요소를 정렬할 때 살펴봐야 하는 총 횟수는 10 + 9 + ... + 1 = 55번의 비교 연산을 해야 한다.
- n개의 요소라면 비교 연산의 총 횟수는 n*(n+1)/2번이다.
- 그러므로 시간 복잡도는 O(n^2)를 따른다.