선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

 개념
최솟값을 찾아서 앞에 위치한 값과 교체하는 방법
<단순하지만 비효율적인 방법>
1. 주어진 데이터에서 최솟값을 탐색한다.
2. 탐색한 최솟값을 인덱스 첫 번째 위치한 값과 교체한다.
3. 첫 번째 위치한 값을 제외하고 나머지 데이터에서 최솟값을 다시 탐색 후 두 번째 위치한 값과 교체한다.
4. 마지막 데이터가 정렬될 때까지 위의 방법을 반복한다.

 시간 복잡도: T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

 Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] data) {
    int minData, temp;
 
    for(int i = 0; i < data.length-1; i++) {
        minData = i;
 
        for(int j = i+1; j < data.length; j++) {
            if(data[minData] > data[j]) {
                minData = j;
            }
        }
 
        temp = data[i];
        data[i] = data[minData];
        data[minData] = temp;
    }
}
cs


 코드 해석

✓ data = { 2, 9, 5, 4, 8, 1 }

           위와 같이 크기가 6인 배열의 예시가 있다.

✓ minData는 최솟값의 위치를 저장하기 위한 변수이다.

✓ temp는 변경할 위치의 데이터를 임시로 저장하기 위한 변수이다.


▪︎ 첫 번째 탐색

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 1

▫︎ (7번 라인) if(data[0] > data[1]) 결과 값이 (2 < 9)이므로 조건 불일치


▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 2

▫︎ (7번 라인) if(data[0] > data[2]) 결과 값이 (2 < 5)이므로 조건 불일치


▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[0] > data[3]) 결과 값이 (2 < 4)이므로 조건 불일치


▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[0] > data[4]) 결과 값이 (2 < 8)이므로 조건 불일치


▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[0] > data[5]) 결과 값이 (2 > 1)이므로 조건 일치

▫︎ (8번 라인) minData = 5


▫︎ (13번 ~ 15번 라인) { 2, 9, 5, 4, 8, 1 ☛ swap  { 1, 9, 5, 4, 8, 2 }


▪︎ 두 번째 탐색

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 1

▫︎ (6번 라인) j = 2

▫︎ (7번 라인) if(data[1] > data[2]) 결과 값이 (9 > 5)이므로 조건 일치

▫︎ (8번 라인) minData = 2


▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 2

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[2] > data[3]) 결과 값이 (5 > 4)이므로 조건 일치

▫︎ (8번 라인) minData = 3


▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[3] > data[4]) 결과 값이 (4 < 8)이므로 조건 불일치


▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[3] > data[5]) 결과 값이 (4 > 2)이므로 조건 일치

▫︎ (8번 라인) minData = 5


▫︎ (13번 ~ 15번 라인) { 1, 9, 5, 4, 8, 2 ☛ swap  { 12, 5, 4, 8, 9 }


▪︎ 세 번째 탐색

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 2

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[2] > data[3]) 결과 값이 (5 > 4)이므로 조건 일치

▫︎ (8번 라인) minData = 3


▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[3] > data[4]) 결과 값이 (4 < 8)이므로 조건 불일치


▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[3] > data[5]) 결과 값이 (4 < 9)이므로 조건 불일치


▫︎ (13번 ~ 15번 라인) { 12, 5, 4, 8, 9 } ☛ swap  { 1, 2, 4, 5, 8, 9 }


▪︎ 네 번째 탐색

▫︎ 첫 번째 ~ 세 번째 탐색과 동일하게 진행 (정렬이 완료되어서 설명 생략)


▪︎ 다섯 번째 탐색

▫︎ 첫 번째 ~ 세 번째 탐색과 동일하게 진행 (정렬이 완료되어서 설명 생략)


 코드 결과

모든 탐색과 정렬이 끝난 후 최종적으로 출력되는 결과 값은 { 1, 2, 4, 5, 8, 9 }이다.

선택한 배열의 위치를 제외한 나머지 배열에서 최솟값을 찾은 후 오름차순으로 정렬하는 방법이다.

(정렬된 배열의 위치는 탐색에서 제외)






✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 수정하도록 하겠습니다~^^)


✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)

댓글