선택 정렬(Selection Sort)

• 앞에서부터 범위를 줄여가며(i:0 ~ len-1, j:i+1 ~ len) 최소값과 자리를 바꿔가는 정렬 알고리즘
• 제자리 정렬(충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘)

설명

1. 주어진 리스트 중 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

• 시간복잡도 : $O(n^2)$, 공간복잡도 : $O(1)$

예시

[6, 1, 9, 2, 4, 7, 3]을 오름차순으로 sorting하려고 한다.

i = 0, 인덱스 1부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 0, minIdx = 1, 인덱스 0와 1를 swapping한다.
→ arr : [1, 6, 9, 2, 4, 7, 3]


i = 1, 인덱스 2부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 1, minIdx = 3, 인덱스 1와 3를 swapping한다.
→ arr : [1, 2, 9, 6, 4, 7, 3]


i = 2, 인덱스 3부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 2, minIdx = 6, 인덱스 2와 6를 swapping한다.
→ arr : [1, 2, 3, 6, 4, 7, 9]


i = 3, 인덱스 4부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 3, minIdx = 4, 인덱스 3와 4를 swapping한다.
→ arr : [1, 2, 3, 4, 6, 7, 9]


i = 4, 인덱스 5부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 4, minIdx = 4, 인덱스 4와 4를 swapping한다.
→ arr : [1, 2, 3, 4, 6, 7, 9]


i = 5, 인덱스 6부터 arr.length - 1까지의 범위에서 최솟값을 찾는다.
i = 5, minIdx = 5, 인덱스 5와 5를 swapping한다.
→ arr : [1, 2, 3, 4, 6, 7, 9]

구현

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {6, 1, 9, 2, 4, 7, 3};
        for(int i = 0; i < arr.length - 1; i++){
            int minIdx = i;
            int j;
            for(j = i+1; j < arr.length; j++){
                if(arr[j] < arr[minIdx]){
                    minIdx = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

출처

---

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC