티스토리 뷰

지난 포스팅에서는 버블 정렬(Bubble Sort) 에 대해 포스팅 해보았습니다.

이번에는 버블 정렬과 함께 기초적인 정렬 방법인 선택 정렬(Selection Sort) 에 대해 알아보도록 하겠습니다.

 

선택 정렬(Selection Sort)
선택 정렬(Selection Sort)은 제자리 정렬(in-place sorting) 알고리즘 중 하나로 주어진 리스트의 최소값을 찾아 그 값을 맨 앞으로 교체하며 정렬하는 방법입니다.
시간복잡도O(N2)으로 상당히 느리지만, 알고리즘이 단순하며 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

*위키백과 참조

https://algorithms.tutorialhorizon.com/selection-sort-java-implementation/selection-sort-gif/ 참조

 

선택 정렬(Selection Sort)은 정렬을 구현할 때 알고리즘을 모르더라도 가장 일반적인 접근방법 중 한가지라고 생각합니다.

그림을 통해 위의 설명을 부가적으로 돕도록 하겠습니다.

 

 

정렬이 안된 초기상태의 배열이 있습니다.

가장 처음 인덱스인 5와 전체 배열 중 가장 작은 1의 위치를 교환합니다.

이제 전체 배열의 첫번째 인덱스는 가장 최소값이므로, 두번째 탐색에서는 첫번째 인덱스를 제외한 숫자부터 검색을 합니다. 그림으로 확인해보면 두번째 인덱스인 5와 전체 배열 중 가장 작은 값인 2의 위치를 교환합니다.

위와 마찬가지로 전체 배열의 두번째 인덱스는 이미 최소값이기 때문에 다음 인덱스부터 검색을 진행합니다.

하지만 그림에서 3은 이미 올바른 위치에 있기 때문에 교환이 일어나지 않습니다.

다음 과정들을 되풀이하여 정렬을 완료합니다.

 

 

이미지 참조

https://m.blog.naver.com/PostView.nhn?logId=justant&logNo=20203018572&proxyReferer=https:%2F%2Fwww.google.com%2F


선택 정렬(Selection Sort) 구현 (For문)
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
32
33
34
35
36
37
38
39
40
 
public class SelectionSort {
 
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {            
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }
    
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
    
    public static void printArray(int[] array) {
        for(int data: array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    
    
    public static void main(String[] args) {
        int[] item = new int[] {5,1,3,7,2,9};
        System.out.print("선택정렬  전   : ");
        printArray(item);
        System.out.print("선택정렬  후   : ");
        selectionSort(item);
        printArray(item);
    }
    
}
 
cs

 

결과값

선택 정렬(Selection Sort)의 구현은 다음과 같습니다.

버블 정렬(Bubble Sort)와 마찬가지로, For문의 이해만으로 구현할 수 있기 때문에 구현이 쉽다고 생각합니다.

코드의 설명을 돕자면 다음과 같습니다.

selectionSort 를 구현하기 위한 메소드는 배열을 인자값으로 받습니다. (4번째줄)

첫번째 For문(외부)에서 마지막 요소는 자연스럽게 정렬이 됩니다. [ n-1번 반복 ] (5번째줄)

시작 인덱스를 담을 변수를 선언해주고 배열의 가장 처음을 초기값으로 정해줍니다. (6번째줄)

두번째 For문(내부)에서 항상 시작 인덱스가 최소값으로 정렬이 되기 때문에 제외한 나머지를 반복합니다. [ (n-1) - i번 반복 ]

(7번째줄)

전체 배열에서 가장 작은 값을 찾아줍니다. (8~9번째줄)

한번의 탐색을 끝났을 때 가장 작은 값이 선택이 됬다면, 가장 앞의 값과 찾은 작은 값을 swap해 줍니다. (12번째줄)

 

이해가 가지 않으신다면 [더보기]를 통해 명시적으로 확인해보시길 바랍니다.

또한 재귀적인 방법에 대해서도 확인하실 수 있습니다.

더보기

출력을 통해 흐름보기

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
32
33
34
35
36
37
38
39
40
41
42
 
public class SelectionSort {
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {            
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
            System.out.print("선택 정렬 " + (i+1)+"회차 : ");
            for(int data : array) {
                System.out.print(data + " ");
            }
            System.out.println();
        }
    }
    
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
    
    public static void printArray(int[] array) {
        for(int data: array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    
    
    public static void main(String[] args) {
        int[] item = new int[] {5,1,3,7,2,9};
        System.out.print("선 택 정 렬  전  : ");
        printArray(item);
        selectionSort(item);
    }
    
}
 
cs

 

결과값

 

내부적으로 다음과 같은 흐름을 볼 수 있다.

눈으로 확인해보기 위해 조금 많은 sysout이 있다.

불필요한 코드 제거는 위에서 확인하세요.


선택 정렬(Selection Sort)의 재귀적인 구현

다음과 같은 방법으로도 구현이 가능하다.

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
32
33
34
35
36
37
38
39
40
41
42
 
public class SelectionSort {
    
    public static void selectionSort(int[] array) {
        selectionSort(array, 0);
    }
    public static void selectionSort(int[] array, int start) {
        if(start < array.length - 1) {
            int minIndex = start;
            for(int i = start; i<array.length; i++) {
                if(array[i] < array[minIndex])
                    minIndex = i;
            }
            swap(array, start, minIndex);
            selectionSort(array, start + 1);
        }
    }
    
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
    
    public static void printArray(int[] array) {
        for(int data: array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] item = new int[] {5,1,3,7,2,9};
        System.out.print("선 택 정 렬  전  : ");
        printArray(item);
        System.out.print("선 택 정 렬  후  : ");
        selectionSort(item);
        printArray(item);
        
    }
}
 
cs

선택정렬(Selection Sort) 정리
버블 정렬(Bubble Sort)과 같은 시간 복잡도 O(N2)을 갖지만, 실제로는 버블 정렬(Bubble Sort)에 비해 조금 더 빠르다
버블 정렬과 마찬가지로 구현이 쉬운 편이다.
비교 횟수는 많지만, 교환 횟수는 적기 때문에 교환이 많이 이루어져야하는 자료 상태에서 효율적이다.
( 내림 차순으로 정렬된 자료 상태라면 최적이다.)
이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬 시 최악의 성능을 보인다.

다른 정렬들과의 시간복잡도 비교

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html 참조


그럼 2만

댓글
공지사항
글 보관함
최근에 올라온 글
최근에 달린 댓글