[알고리즘] 선택 정렬(Selection sort)

📍선택 정렬이란?

 

1. 주어진 리스트 중에 최소값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.   

 

선택 정렬은 위 규칙에 따라 정렬이 이루어진다. 

 

실행 예시

0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

---

시간 복잡도	비교	교환
최악의 경우	O(n^2)	O(n)
최선의 경우	O(n^2)	O(n)
평균	O(n^2)	O(n)

 

선택 정렬은 시간의 복잡도는 O(n^2)으로 속도가 느린 정렬 방법에 속하지만, 구현이 간단하다는 장점이 있다. 

또, 버블 정렬보다는 선택 정렬이 항상 시간 복잡도 측면에서 우수하다.

---

📍선택 정렬 구현 코드 | Java

    static void selectionSort(int[] arr) {
        int indexMin, temp;

        for (int i = 0; i < arr.length - 1; i++) {
            //for문으로 배열을 돌면서 배열의 가장 작은 원소의 인덱스를 찾아냄
            indexMin = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[indexMin]) {
                    indexMin = j;
                }
            }

            //가장 작은 원소를 기준 원소와 바꿔치기
            temp = arr[indexMin];
            arr[indexMin] = arr[i];
            arr[i] = temp;

            System.out.println("배열: "+Arrays.toString(arr));
        }

        System.out.println("\n정렬된 최종 배열: "+Arrays.toString(arr));
    }
    
        public static void main(String[] args) {
        int[] arr = {5, 1, 9, 7, 2, 3};
        selectionSort(arr);
    }

 

📍실행 결과 

기존 배열: {5, 1, 9, 7, 2, 3}

 

---

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