선택 정렬

개요

최소값의 인덱스값을 찾고 해당 위치와 타겟 위치를 Swap하며 정렬하는 방법.

---

복잡도

	최악	평균	최소
Big O 표기법	O(n^2)	O(n^2)	O(n^2)

---

알고리즘 절차

1. 타겟 인덱스를 0으로 설정함.
2. 타겟 인덱스부터 끝까지 선형 탐색하며 최소값의 인덱스값을 기억함.
3. 타겟 인덱스와 최소값의 인덱스를 활용해서 Swap함.
4. 타겟 인덱스값을 1로 설정하고 1~3 과정을 다시 반복함. 
5. 모든 요소가 정렬되면 종료.

---

자바 코드

class Selection {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        selectionSort(testCase1);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    public static void selectionSort(int[] arr) {
        for(int i=0; i<arr.length-1; i++) {
            int minIdx = i;
            for(int j=i; j<arr.length; j++) {
                if(arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }
            swap(arr, i, minIdx);
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}