02. 선택 정렬 (Selection Sort)

정의

주어진 데이터 중 최소값을 찾은 후 해당 최소값을 맨 앞과 교체하는 방법의 알고리즘

j 를 다 돈 뒤 최소값을 i 와 바꾸는 방식

https://coding-factory.tistory.com/615

선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬방법입니다. 코드가 직관적이기에 구현도 비교적 간단합니다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 
정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점인 정렬 방식입니다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식입니다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬입니다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여줍니다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있습니다.

분석

 

선택 정렬 (Selection Sort)

public class SelectionSort {
    public static void main(String[] args) {

        int[] arr = {5, 2, 9, 7, 14, 3, 1};

        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;

        }

        System.out.println(Arrays.toString(arr));
    }
}