CSAlgorithm

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

Algorithm, CS

선택정렬

1. 선택정렬의 개념

선택정렬은 최솟값을 찾아 선택하여 위치를 바꿔가며 정렬하는 방식이다.
그럼 7, 9, 5, 3, 1 을 오름차순으로 선택정렬해보자.

1 단계 - index 0)

먼저 index 0 의 값인 7을 시작값으로 하여 7, 9, 5, 3, 1 중에 가장 작은 값을 검색하여 선택한다. 가장 작은 값은 1이기 때문에 아래와 같이 7과 1의 자리를 바꾼다.
7 9 5 3 1 => 1 9 5 3 7

그러면 아래와 같이 index 0 까지 정렬이 완료된 것이다.
1 9 5 3 7

2 단계 - index 1)

그 다음, index 1 의 값인 9를 시작값으로 하여 9, 5, 3, 7 중에 가장 작은 값을 검색하여 선택한다. 가장 작은 값은 3이기 때문에 아래와 같이 9와 3의 자리를 바꾼다.
1 9 5 3 7 => 1 3 5 9 7

그러면 아래와 같이 index 1 까지 정렬이 완료된 것이다.
1 3 5 9 7

3 단계 - index 2)

그 다음, index 2 의 값인 5를 시작값으로 하여 5, 9, 7 중에 가장 작은 값을 검색하여 선택한다. 가장 작은 값은 5이기 때문에 아래와 같이 5와 5의 자리를 바꾼다. 사실 자리를 바꾸는 작업을 진행하기는 하지만 동일한 자리이기 때문에 아무런 작업도 하지 않는 것처럼 보인다.
1 3 5 9 7 => 1 3 5 9 7

그러면 아래와 같이 index 2 까지 정렬이 완료된 것이다.
1 3 5 9 7

4 단계 - index 3)

그 다음, index 3 의 값인 9를 시작값으로 하여 9, 7 중에 가장 작은 값을 검색하여 선택한다. 가장 작은 값은 7이기 때문에 아래와 같이 9와 7의 자리를 바꾼다.
1 3 5 9 7 => 1 3 5 7 9

그러면 아래와 같이 index 3 까지 정렬이 완료된 것이다.
1 3 5 7 9

완료)

이 다음 단계는 할 필요가 없다. length가 5 일때, index 3 까지 정렬된 것이 전체가 정렬된 것이다. index 4 단계에서 남은 값이 1개이기 때문에 여기에서 최솟값을 찾는 것은 의미가 없기 때문이다. 즉, index = arr.length - 2 단계가 끝이다. 따라서 아래와 같이 정렬이 완료되었다.
1 3 5 7 9


2. 선택정렬 시간복잡도

최선 평균 최악
O(n^2) O(n^2) O(n^2)


3. 선택정렬 JAVA 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 배열 a에서 i 위치와 j 위치의 값을 서로 바꾼다.
static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 배열 a의 start 위치부터 끝까지에서 가장 작은 값의 위치를 리턴한다.
static int findMin(int[] a, int start) {
    int minIndex = start;
    for(int i=start; i<a.length; i++) {
        if(a[i] < a[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}

// 선택정렬
static void selectionSort(int[] a) {
    for(int i=0; i<a.length-1; i++) {
        int minIndex = findMin(a, i);
        swap(a, i, minIndex);
    }
}

public static void main(String[] args) {
    int[] a = { 7, 9, 5, 3, 1 };
    selectionSort(a);
    System.out.println(Arrays.toString(a)); // 출력결과 : [1, 3, 5, 7, 9]
}
Share