선택 정렬

선택 정렬

선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법입니다.

정렬 방법

• 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
• 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
• 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다.
• 전체 데이터 크기만큼 index가 커질 때까지 반복한다.

시간 복잡도

선택 정렬의 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편입니다.

코드(Java)

아래 코드는 최댓값을 기준으로 정렬한 코드입니다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {11, 9, 23, 5, 12};
        int end = arr.length;

        int maxIdx = 0;

        while(end > 0) {
            for(int i=1; i<end; i++) {
                if(arr[maxIdx] < arr[i]) maxIdx = i;
            }

            int temp = arr[end-1];
            arr[end-1] = arr[maxIdx];
            arr[maxIdx] = temp;

            maxIdx = 0;
            end--;
        }

        for(int n: arr) {
            System.out.print(n + " ");
        }
    }
}

참고
Doit! 알고리즘 코딩 테스트 자바편